题意:链接
**方法:**cdq分治+树状数组
解析:
首先对于这道题，看了范围之后。二维的数据结构是显然不能过的。于是我们可能会考虑把一维排序之后还有一位上数据结构什么的，然而cdq分治却可以非常好的体现它的作用。
首先，对于每个询问求和，显然是x在它左边的而且出现时间在它之前的全部的change对他可能会有影响。
我们依照x第一关键字,y第二关键字,操作第三关键字来排序全部的询问。然后在cdq的时候，每次递归处理左半区间，依照x动态的将y这一列的值加到树状数组里。来更新右半边的全部询问，注意这里的树状数组是须要清的，也就是每次cdq都是採用不同的树状数组。
另:这题神坑。数组开小不是RE而是WA
数组范围是要开到200000*4的，由于对于每个1操作。是一个操作，而2操作依据容斥原理，是4个操作。
所以复杂度大概是多少呢O(nlog^2(n))cdq+树状数组。n<=800000
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 800010
#define Q q[tot]
using namespace std;
struct node
{
int opt,x,y,A,no,belong;
}q[N],nq[N];
int n;
int jd,tot,T;
int ans[N];
int c[N];
int lowbit(int x){return x&(-x);}
int getsum(int x){int ret=0;while(x){ret+=c[x],x-=lowbit(x);}return ret;}
void update(int x,int v){while(x<=n){c[x]+=v;x+=lowbit(x);}}
int cmp(node a,node b)
{
if(a.x==b.x&&a.y==b.y)return a.opt<b.opt;
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
void sov(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1,l1=l,l2=mid+1;
for(int i=l;i<=r;i++)
{
if(q[i].no<=mid&&q[i].opt==1)update(q[i].y,q[i].A);
if(q[i].no>mid&&q[i].opt==2)ans[q[i].belong]+=getsum(q[i].y);
}
for(int i=l;i<=r;i++)
{
if(q[i].no<=mid&&q[i].opt==1)update(q[i].y,-q[i].A);
}
l1=l,l2=mid+1;
for(int i=l;i<=r;i++){if(q[i].no<=mid)nq[l1++]=q[i];else nq[l2++]=q[i];}
for(int i=l;i<=r;i++)q[i]=nq[i];
sov(l,mid),sov(mid+1,r);
}
int main()
{
scanf("%d",&n);
while(scanf("%d",&jd)&&jd^3)
{
if(jd==1){int x,y,a;scanf("%d%d%d",&x,&y,&a);q[++tot].opt=1,Q.x=x,Q.y=y,Q.A=a,Q.no=tot;}
else
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
q[++tot].opt=2,Q.x=x1-1,Q.y=y1-1,Q.A=1,Q.no=tot,Q.belong=++T;
q[++tot].opt=2,Q.x=x1-1,Q.y=y2,Q.A=-1,Q.no=tot,Q.belong=T;
q[++tot].opt=2,Q.x=x2,Q.y=y1-1,Q.A=-1,Q.no=tot,Q.belong=T;
q[++tot].opt=2,Q.x=x2,Q.y=y2,Q.A=1,Q.no=tot,Q.belong=T;
}
}
sort(q+1,q+1+tot,cmp);
sov(1,tot);
for(int i=1;i<=T;i++)printf("%d\n",ans[i]);
}