题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1176
题意：维护一个 W*W 的矩阵，初始值均为 S. 每次操作可以增加某格子的权值, 或询问某子矩阵的总权值. 修改操作数 M<=160000, 询问数 Q<=10000,W<=2000000.
CDQ 分治... 以前这种题都用 KD-tree 水的...
|
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 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 2000010 #define Q 200010 #define ll long long using namespace std; inline 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; } struct zgz { int x,y,v,type,id; }q[Q],tmp[Q]; int S,n,opt,cnt,top,tot,last; int ans[Q],pos[Q]; int c[N]; void add(int x,int v) { for(int i=x;i<=n;i+=i&(-i)) c[i]+=v; } int query(int x) { int ret=0; for(int i=x;i;i-=i&(-i)) ret+=c[i]; return ret; } void CDQ(int l,int r) { if(l==r)return ; int mid=(l+r)>>1; CDQ(l,mid),CDQ(mid+1,r); int i=l,j=mid+1;last=0; while(j<=r) { while(q[i].type==2&&i<=mid)i++; while(q[j].type==1&&j<=r)j++; if(i<=mid&&q[i].x<=q[j].x) add(q[i].y,q[i].v),last=i++; else if(j<=r) ans[q[j].id]+=query(q[j].y),j++; } for(i=l;i<=last;i++)if(q[i].type==1)add(q[i].y,-q[i].v); i=l,j=mid+1; for(int k=l;k<=r;k++) if(j>r||(i<=mid&&q[i].x<=q[j].x))tmp[k]=q[i++];else tmp[k]=q[j++]; for(int i=l;i<=r;i++) q[i]=tmp[i]; } int main() { S=read(),n=read(); while(1) { opt=read(); if(opt==1) q[++cnt].x=read(),q[cnt].y=read(),q[cnt].v=read(),q[cnt].type=1; if(opt==2) { int x1=read(),y1=read(),x2=read(),y2=read();pos[++tot]=cnt;ans[cnt+1]=(x2-x1+1)*(y2-y1+1)*S; q[++cnt].x=x2,q[cnt].y=y2,q[cnt].type=2,q[cnt].id=cnt; q[++cnt].x=x1-1,q[cnt].y=y1-1,q[cnt].type=2,q[cnt].id=cnt; q[++cnt].x=x1-1,q[cnt].y=y2,q[cnt].type=2,q[cnt].id=cnt; q[++cnt].x=x2,q[cnt].y=y1-1,q[cnt].type=2,q[cnt].id=cnt; } if(opt==3)break; } CDQ(1,cnt); for(int i=1,x=pos[i];i<=tot;x=pos[++i]) printf("%d\n",ans[x+1]+ans[x+2]-ans[x+3]-ans[x+4]); } |
Comments | NOTHING