记录编号	317635	评测结果	AAAAAAAAAA
题目名称	蝗灾	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.898 s
提交时间	2016-10-08 12:07:16	内存使用	15.17 MiB

#include<cstdio>
struct Q{
    int x1,y1,x2,num;
    Q(){}
    Q(int a,int b,int c,int d){
        x1=a;y1=b;x2=c;num=d;
    }
    bool operator <(const Q &B)const{
        return y1<B.y1;
    }
}lst[400005],buf[400005];
void merge(int l,int r){
    int mid=(l+r)>>1;
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(lst[i]<lst[j]){
            buf[k]=lst[i];++i;++k;
        }else{
            buf[k]=buf[j];++j;++k;
        }
    }
    while(i<=mid){
        buf[k]=lst[i];++i;++k;
    }
    while(j<=r){
        buf[k]=buf[j];++j;++k;
    }
    for(i=l;i<=r;++i)lst[i]=buf[i];
}
int c[500050];
inline int lowbit(int x){
    return x&(-x);
}
int sum(int x){//printf("S%d\n",x);
    int ans=0;
    for(;x;x-=lowbit(x))ans+=c[x];
    return ans;
}
void add(int x,int w){//printf("A");
    for(;x<500050;x+=lowbit(x))c[x]+=w;
}
int ans[200005];
void solve(int l,int r){//printf("%d %d\n",l,r);
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    merge(l,mid);merge(mid+1,r);//printf("-%d %d\n",l,r);
    int pt=l;
    for(int i=mid+1;i<=r;++i){
        while(pt<=mid&&lst[pt].y1<=lst[i].y1){
            if(lst[pt].num==0){
                add(lst[pt].x1,lst[pt].x2);
            }
            pt++;
        }
        if(lst[i].num>0){
            ans[lst[i].num]+=sum(lst[i].x1)-sum(lst[i].x2-1);
        }else if(lst[i].num<0){
            ans[-lst[i].num]-=sum(lst[i].x1)-sum(lst[i].x2-1);
        }
    }
    for(int i=l;i<=mid&&lst[i].y1<=lst[r].y1;++i){
        if(lst[i].num==0)add(lst[i].x1,-lst[i].x2);
    }
}
int main(){
    freopen("locust.in","r",stdin);
    freopen("locust.out","w",stdout);
    int w;scanf("%d",&w);
    int n;scanf("%d",&n);
    int typ,tot=0,qs=0;
    int x1,y1,x2,y2;
    for(int i=1;i<=n;++i){
        scanf("%d",&typ);
        if(typ==1){
            scanf("%d%d%d",&x1,&y1,&x2);
            lst[++tot]=Q(x1+1,y1+1,x2,0);
        }else{
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            qs++;
            lst[++tot]=Q(x2+1,y2+1,x1+1,qs);
            lst[++tot]=Q(x2+1,y1,x1+1,-qs);
        }
    }
    solve(1,tot);
    for(int i=1;i<=qs;++i){
        printf("%d\n",ans[i]);
    }//while(1);
    fclose(stdin);fclose(stdout);
    return 0;
}