Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #define TAM 1048576
- int tree[TAM+1], lazy[TAM+1];
- void updateRange(int node, int L, int U, int R, int D, int left, int up, int right, int down, int val)
- {
- int node2 = node*4;
- if(lazy[node] != 0)
- {
- if(!((U == D) && (L == R)))
- {
- lazy[node2+1] += lazy[node];
- lazy[node2+2] += lazy[node];
- lazy[node2+3] += lazy[node];
- lazy[node2+4] += lazy[node];
- }
- else
- tree[node] += lazy[node];
- lazy[node] = 0;
- }
- if(U > D || L > R || U > down || D < up || L > right || R < left)
- return;
- if((up <= U) && (left <= L) && (right >= R) && (down >= D))
- {
- if(!((U == D) && (L == R)))
- {
- lazy[node2+1] += val;
- lazy[node2+2] += val;
- lazy[node2+3] += val;
- lazy[node2+4] += val;
- }
- else
- tree[node] += val;
- return;
- }
- int mid = (L + R) / 2;
- int mid2 = (U + D) / 2;
- updateRange(node2+1, L, U, mid, mid2, left, up, right, down, val);
- updateRange(node2+2, L, mid2+1, mid, D, left, up, right, down, val);
- updateRange(node2+3, mid+1, U, R, mid2, left, up, right, down, val);
- updateRange(node2+4, mid+1, mid2+1, R, D, left, up, right, down, val);
- }
- int queryRange(int node, int L, int U, int R, int D, int x, int y)
- {
- int node2 = node*4;
- if(U > D || L > R || U > y || D < y || L > x || R < x)
- return 0;
- if(lazy[node] != 0)
- {
- if(!((U == D) && (L == R)))
- {
- lazy[node2+1] += lazy[node];
- lazy[node2+2] += lazy[node];
- lazy[node2+3] += lazy[node];
- lazy[node2+4] += lazy[node];
- }
- else
- tree[node] += lazy[node];
- lazy[node] = 0;
- }
- if(U == y && L == x && R == x && D == y)
- return tree[node];
- int mid = (L + R) / 2;
- int mid2 = (U + D) / 2;
- int p1 = queryRange(node2+1, L, U, mid, mid2, x, y);
- int p2 = queryRange(node2+2, L, mid2+1, mid, D, x, y);
- int p3 = queryRange(node2+3, mid+1, U, R, mid2, x, y);
- int p4 = queryRange(node2+4, mid+1, mid2+1, R, D, x, y);
- 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)
- }
- main()
- {
- int N, i, a, b, c, d, e;
- char op;
- for(i = 0; i <= TAM; i++)
- lazy[i] = 0;
- scanf("%d", &N);
- while(N--)
- {
- scanf("%*c%c", &op);
- if(op == 'A')
- {
- scanf("%d %d", &a, &b);
- printf("%d\n", queryRange(0, 1, 1, 512, 512, a, b));
- }
- else
- {
- scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
- updateRange(0, 1, 1, 512, 512, a, b, c, d, e);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement