[BZOJ1176]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

Sample Output

3
5

时隔五个月再做这道题又有新的理解

首先把操作看成四个二维前缀和相加减，然后对于每个操作有三个维度：时间，$x$轴，$y$轴

考虑对一个查询，哪些修改操作会对它产生影响，当且仅当在它之前发生且在它的左下方

所以我们可以按照$x$轴先排序消除$x$轴的影响

然后对归并排序时间戳使得左右两部分的操作有序

然后按时间戳加入修改和询问就完成了

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define M 2000010

 using namespace std;

 int read() {

     char ch=getchar();int x=;

     while(ch>''||ch<'') ch=getchar();

     while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

     return x;

 }

 int n,S,tot,qcnt,tim;

 int ans[M],f[M];

 struct ASK{int t,x,y,w,ot,id;}q[M],tmp[M];

 bool cmp(ASK a1,ASK a2) {

     if(a1.x!=a2.x) return a1.x<a2.x;

     if(a1.y!=a2.y) return a1.y<a2.y;

     return a1.id<a2.id;

 }

 void add(int loc,int v) {

     for(int i=loc;i<=n;i+=(i&-i)) f[i]+=v;

 }

 int query(int loc) {

     int ans=;

     for(int i=loc;i;i-=(i&-i)) ans+=f[i];

     return ans;

 }

 void CDQ(int l,int r) {

     if(l==r) return;

     int mid=(l+r)>>;

     CDQ(l,mid);CDQ(mid+,r);

     int t1=l,t2=mid+,now=l;

     while(t1<=mid||t2<=r) {

         if(t1<=mid&&q[t1].t<q[t2].t||t2>r) {

             if(q[t1].ot==) add(q[t1].y,q[t1].w);

             tmp[now++]=q[t1++];

         }

         else {

             if(q[t2].ot==) ans[q[t2].id]+=q[t2].w*query(q[t2].y);

             tmp[now++]=q[t2++];

         }

     }

     for(int i=l;i<=mid;i++)

         if(q[i].ot==)

             add(q[i].y,-q[i].w);

     for(int i=l;i<=r;i++) q[i]=tmp[i];

 }

 int main() {

     S=read();n=read();

     while() {

         int opt=read();

         if(opt==) break;

         if(opt==) {

             int x=read(),y=read(),z=read();

             q[++tot]=(ASK){++tim,x,y,z,};

         }

         else {

             int x1=read(),y1=read(),x2=read(),y2=read();

             ans[++qcnt]=(x2-x1+)*(y2-y1+)*S;

             q[++tot]=(ASK){++tim,x1-,y1-,,,qcnt};

             q[++tot]=(ASK){++tim,x2,y2,,,qcnt};

             q[++tot]=(ASK){++tim,x1-,y2,-,,qcnt};

             q[++tot]=(ASK){++tim,x2,y1-,-,,qcnt};

         }

     }

     sort(q+,q++tot,cmp);

     CDQ(,tot);

     for(int i=;i<=qcnt;i++) printf("%d\n",ans[i]);

     return ;

 }

巴特西