记录编号	464281	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.481 s
提交时间	2017-10-25 15:55:06	内存使用	47.62 MiB

# include "iostream"
# include "stdio.h"
# include "algorithm"
# include "string.h"
# include "math.h"
# define maxn 800005
using namespace std;
# define lowbit(x) (x&-x)
struct node{
       int id,x,y,val,opt,qes;
       bool operator <(node A)const{
           if(x==A.x&&y==A.y) return opt<A.opt;
           return x==A.x?y<A.y:x<A.x;
       }
}e[maxn],s[maxn];

int n,cnt,ans,ANS[maxn];
int ai,opt,a,b,c,d;
int sum[2000005];

void update(int i,int x){
     for(;i<=n;i+=lowbit(i))
         sum[i]+=x;
}
int SUM(int x){
    int ret=0;
    for(;x;x-=lowbit(x)) ret+=sum[x];
    return ret;
}

void CDQ(int l,int r){
     if(l==r) return;
     int mid=(l+r)/2,s1=l,s2=mid+1;
     for(int i=l;i<=r;i++){
         if(e[i].id<=mid&&e[i].opt==1) {update(e[i].y,e[i].val);}
         if(e[i].id>mid&&e[i].opt==2){
             //cout<<" "<<SUM(e[i].y)*e[i].val<<" ";
            ANS[e[i].qes]+=SUM(e[i].y)*e[i].val;
            //cout<<SUM(e[i].y)<<" ";
         }
     }
     for(int i=l;i<=r;i++) if(e[i].id<=mid&&e[i].opt==1) update(e[i].y,-e[i].val);
     for(int i=l;i<=r;i++){
         if(e[i].id>mid) s[s2++]=e[i];
         else s[s1++]=e[i];
     }
     for(int i=l;i<=r;i++) e[i]=s[i];
     CDQ(l,mid);CDQ(mid+1,r);
}
int main(){
    freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    scanf("%d%d",&ai,&n);
    while(true){
          scanf("%d",&opt);
          if(opt==3) break;
          if(opt==1){
             ++cnt;e[cnt].opt=1;e[cnt].id=cnt;
             scanf("%d%d%d",&e[cnt].x,&e[cnt].y,&e[cnt].val);
          }
          if(opt==2){
             scanf("%d%d%d%d",&a,&b,&c,&d);ans++;
             ++cnt;e[cnt].qes=ans,e[cnt].opt=2,e[cnt].id=cnt;e[cnt].x=c,e[cnt].y=d,e[cnt].val=1;
             ++cnt;e[cnt].qes=ans,e[cnt].opt=2,e[cnt].id=cnt;e[cnt].x=a-1,e[cnt].y=b-1,e[cnt].val=1;
             ++cnt;e[cnt].qes=ans,e[cnt].opt=2,e[cnt].id=cnt;e[cnt].x=a-1,e[cnt].y=d,e[cnt].val=-1;
             ++cnt;e[cnt].qes=ans,e[cnt].opt=2,e[cnt].id=cnt;e[cnt].x=c,e[cnt].y=b-1,e[cnt].val=-1;
          }
    }sort(e+1,e+1+cnt);
    CDQ(1,cnt);
    for(int i=1;i<=ans;i++) printf("%d\n",ANS[i]);
}
/*
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

3 5
*/