v 0. Pasted by alias as cpp at 2011-12-07 03:15:26 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 = 1024;
  36.  
  37. struct RSQ {
  38.     int a[N * 2][N * 2];
  39.     RSQ()
  40.     {
  41.         memset(a, 0, sizeof(a));
  42.     }
  43.     void Build(int L, int R, int* ar) const
  44.     {
  45.         int k = 0;
  46.         for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
  47.             if (L & 1)
  48.                 ar[k++] = L++;
  49.             if (R & 1)
  50.                 ar[k++]= --R;
  51.         }
  52.         ar[k] = -1;
  53.     }
  54.     void Add(int posI, int posJ, int dVal)
  55.     {
  56.         for (int i = posI + N; i; i >>= 1)
  57.             for (int j = posJ + N; j; j >>= 1)
  58.                 a[i][j] += dVal;
  59.     }
  60.     int Sum(int Lx, int Rx, int Ly, int Ry) const
  61.     {
  62.         int res = 0;
  63.         int x[100];
  64.         int y[100];
  65.         Build(Lx, Rx, x);
  66.         Build(Ly, Ry, y);
  67.         for (int i = 0; x[i] != -1; i++)
  68.             for (int j = 0; y[j] != -1; j++)
  69.                 res += a[x[i]][y[j]];
  70.         return res;
  71.     }
  72. };
  73.  
  74. //struct invRSQ analogious
  75.  


Editing is locked.