原題

給出W×W的矩陣（S沒有用，題目有誤），給出無限次操作，每次操作的含義為：
輸入1:你需要把(x,y)(第x行第y列)的格子權值增加a
輸入2:你需要求出以左下角為(x1,y1),右上角為(x2,y2)的矩陣內所有格子的權值和,并輸出
輸入3:表示輸入結束

---

因為修改之間相互獨立，所以可以用CDQ。
三個維度分別為時間，x軸，y軸。
簡單的三維偏序即可。

#include<cstdio>
#include<algorithm>
#define N 200010
using namespace std;
struct hhh
{int x,y,w,pos,id,op;bool operator < (const hhh &b) const{if (x==b.x && y==b.y) return op<b.op;if (x==b.x) return y<b.y;return x<b.x;}
}q[N],tmp[N];
int s,w,n,ans[N],m,op,f[10*N];int read()
{int ans=0,fu=1;char j=getchar();for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';return ans*fu;
}void addquery()
{int lx=read(),ly=read(),rx=read(),ry=read();int pos=++ans[0];q[++m].pos=pos;q[m].id=m;q[m].x=lx-1;q[m].y=ly-1;q[m].w=1;q[m].op=1;q[++m].pos=pos;q[m].id=m;q[m].x=rx;q[m].y=ry;q[m].w=1;q[m].op=1;q[++m].pos=pos;q[m].id=m;q[m].x=lx-1;q[m].y=ry;q[m].w=-1;q[m].op=1;q[++m].pos=pos;q[m].id=m;q[m].x=rx;q[m].y=ly-1;q[m].w=-1;q[m].op=1; 
}void add(int x,int y)
{while (x<=w){f[x]+=y;x+=x&-x;}
}int query(int x)
{int ans=0;while (x){ans+=f[x];x-=x&-x;}return ans;
}void CDQ(int l,int r)
{if (l==r) return ;int mid=(l+r)>>1,i=l,j=mid+1;for (int k=l;k<=r;k++){if (q[k].id<=mid && !q[k].op)add(q[k].y,q[k].w);if (q[k].id>mid && q[k].op)ans[q[k].pos]+=q[k].w*query(q[k].y);}for (int k=l;k<=r;k++)//清空樹狀數組if (q[k].id<=mid && !q[k].op) add(q[k].y,-q[k].w);for (int k=l;k<=r;k++)if (q[k].id<=mid) tmp[i++]=q[k];else tmp[j++]=q[k];for (int k=l;k<=r;k++)q[k]=tmp[k];CDQ(l,mid);CDQ(mid+1,r);
}int main()
{s=read();w=read();while (1){op=read();if (op==1){q[++m].x=read();q[m].y=read();q[m].w=read();q[m].id=m;}else if (op==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;
}

轉載于:https://www.cnblogs.com/mrha/p/8057667.html

總結

以上是生活随笔為你收集整理的[bzoj] 1176 Mokia || CDQ分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。