1176: [Balkan2007]Mokia
Time Limit: 30 Sec Memory Limit: 162 MB Submit: 1059 Solved: 432 [Submit][Status][Discuss] Description维护一个W*W的矩阵，初始值均为S.每次操作能够添加某格子的权值,或询问某子矩阵的总权值.改动操作数M<=160000,询问数Q<=10000,W<=2000000.
Input第一行两个整数,S,W;当中S为矩阵初始值;W为矩阵大小
接下来每行为一下三种输入之中的一个(不包括引號):
“1 x y a”
“2 x1 y1 x2 y2”
“3”
输入1:你须要把(x,y)(第x行第y列)的格子权值添加a
输入2:你须要求出以左上角为(x1,y1),右下角为(x2,y2)的矩阵内全部格子的权值和,并输出
输入3:表示输入结束
Output对于每一个输入2,输出一行,即输入2的答案
Sample Input 0 41 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output 35
HINT保证答案不会超过int范围
Source
cdq分治的模板题然而我如今才做这个题。
。。
差分一下询问操作。对全部操作按y排序。 树状数组维护一下。然后就能够了。
自从看过了Tsinsen上的姿势分 我写代码都開始丧心病狂了
#include#include #include #include #include #define MAXN 200000#define SIZE 2000010#define lowbit(x) (x&(-x))using namespace std;int w;int top,opt,L,R,l,r,delta,Top;struct Query{ int op; int x,y,A; int t,id; bool operator <(const Query& a)const { if (x == a.x && y == a.y) return op < a.op; if (x == a.x) return y < a.y; return x < a.x; }}que[MAXN],newq[MAXN];int ans[MAXN],c[SIZE];inline void in(int &x){ x=0;char ch = getchar(); while (!(ch >= '0' && ch <= '9')) ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0',ch = getchar();}inline void add(int i,int x){ while (i && i <= w) c[i] += x,i += lowbit(i);}inline int query(int i){ int ret = 0; while (i) ret += c[i],i -= lowbit(i); return ret;}inline void Solve(int l,int r){ int mid = (l + r) >> 1,tp1 = l,tp2 = mid + 1; if (l == r) return; for (int i = l;i <= r;i++) { if (que[i].t <= mid && que[i].op == 1) add(que[i].y,que[i].A); if (que[i].t > mid && que[i].op == 2) ans[que[i].id] += query(que[i].y) * que[i].A; } for (int i = l;i <= r;i++) if (que[i].t <= mid && que[i].op == 1) add(que[i].y,-que[i].A); for (int i = l;i <= r;i++) if (que[i].t <= mid) newq[tp1++] = que[i]; else newq[tp2++] = que[i]; memcpy(que+l,newq+l,sizeof(Query)*(r - l + 1)); Solve(l,mid);Solve(mid+1,r); }int main(){ freopen("mokia.in","r",stdin); freopen("mokia.out","w",stdout); in(opt);in(w); while (1) { in(opt); if (opt == 3) break; switch (opt) { case 1: in(L);in(R);in(delta); que[++top].op = opt;que[top].x = L;que[top].y = R;que[top].A = delta;que[top].t = top; break; case 2: in(L);in(R);in(l);in(r); que[++top].op = opt;que[top].x = L - 1;que[top].y = R - 1;que[top].t = top;que[top].A = 1;que[top].id = ++Top; que[++top].op = opt;que[top].x = L - 1;que[top].y = r;que[top].t = top;que[top].A = -1;que[top].id = Top; que[++top].op = opt;que[top].x = l;que[top].y = R - 1;que[top].t = top;que[top].A = -1;que[top].id = Top; que[++top].op = opt;que[top].x = l;que[top].y = r;que[top].t = top;que[top].A = 1;que[top].id = Top; break; } } sort(que + 1,que + top + 1); Solve(1,top); for (int i = 1;i <= Top;i++) printf("%d\n",ans[i]);}