一道毒瘤的 主席树套 $\texttt{k-D Tree}$ 题，或者 暴力分块 的简单题。

题目链接：Luogu P4848/LibreOJ 6016。

题目

题目描述

具体说来，蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇 Aleph 在矩形区域 $x_1\leq x\leq x_2,y_1\leq y\leq y_2$ 中，崂山白花蛇草水瓶数第 $k$ 多的是多少。为了避免麻烦，蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻 Bob 想为难一下神犇 Aleph，希望他能在每次询问时立刻回答出答案。

神犇 Aleph 不屑于做这种问题，所以把这个问题交给了你。

数据范围

时空限制

题解

本题有多种写法。

写法一

不保证能过的奇怪写法（数据过水）。

暴力分块，开两个数组，一大一小，小的大小约为 $\sqrt{q}+1$。

每次加点往小的数组里面用插入排序的方法加，按 $v$ 排列，超过大小后按照归并排序的方法合并两个数组。

查询时按照归并的方法查询。

期望时间复杂度为 $\Theta(q\sqrt{q}+q^2)$。实际开 O2 优化能过（数据太水了）。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define getcharead()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getcharead();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getcharead();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getcharead();
    return f?-res:res;
}

const int MAXQ=100000+5;

struct Querys{
    int x,y,v;
    inline Querys(reg int x=0,reg int y=0,reg int v=0):x(x),y(y),v(v){
        return;
    }
};

int n,Q;
Querys big[MAXQ],small[MAXQ];

inline bool in(const Querys& Q,reg int x1,reg int x2,reg int y1,reg int y2){
    return x1<=Q.x&&Q.x<=x2&&y1<=Q.y&&Q.y<=y2;
}

int main(void){
    n=read(),Q=read();
    reg int cnt1=0,cnt2=0;
    reg int lastans=0;
    reg int BLOCK=sqrt(n)+1;
    while(Q--){
        static int type;
        type=read();
        if(type==1){
            static int x,y,v;
            x=read(),y=read(),v=read();
            x^=lastans,y^=lastans,v^=lastans;
            reg int ptr=0;
            for(ptr=cnt2;ptr&&small[ptr].v>v;--ptr)
                small[ptr+1]=small[ptr];
            small[ptr+1]=Querys(x,y,v);
            ++cnt2;
            if(cnt2>=BLOCK){
                static Querys temp[MAXQ];
                reg int i=cnt1,j=cnt2,k=cnt1+cnt2;
                while(i&&j){
                    if(big[i].v>small[j].v)
                        temp[k--]=big[i--];
                    else
                        temp[k--]=small[j--];
                }
                while(i)
                    temp[k--]=big[i--];
                while(j)
                    temp[k--]=small[j--];
                for(reg int i=1;i<=cnt1+cnt2;++i)
                    big[i]=temp[i];
                cnt1=cnt1+cnt2;
                cnt2=0;
            }
        }
        if(type==2){
            static int x1,y1,x2,y2,k;
            x1=read(),y1=read(),x2=read(),y2=read(),k=read();
            x1^=lastans,y1^=lastans,x2^=lastans,y2^=lastans,k^=lastans;
            if(k>cnt1+cnt2){
                puts("NAIVE!ORZzyz.");
                lastans=0;
                continue;
            }
            reg int i=cnt1,j=cnt2;
            while(i&&j&&k){
                if(big[i].v>small[j].v){
                    if(in(big[i],x1,x2,y1,y2))
                        --k;
                    if(k==0){
                        printf("%d\n",lastans=big[i].v);
                        break;
                    }
                    --i;
                }
                else{
                    if(in(small[j],x1,x2,y1,y2))
                        --k;
                    if(k==0){
                        printf("%d\n",lastans=small[j].v);
                        break;
                    }
                    --j;
                }
            }
            while(i&&k){
                if(in(big[i],x1,x2,y1,y2))
                    --k;
                if(k==0){
                    printf("%d\n",lastans=big[i].v);
                    break;
                }
                --i;
            }
            while(j&&k){
                if(in(small[j],x1,x2,y1,y2))
                    --k;
                if(k==0){
                    printf("%d\n",lastans=small[j].v);
                    break;
                }
                --j;
            }
            if(k){
                puts("NAIVE!ORZzyz.");
                lastans=0;
            }
        }
    }
    return 0;
}

写法二

思路

首先观察到二维平面，考虑使用 $\texttt{k-D Tree}$。

其次观察到第 $k$ 大，考虑 主席树。

于是决定使用 主席树套 $\texttt{k-D Tree}$ 来解决问题。相当于每个结点上开一个 $\texttt{k-D Tree}$。动态插入 + 替罪羊树式重构，查询时可以这么做：

1. 确定一个 $t$；
2. 求 $v$ 大于等于 $t$ 且在 查询范围内的点的个数 （用 $\texttt{k-D Tree}$）；
3. 如果个数大于 $k$，增加 $t$，否则减小 $t$。
4. 最后得到的 $t$ 就是答案。二分 $t$ 即可，最终的时间复杂度是 $\Theta(q\log_2v\log_2q)$，比较优秀。

代码

代码比较长，并且这道题目时间比较松（$3\text{s}$比较长），推荐管理员卡到 $1.5\text{s}$，这道题目也可以卡一卡常数。

卡常数

1. 写快读，因为本题数字都是正数（好像没有 $0$），所以不需要考虑符号；
2. 不要写快速输出，那个东西慢的很；
3. $\texttt{k-D Tree}$ 里面不要用很多数组，要写成结构体的形式，不然很慢；
4. x=max(x,y) 全部改成 cMax(x,y) 这样的形式，其中有宏定义#define cMax(x,y) ( (x) < (y) ? (x) = (y) : (0) )；
5. 开 O2 优化。

下面就是代码了。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 1e9
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=100000+5;
const double alpha=0.75;

const int MAXSIZE=MAXN*20;

int n,K;
int X[2];
int _Max[2],_Min[2];

namespace SegmentTree{
    #define mid ( ( (l) + (r) ) >> 1 )
    int lastans;
    namespace kD_Tree{
        #define cMax(x,y) ( (x) < (y) ? (x) = (y) : (0) )
        #define cMin(x,y) ( (x) > (y) ? (x) = (y) : (0) )
        int cnt;
        #define val(x,y) T[x].val[y]
        #define Max(x,y) T[x].Max[y]
        #define Min(x,y) T[x].Min[y]
        #define lson(x) T[x].lson
        #define rson(x) T[x].rson
        #define size(x) T[x].size
        struct Node{
            int size;
            int lson,rson;
            int Max[2],Min[2];
            int val[2];
        }T[MAXSIZE];
        int WD,p[MAXN];
        inline bool cmp(reg int a,reg int b){
            return val(a,WD)<val(b,WD);
        }
        inline void pushup(reg int k){
            reg int l=lson(k),r=rson(k);
            if(l)
                cMax(Max(k,0),Max(l,0)),cMax(Max(k,1),Max(l,1)),cMin(Min(k,0),Min(l,0)),cMin(Min(k,1),Min(l,1));
            if(r)
                cMax(Max(k,0),Max(r,0)),cMax(Max(k,1),Max(r,1)),cMin(Min(k,0),Min(r,0)),cMin(Min(k,1),Min(r,1));
            size(k)=size(l)+size(r)+1;
            return;
        }
        inline void flat(reg int k){
            if(lson(k)) 
                flat(lson(k));
            p[++cnt]=k;
            if(rson(k))
                flat(rson(k));
            return;
        }
        int buf[MAXN];
        inline int Build(reg int l,reg int r,reg int wd){
            if(l>r)
                return 0;
            WD=wd;
            std::nth_element(p+l,p+mid,p+r+1,cmp);
            reg int k=p[mid];
            Max(k,0)=Min(k,0)=val(k,0),Max(k,1)=Min(k,1)=val(k,1);
            lson(k)=Build(l,mid-1,wd^1),rson(k)=Build(mid+1,r,wd^1);
            pushup(k);
            return k;
        }
        inline void Insert(reg int& root,reg int c){
            if(!root){
                root=c;
                return;
            }
            reg int top=0;
            for(reg int wd=0,x=root;;wd^=1){
                buf[++top]=x;
                cMax(Max(x,0),Max(c,0)),cMax(Max(x,1),Max(c,1)),cMin(Min(x,0),Min(c,0)),cMin(Min(x,1),Min(c,1));
                ++size(x);
                if(val(c,wd)<val(x,wd))
                    if(!lson(x)){
                        lson(x)=c;
                        break;
                    }
                else
                    x=lson(x);
                else
                    if(!rson(x)){
                        rson(x)=c;
                        break;
                    }
                else
                    x=rson(x);
            }
            buf[++top]=c;
            while(size(lson(c))<alpha*size(c)&&size(rson(c))<alpha*size(c))
                c=buf[--top];
            if(!c)
                return;
            if(c==root){
                cnt=0;
                flat(root);
                root=Build(1,cnt,0);
                cnt=0;
                return;
            }
            reg int fa=buf[--top],crt;
            flat(c);
            crt=Build(1,cnt,top&1);
            cnt=0;
            if(lson(fa)==c)
                lson(fa)=crt;
            else
                rson(fa)=crt;
        }
        inline void Query(reg int x){
            if(!x||Max(x,0)<_Min[0]||Max(x,1)<_Min[1]||Min(x,0)>_Max[0]||Min(x,1)>_Max[1]||lastans>=K)
                return;
            if(_Min[0]<=Min(x,0)&&Max(x,0)<=_Max[0]&&_Min[1]<=Min(x,1)&&Max(x,1)<=_Max[1]){
                lastans+=size(x);
                return;
            }
            if(_Min[0]<=val(x,0)&&val(x,0)<=_Max[0]&&_Min[1]<=val(x,1)&&val(x,1)<=_Max[1])
                ++lastans;
            Query(lson(x));
            Query(rson(x));
            return;
        }
        #undef lson
        #undef rson
    }
    using kD_Tree::T;
    int ct,tot=1;
    int root[MAXSIZE],lson[MAXSIZE],rson[MAXSIZE];
    inline void Update(void){
        reg bool flag=true;
        reg int ID=1;
        reg int l=1,r=INF;
        while(true){
            if(flag){
                ++ct;
                Max(ct,0)=Min(ct,0)=val(ct,0)=X[0],Max(ct,1)=Min(ct,1)=val(ct,1)=X[1];
                size(ct)=1;
                kD_Tree::Insert(root[ID],ct);
            }
            if(l==r)
                return;
            if(K<=mid){
                if(!lson[ID])
                    lson[ID]=++tot;
                ID=lson[ID],r=mid;
                flag=false;
            }
            else{
                if(!rson[ID])
                    rson[ID]=++tot;
                ID=rson[ID],l=mid+1;
                flag=true;
            }
        }
        return;
    }
    inline void Query(void){
        lastans=0;
        kD_Tree::Query(root[1]);
        if(lastans<K){
            puts("NAIVE!ORZzyz.");
            lastans=0;
            return;
        }
        reg int ID=1,l=1,r=INF;
        while(l<r){
            lastans=0;
            kD_Tree::Query(root[rson[ID]]);
            if(K<=lastans)
                ID=rson[ID],l=mid+1;
            else
                K-=lastans,ID=lson[ID],r=mid;
        }
        printf("%d\n",lastans=l);
        return;
    }
}

using SegmentTree::lastans;

int main(void){
    reg int cnt=0;
    read(),n=read();
    reg int type,x1,y1,x2,y2;
    for(reg int i=1;i<=n;++i)
        switch(type=read()){
            case 1:{
                x1=read()^lastans,y1=read()^lastans,K=read()^lastans;
                X[0]=x1,X[1]=y1;
                SegmentTree::Update();
                ++cnt;
                break;
            }
            case 2:{
                x1=read()^lastans,y1=read()^lastans,x2=read()^lastans,y2=read()^lastans,K=read()^lastans;
                _Min[0]=x1,_Min[1]=y1,_Max[0]=x2,_Max[1]=y2;
                SegmentTree::Query();
                break;
            }
            default:break;
        }
    return 0;
}