[文章目录]
Descripton
你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：
1 x y A,1<=x,y<=N，A是正整数,将格子x,y里的数字加上A
2 x1 y1 x2 y2,1<=x1<= x2<=N,1<=y1<= y2<=N:输出x1 y1 x2 y2这个矩形内的数字和
3 终止程序
话说以前怎么能够傻到以为这道题就是个splay。。。
将询问按时间分治，考虑前期修改对后期询问的影响，将询问子矩阵容斥，变成四个询问。然后就变成了三维偏序统计权值和的问题了，处理影响的时候用树状数组维护和。
话说每到一个区间进行sort的常数真是感人。懒得改归并了。
以下是2683（慢到死）的代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot,f[501000];
struct node
{
int id,x,y,A,ans;
}a[801000];
bool cmp1(node x,node y){return x.x==y.x?x.id<y.id:x.x<y.x;}
bool cmp2(node x,node y){return x.id<y.id;}
void fix(int x,int y) {while(x<=n) f[x]+=y,x+=-x&x;}
void clear(int x) {while(x<=n) f[x]=0,x+=-x&x;}
int query(int x)
{
if(!x) return 0; int re=0;
while(x>0) re+=f[x],x-=-x&x;
return re;
}
void solve(int l,int r)
{
if(l==r) return ;
int mid=l+r>>1;
solve(l,mid); sort(a+l,a+r+1,cmp1);
for(int i=l;i<=r;++i)
{
if(a[i].id<=mid&&a[i].A) fix(a[i].y,a[i].A);
if(a[i].id>mid&&!a[i].A) a[i].ans+=query(a[i].y);
}
sort(a+l,a+r+1,cmp2);
for(int i=l;i<=r;++i)
if(a[i].A) clear(a[i].y);
solve(mid+1,r);
}
int main()
{
scanf("%d",&n); int sw,x,xx,y,yy;
while(1)
{
scanf("%d",&sw);
if(sw==3) break;
if(sw==1)
{
tot++;
scanf("%d%d%d",&a[tot].x,&a[tot].y,&a[tot].A);
a[tot].id=tot;
}
else
{
scanf("%d%d%d%d",&x,&y,&xx,&yy);
tot++; a[tot].id=tot; a[tot].x=x-1; a[tot].y=y-1;
tot++; a[tot].id=tot; a[tot].x=xx; a[tot].y=y-1;
tot++; a[tot].id=tot; a[tot].x=x-1; a[tot].y=yy;
tot++; a[tot].id=tot; a[tot].x=xx; a[tot].y=yy;
}
}
solve(1,tot); int i=1;
while(i<=tot)
{
if(a[i].A) ++i;
else printf("%d\n",a[i+3].ans-a[i+2].ans-a[i+1].ans+a[i].ans),i+=4;
}
return 0;
}