Advertisement
Guest User

Untitled

a guest
Jan 18th, 2017
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.71 KB | None | 0 0
  1. #include<stdio.h>
  2. #define TAM 1048576
  3.  
  4. int tree[TAM+1], lazy[TAM+1];
  5.  
  6. void updateRange(int node, int L, int U, int R, int D, int left, int up, int right, int down, int val)
  7. {
  8.     int node2 = node*4;
  9.     if(lazy[node] != 0)
  10.     {
  11.         if(!((U == D) && (L == R)))
  12.         {
  13.             lazy[node2+1] += lazy[node];
  14.             lazy[node2+2] += lazy[node];
  15.             lazy[node2+3] += lazy[node];
  16.             lazy[node2+4] += lazy[node];
  17.         }
  18.         else
  19.             tree[node] += lazy[node];  
  20.         lazy[node] = 0;
  21.     }
  22.     if(U > D || L > R || U > down || D < up || L > right || R < left)
  23.         return;
  24.     if((up <= U) && (left <= L) && (right >= R) && (down >= D))
  25.     {
  26.         if(!((U == D) && (L == R)))
  27.         {
  28.             lazy[node2+1] += val;
  29.             lazy[node2+2] += val;
  30.             lazy[node2+3] += val;
  31.             lazy[node2+4] += val;
  32.         }
  33.         else
  34.             tree[node] += val; 
  35.         return;
  36.     }
  37.     int mid = (L + R) / 2;
  38.     int mid2 = (U + D) / 2;
  39.     updateRange(node2+1, L, U, mid, mid2, left, up, right, down, val);
  40.     updateRange(node2+2, L, mid2+1, mid, D, left, up, right, down, val);
  41.     updateRange(node2+3, mid+1, U, R, mid2, left, up, right, down, val);
  42.     updateRange(node2+4, mid+1, mid2+1, R, D, left, up, right, down, val);
  43. }
  44.  
  45. int queryRange(int node, int L, int U, int R, int D, int x, int y)
  46. {
  47.     int node2 = node*4;
  48.     if(U > D || L > R || U > y || D < y || L > x || R < x)
  49.         return 0;
  50.     if(lazy[node] != 0)
  51.     {
  52.         if(!((U == D) && (L == R)))
  53.         {
  54.             lazy[node2+1] += lazy[node];
  55.             lazy[node2+2] += lazy[node];
  56.             lazy[node2+3] += lazy[node];
  57.             lazy[node2+4] += lazy[node];
  58.         }
  59.         else
  60.             tree[node] += lazy[node];
  61.         lazy[node] = 0;
  62.     }
  63.     if(U == y && L == x && R == x && D == y)
  64.         return tree[node];
  65.     int mid = (L + R) / 2;
  66.     int mid2 = (U + D) / 2;
  67.     int p1 = queryRange(node2+1, L, U, mid, mid2, x, y);
  68.     int p2 = queryRange(node2+2, L, mid2+1, mid, D, x, y);
  69.     int p3 = queryRange(node2+3, mid+1, U, R, mid2, x, y);
  70.     int p4 = queryRange(node2+4, mid+1, mid2+1, R, D, x, y);
  71.     return queryRange(node2+1, L, U, mid, mid2, x, y) + queryRange(node2+2, L, mid2+1, mid, D, x, y) + queryRange(node2+3, mid+1, U, R, mid2, x, y)
  72. }
  73.  
  74. main()
  75. {
  76.     int N, i, a, b, c, d, e;
  77.     char op;
  78.     for(i = 0; i <= TAM; i++)
  79.         lazy[i] = 0;
  80.     scanf("%d", &N);
  81.     while(N--)
  82.     {
  83.         scanf("%*c%c", &op);
  84.         if(op == 'A')
  85.         {
  86.             scanf("%d %d", &a, &b);
  87.             printf("%d\n", queryRange(0, 1, 1, 512, 512, a, b));
  88.         }
  89.         else
  90.         {
  91.             scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
  92.             updateRange(0, 1, 1, 512, 512, a, b, c, d, e);
  93.         }
  94.     }
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement