严肃 CDQ 题解

笑哭，你们这群 AIGO 抄的题解我还见过，只是怎么比我慢这么多呢？

切入正题，这题一眼 CDQ 分治模板，我知道题解不能这样说但是标签都打了。见到多种操作直接动态转静态，把时间看作一个新的维度然后偏序。一次2操作分4个询问，通过二维差分求出答案。时间这一块不用再排序，直接 CDQ 归并掉 x，然后 BIT 除掉 y.

Hmmm没什么好说的这玩意太板了，更详细的以后创作计划里说。注意坐标要+1避免 BIT 的 add() 报废,ax 和 ay 不用是因为-1抵消了（后面用的都是-1的值，因为差分）。写这题时 CDQ 计算完贡献忘记把左区间剩下的合并了，不写 sort() 的童鞋注意一下。

疑似轻松跑到最优解第一页（？

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define re register
#define enter putchar_unlocked('\n')
int t[2000005],w,cnt,qcnt,ans[10005],op,ax,ay,bx,by;
struct xyl{int x,y,val,id,op;}a[200005],k[200005];
void add(int x,int d){for(;x<=w;x+=x&-x)t[x]+=d;}
int qry(int x){int res=0;for(;x;x^=x&-x)res+=t[x];return res;}
void clr(int x){for(;x<=w&&t[x];x+=x&-x)t[x]=0;}
void cdq(int l,int r){
    if(l==r)return;
    cdq(l,mid),cdq(mid+1,r);
    re int c1=l,cnt=0;
    for(re int c2=mid+1;c2<=r;++c2){
        for(;a[c1].x<=a[c2].x&&c1<=mid;++c1){if(!a[c1].op)add(a[c1].y,a[c1].val);k[++cnt]=a[c1];}
        if(a[c2].op)ans[a[c2].id]+=a[c2].op*qry(a[c2].y);k[++cnt]=a[c2];
    }
    for(;c1<=mid;++c1)k[++cnt]=a[c1];
    for(re int i=l;i<=mid;++i){if(!a[i].op)clr(a[i].y);a[i]=k[i-l+1];}
    for(re int i=mid+1;i<=r;++i)a[i]=k[i-l+1];
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    read(),w=read()+1;
    for(op=read();op^3;op=read()){
        if(op^2)a[++cnt]={read()+1,read()+1,read(),0,0};
        else{
            ax=read(),ay=read(),bx=read()+1,by=read()+1;
            a[++cnt]={bx,by,0,++qcnt,1},a[++cnt]={ax,by,0,qcnt,-1},a[++cnt]={bx,ay,0,qcnt,-1},a[++cnt]={ax,ay,0,qcnt,1};
        }
    }
    cdq(1,cnt);
    for(re int i=1;i<=qcnt;++i)write(ans[i]),enter;
    return 0;
}