题意:链接

**方法:**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]);

}