GMOJ 3304 Theresa与数据结构 题解

我爱死这个出题人了

简要の题意

裸的四维偏序。

\(n\le 100000\)

思路

众所周知，这题显然可以写 \(O(n\log^3n)\) 的算法。

比如树套树套树，或者 cdq 分治套树套树，或者 cdq 分治套 cdq 分治套树……

除非真的是 KDT 的题目，不然在不卡空间的情况下 KDT 真跑不过这类东西

那么我们算一下：

\(n\log^3n=100000\times\log^3 100000\thickapprox 458226982.3989921344\)

MMP 出题人这 NM 怎么过啊

本着多少能拿分的想法写了 cdq 分治套树状数组套线段树，调了 4 个小时，事实证明能拿暴力分。

WDNMD

然后据说 KDT 并不会更短或者更容易过去并且我已经写了接近 5K 了，决定改成 cdq 分治套 cdq 分治套树状数组。

又调了 2h 过了，开 O2 可以跑进一秒。

然后又卡了卡常，不开 O 也可以跑进一秒。

CODE

剩下的大部分的细节丢进了注释，应该还算详细。

建议丢进 Astyle 或者 Clang Format 之后食用。

#pragma GCC optimize(2)
#include
#include
#include
#define reg register
#define ll long long
using namespace std;
const int N=105000,FSIZE=1<<22,NN=N+N+N;
int cnt=1,cntx,cnty,cntz,st[N],mx,my,mz,*lsx[NN],*lsy[NN],*lsz[NN],*tmp[NN];
struct ques{
    int mode,x,yl,yr,dy,zl,zr,ans;
}e[NN],*dvd[NN],*dl[NN],*dr[NN],p[NN],*d2[NN],*l2[NN],*r2[NN],*num[NN];
struct SToFT{    //这里曾经是 Segment Tree On Fenwick Tree 的意思
    #define lowb(x)((x)&-(x))
    int a[NN];
    void modify(reg int x,reg int c){
        for(;x<=mz;x+=lowb(x)) a[x]+=c;
    }
    int sum(reg int x){
        reg int re=0;
        for(;x;x-=lowb(x)) re+=a[x];
        return(re);
    }
    int query(reg int zl,reg int zr){
        return(sum(zr)-sum(zl-1));
    }
}t;
char BuF[FSIZE],*InF=BuF;
int read(){   //读入的一部分
    reg int x=0;
    for(;47>*InF||*InF>58;++InF);
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    return(x);
}
void sort(reg int **ls,reg int cnt,reg int t,reg int z){
    //基数排序，不知道为什么松式排序反而慢一些
    int w[65536];
    memset(w,0,sizeof(w));
    for(reg int **i=ls,**r=ls+cnt;i>z]);
    for(reg int *i=w,*r=w+65535;i=ls;--i) tmp[--w[(**i&t)>>z]]=*i;
    for(reg int i=0;i>1,cl=0,cr=0;
        for(reg int i=ql;i<=qr;++i){
            ques &now=*d2[i];    //使用指针作为操作顺序的存放方式，避免结构体复制影响效率
            if(now.mode==1){
                if(l==r||now.yl>mid){    //l==r 时全部合法
                    now.ans+=t.query(now.zl,now.zr);
                }
            }else if(l==r||now.yl<=mid){
                t.modify(now.zl,now.mode?-1:1);
            }
            if(now.yl>mid) r2[cr++]=&now;
            else l2[cl++]=&now;
        }
        for(reg int i=ql;i<=qr;++i){
            //把树状数组的更改还原，使用时间戳清空也是可以的，但略慢（查询太多）
            ques &now=*d2[i];
            if(now.mode!=1&&(l==r||now.yl<=mid)){
                t.modify(now.zl,now.mode?1:-1);
            }
        }
        for(reg int i=ql;i>1,cl=0,cr=0,cnt=0;
        for(reg int i=ql;i<=qr;++i){
            ques &now=*dvd[i];    //使用指针作为操作顺序的存放方式，避免结构体复制影响效率
            if(now.mode==1){
                if(l==r||now.x>mid){
                    ++cnt;d2[cnt]=&(p[cnt]=now);p[cnt].ans=0;p[cnt].yl=p[cnt].dy;
                    num[cnt]=&now;
                    ++cnt;d2[cnt]=&(p[cnt]=now);p[cnt].ans=0;p[cnt].yl=p[cnt].yr;
                    //创建两个二次询问，容斥出一次查询，ans 注意清空（虽然不清好像也没问题）
                    //注意最后的细微差别
                }
            }else if(l==r||now.x<=mid){
                p[++cnt]=now;
                d2[cnt]=&p[cnt];
            }
            if(now.x>mid) dr[cr++]=&now;
            else dl[cl++]=&now;
        }
        cdq2(1,my,1,cnt);  //二次 CDQ 出对于在 mid 右的询问包含在几个 mid 左的点
        for(int i=1;i<=cnt;++i){    //找到每个二次询问，把对应的一次询问的答案更新
            if(p[i].mode==1){
                num[i]->ans+=p[i+1].ans-p[i].ans;
                ++i;
            }
        }
        for(reg int i=ql;i32;++InF);   //读入的一部分
        }else{
            read(e[cnt]);
            if(ch=='Q'){
                r=read();
                e[cnt].dy=e[cnt].yl-1;    //求出 y-1 作为容斥的一部分（离散化用）
                e[cnt].yr=e[cnt].yl+r;    //求出 y+r 作为容斥的一部分（离散化用）
                e[cnt].zr=e[cnt].zl+r;    //求出 z+r 作为容斥的一部分（离散化用）
                e[cnt].mode=1;
                e[cnt+1]=e[cnt];
                e[cnt+1].x+=r;    //求出 x+r 作为容斥的一部分（离散化用）
                --e[cnt].x;    //求出 x-1 作为容斥的一部分（离散化用）
                lsy[cnty++]=&e[cnt].dy;lsy[cnty++]=&e[cnt+1].dy;
                //将 cnt 与 cnt+1 的 y-1 单独放入 y 的离散化数组
                push(e[cnt].x,e[cnt].yl,e[cnt].zl);
                //将 cnt 的 x yl zl 分别放入离散化数组
                lsy[cnty++]=&e[cnt].yr;lsz[cntz++]=&e[cnt].zr;
                //将 cnt 的 y+r 和 z+r 单独放入离散化数组，cnt+1 的等一会处理
                ++cnt;    //注意这里 +1
            }else{
                st[++st[0]]=cnt;
            }
        }
        push(e[cnt].x,e[cnt].yl,e[cnt].zl);
        //将 cnt 的 x yl zl 分别放入离散化数组
        //注意在 if 外，这样可以把 CANCEL 操作也放入
    }
    lsh(lsx,mx,cntx);lsh(lsy,my,cnty);lsh(lsz,mz,cntz);
    //离散化
    for(reg int i=1;i