对时间的cdq分治 在外部关于x排序即可 分治的时候维护时间 （就是 一开始整个序列时间为1-cnt 那么往左递归的时候 要保证时间为1-mid 以此类推）
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int n,m,S,x,y,x2,y2,z,t[N],op,tim,cnt,cntq,ans[N]; void add(int x,int v){for(;x<=N;x+=x&-x)t[x]+=v;} int qsum(int x){int ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;} struct node { int t,op,x,y,v,flag,id; }s[N],temp[N]; bool cmp(node a,node b) { if(a.x!=b.x)return a.x<b.x; return a.y<b.y||a.y==b.y&&a.id<b.id; } void cdq(int l,int r) { if(l==r)return ;int mid=(l+r)>>1; rep(i,l,r) { if(s[i].t<=mid&&s[i].op==1)add(s[i].y,s[i].v); if(s[i].t>mid&&s[i].op==2)ans[s[i].id]+=s[i].flag*qsum(s[i].y); } rep(i,l,r) if(s[i].t<=mid&&s[i].op==1)add(s[i].y,-s[i].v); int L=l-1,R=mid; rep(i,l,r) { if(s[i].t<=mid)temp[++L]=s[i]; else temp[++R]=s[i]; } rep(i,l,r)s[i]=temp[i]; cdq(l,mid);cdq(mid+1,r); } int main() { scanf("%d%d",&S,&n); while(1) { scanf("%d",&op); if(op==3)break; if(op==1) { scanf("%d%d%d",&x,&y,&z); s[++cnt]=(node){cnt,1,x,y,z}; } else { scanf("%d%d%d%d",&x,&y,&x2,&y2); ans[++cntq]=(y-y+1)*(x2-x+1)*S; s[++cnt]=(node){cnt,2,x-1,y-1,0,1,cntq}; s[++cnt]=(node){cnt,2,x2,y2,0,1,cntq}; s[++cnt]=(node){cnt,2,x-1,y2,0,-1,cntq}; s[++cnt]=(node){cnt,2,x2,y-1,0,-1,cntq}; } } sort(s+1,s+1+cnt,cmp); cdq(1,cnt); rep(i,1,cntq)printf("%d ",ans[i]); return 0; }