题目概述

Kth Query

解题报告

这道题给了我01 Trie的新思路QAQ。

首先我们考虑没有限制的情况，我们对于每个节点 $x$ 维护 $MIN_{x,k}$ 表示 $x$ 子树中第 $k$ 小值的最小值（ $1\le k\le si_x$ ）。记 $ls_x,rs_x$ 为 $x$ 的 $01$ 儿子，$si_x$ 为 $x$ 子树大小，$bit(x)$ 为 $x$ 节点的二进制位，那么：

• $0$ 儿子：$\begin{cases}MIN_{ls_x,k}&k\le si_{ls_x}\\MIN_{rs_x,k-si_{ls_x}}+2^{bit(x)}&k>si_{ls_x}\end{cases}$
• $1$ 儿子：$\begin{cases}MIN_{rs_x,k}&k\le si_{rs_x}\\MIN_{ls_x,k-si_{rs_x}}+2^{bit(x)}&k>si_{rs_x}\end{cases}$

$MIN_{x,k}$ 就是 $01$ 儿子中的最小值。

但是这样复杂度不是起飞了？实际上，每次插入一个数，只会让 $30$ 个节点的 $si$ 增加，也就是说，$MIN$ 数组元素个数为 $O(30n)$ ，因此预处理复杂度为 $O(30n)$ 。

询问时候的 $[L,R]$ 看起来很可怕，实际上 $S$ 只是分三个阶段：

1. 与 $L,R$ 的前若干位相同。
2. 与 $L,R$ 其中一个的前若干位相同。
3. 无限制。

那么，只要处理出 $L,R$ 相同的前几位，然后枚举和 $L$ 或 $R$ 相同的前若干位，之后就可以直接利用 $MIN$ 数组得到答案。

示例程序

#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100000,maxt=maxn*30;

int n,te;
int po=1,son[maxt+5][2],si[maxt+5];vector<int> MIN[maxt+5];

void Insert(int x){
    int p=1;si[p]++;
    for (int i=29;~i;i--){
        int &now=son[p][x>>i&1];
        if (!now) now=++po;
        p=now;si[p]++;
    }
}
void DFS(int x,int d=29){
    int ls=son[x][0],rs=son[x][1];
    if (ls) DFS(ls,d-1);if (rs) DFS(rs,d-1);
    MIN[x].resize(si[x]+1);
    if (!ls && !rs) return;
    for (int i=1;i<=si[x];i++){
        int A=(i<=si[ls]?MIN[ls][i]:MIN[rs][i-si[ls]]+(1<<d));
        int B=(i<=si[rs]?MIN[rs][i]:MIN[ls][i-si[rs]]+(1<<d));
        MIN[x][i]=min(A,B);
    }
}
int main(){
    scanf("%d%d",&n,&te);
    for (int i=1,x;i<=n;i++) scanf("%d",&x),Insert(x);DFS(1);
    for (int t=1;t<=te;t++){
        int L,R,K;scanf("%d%d%d",&L,&R,&K);
        int p=1,st,now=0,ans=2e9;
        for (st=29;~st && (L>>st&1)==(R>>st&1);st--){
            int d=L>>st&1,A=son[p][d],B=son[p][d^1];
            if (K<=si[A]) p=A; else K-=si[A],p=B,now+=1<<st;
        }
        if (st<0) {printf("%d\n",now);continue;}
        int tem[3]={p,K,now};
        for (int i=st;~i;i--){
            int d=R>>i&1,A=son[p][d],B=son[p][d^1];
            if (i<st && d) ans=min(ans,now+(K<=si[B]?MIN[B][K]:MIN[A][K-si[B]]+(1<<i)));
            if (K<=si[A]) p=A; else K-=si[A],p=B,now+=1<<i;
        }
        ans=min(ans,now+MIN[p][K]);
        p=tem[0];K=tem[1];now=tem[2];
        for (int i=st;~i;i--){
            int d=L>>i&1,A=son[p][d],B=son[p][d^1];
            if (i<st && !d) ans=min(ans,now+(K<=si[B]?MIN[B][K]:MIN[A][K-si[B]]+(1<<i)));
            if (K<=si[A]) p=A; else K-=si[A],p=B,now+=1<<i;
        }
        ans=min(ans,now+MIN[p][K]);
        printf("%d\n",ans);
    }
    return 0;
}