v 0. Pasted by alias as cpp at 2013-02-07 03:50:24 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 bb)
  22. {
  23.     if (!bb)
  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. typedef vector<int> vi;
  36.  
  37. const int N = 1 << 8;
  38.  
  39. struct RSQ2 {
  40.     int a[N * 2][N * 2];
  41.     RSQ2()
  42.     {
  43.         memset(a, 0, sizeof(a));
  44.     }
  45.  
  46.     void Add(int posX, int posY, int dx)
  47.     {
  48.         for (int i = posX + N; i; i >>= 1)
  49.             for (int j = posY + N; j; j >>= 1)
  50.                 a[i][j] += dx;
  51.     }
  52.  
  53.     int Sum(int Lx, int Rx, int Ly, int Ry) const
  54.     {
  55.         int res = 0;
  56.         for (Lx += N, Rx += N; Lx < Rx; Lx >>= 1, Rx >>= 1) {
  57.             if (Lx & 1) {
  58.                 int tLy = Ly;
  59.                 int tRy = Ry;
  60.                 for (tLy += N, tRy += N; tLy < tRy; tLy >>= 1, tRy >>= 1) {
  61.                     if (tLy & 1)
  62.                         res += a[Lx][tLy++];
  63.                     if (tRy & 1)
  64.                         res += a[Lx][--tRy];
  65.                 }
  66.                 Lx++;
  67.             }
  68.             if (Rx & 1) {
  69.                 --Rx;
  70.                 int tLy = Ly;
  71.                 int tRy = Ry;
  72.                 for (tLy += N, tRy += N; tLy < tRy; tLy >>= 1, tRy >>= 1) {
  73.                     if (tLy & 1)
  74.                         res += a[Rx][tLy++];
  75.                     if (tRy & 1)
  76.                         res += a[Rx][--tRy];
  77.                 }
  78.             }
  79.         }
  80.         return res;
  81.     }
  82. };
  83.  
  84. void Build(int L, int R, int *res) {
  85.     int resc = 0;
  86.     for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
  87.         if (L & 1)
  88.             res[resc++] = L++;
  89.         if (R & 1)
  90.             res[resc++] = --R;
  91.     }
  92.     res[resc] = -1;
  93. }
  94.  
  95. struct RSQ22 {
  96.     int a[N * 2][N * 2];
  97.     RSQ22()
  98.     {
  99.         memset(a, 0, sizeof(a));
  100.     }
  101.  
  102.     void Add(int posX, int posY, int dx)
  103.     {
  104.         for (int i = posX + N; i; i >>= 1)
  105.             for (int j = posY + N; j; j >>= 1)
  106.                 a[i][j] += dx;
  107.     }
  108.  
  109.     int Sum(int Lx, int Rx, int Ly, int Ry) const
  110.     {
  111.         int res = 0;
  112.         static int x[142];
  113.         static int y[142];
  114.         Build(Lx, Rx, x);
  115.         Build(Ly, Ry, y);
  116.         for (int i = 0; x[i] != -1; ++i)
  117.             for (int j = 0; y[j] != -1; ++j)
  118.                 res += a[x[i]][y[j]];
  119.         return res;
  120.     }
  121. };
  122.  
  123. int main()
  124. {
  125.     return 0;
  126. }


Editing is locked.