「BZOJ1176」[Balkan2007] Mokia
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 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
5
HINT
保证答案不会超过int范围
题解
补了下CDQ分治TAT
按照时间对操作分治。。。
具体还是找度娘吧。。。毕竟入门题题解到处是
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int s,w,m; int ans[10005]; int t[2000005]; struct que{ int x,y,val,pos,id,opt; }q[200005],tmp[200005]; bool operator<(que a,que b) { if(a.x==b.x&&a.y==b.y)return a.opt<b.opt; if(a.x==b.x)return a.y<b.y; return a.x<b.x; } void addquery() { int x1=read(),y1=read(),x2=read(),y2=read(); int pos=++ans[0]; q[++m].pos=pos;q[m].id=m;q[m].x=x1-1;q[m].y=y1-1;q[m].val=1;q[m].opt=1; q[++m].pos=pos;q[m].id=m;q[m].x=x2;q[m].y=y2;q[m].val=1;q[m].opt=1; q[++m].pos=pos;q[m].id=m;q[m].x=x1-1;q[m].y=y2;q[m].val=-1;q[m].opt=1; q[++m].pos=pos;q[m].id=m;q[m].x=x2;q[m].y=y1-1;q[m].val=-1;q[m].opt=1; } void add(int x,int val) { for(int i=x;i<=w;i+=i&-i)t[i]+=val; } int query(int x) { int tmp=0; for(int i=x;i;i-=i&-i)tmp+=t[i]; return tmp; } void cdq(int l,int r) { if(l==r)return; int mid=(l+r)>>1,l1=l,l2=mid+1; for(int i=l;i<=r;i++) { if(q[i].id<=mid&&!q[i].opt)add(q[i].y,q[i].val); if(q[i].id>mid&&q[i].opt)ans[q[i].pos]+=q[i].val*query(q[i].y); } for(int i=l;i<=r;i++) if(q[i].id<=mid&&!q[i].opt)add(q[i].y,-q[i].val); for(int i=l;i<=r;i++) if(q[i].id<=mid)tmp[l1++]=q[i]; else tmp[l2++]=q[i]; for(int i=l;i<=r;i++) q[i]=tmp[i]; cdq(l,mid);cdq(mid+1,r); } int main() { s=read();w=read(); while(1) { int opt=read(); if(opt==1) { q[++m].x=read(),q[m].y=read(),q[m].val=read(); q[m].id=m; } else if(opt==2) addquery(); else break; } sort(q+1,q+m+1); cdq(1,m); for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]); return 0; } |
计数器 9856650
OI 课件=>
OI 课件=>
Orz 您的s好像没用
代码里有至少有20个s
额。。。这题据说s是数据编号。。确实没用
s不是初始值么…