[bzoj] 1176 Mokia || CDQ分治

原题

给出W×W的矩阵（S没有用，题目有误），给出无限次操作，每次操作的含义为：

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

---

因为修改之间相互独立，所以可以用CDQ。

三个维度分别为时间，x轴，y轴。

简单的三维偏序即可。

#include
#include
#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'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
",ans[i]);return 0;
}