v 0. Pasted by alias as cpp at 2011-12-07 02:56:10 MSK and set expiration to never.

Paste will expire never.

  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stdlib.h>
  6. #include <ctime>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <string>
  11. #include <math.h>
  12. #include <queue>
  13. #include <memory.h>
  14. #include <iostream>
  15. #include <stack>
  16. #include <complex>
  17. #include <list>
  18.  
  19. using namespace std;
  20.  
  21. void ASS(bool b)
  22. {
  23.     if (!b)
  24.     {
  25.         ++*(int*)0;
  26.     }
  27. }
  28.  
  29. #define FOR(i, x) for (int i = 0; i < (int)(x); i++)
  30. #define CL(x) memset(x, 0, sizeof(x))
  31. #define CLX(x, y) memset(x, y, sizeof(x))
  32.  
  33. #pragma comment(linker, "/STACK:106777216")
  34.  
  35. const int N = 1 << 16;
  36.  
  37. struct RSQ {
  38.     int a[N * 2];
  39.     RSQ()
  40.     {
  41.         memset(a, 0, sizeof(a));
  42.     }
  43.     void Add(int pos, int dx) // add dx to a[pos]
  44.     {
  45.         for (int i = pos + N; i; i >>= 1)
  46.             a[i] += dx;
  47.     }
  48.     int Sum(int L, int R) const // sum on interval [L, R) R-- for [L, R]
  49.     {
  50.         int res = 0;
  51.         for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
  52.             if (L & 1)
  53.                 res += a[L++];
  54.             if (R & 1)
  55.                 res += a[--R];
  56.         }
  57.         return res;
  58.     }
  59. };
  60.  
  61. struct invRSQ {
  62.     int a[N * 2];
  63.     invRSQ()
  64.     {
  65.         memset(a, 0, sizeof(a));
  66.     }
  67.     int Sum(int pos) const // sum in pos
  68.     {
  69.         int res = 0;
  70.         for (int i = pos + N; i; i >>= 1)
  71.             res += a[i];
  72.         return res;
  73.     }
  74.     void Sum(int L, int R, int dx) // add dx to interval [L, R) R-- for [L, R]
  75.     {
  76.         for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
  77.             if (L & 1)
  78.                 a[L++] += dx;
  79.             if (R & 1)
  80.                 a[--R] += dx;
  81.         }
  82.     }
  83. };


Editing is locked.