题解 SP3946 【MKTHNUM - K-th Number】

· · 题解

第一步 读题

题目我就不放了（其实是翻译人的 \LaTeX 有点恶心）。

给一个简化版的题目：给定一个长度为 n 的序列，然后有 m 次询问，每次询问在 \left[l,r\right] 区间内第 k 小的数。

第二步 思路

要我们求 \left[l,r\right] 中的第 k 小数。我们有一下几点思路：

首先是暴力枚举，对于每一次询问直接枚举 l,r，记录。加上预处理，时间复杂度最优是 O\left(nm\right)。由于 n\le10^5，m\le5\times 10^3，所以会超时，舍去。

然后我们要考虑优化。我们发现这道题让我们求区间内第 k 大数，普通线段树显然做不了。。我看了一圈题解，大概有树套树、分块、划分树、归并树等等，但是还是可持久化线段树（主席树）居多。

我这个蒟蒻只会可持久化线段树，那就讲这个吧。初学者可以来看这篇博文，蒟蒻会详细讲解可持久化线段树。

第一部分 基础介绍&存储插入

由于可持久化线段树的创造者的名字缩写为 HJT，与我们敬爱的前国家主席的名字相同，故得主席树知名。算法主要思想就是保存多个历史版本的线段树。但是怎么保存呢？每一次修改都保存？空间不就炸了吗......

但是我们仔细想想，发现每次更改的仅仅是叶子节点到根节点这一条链上的结点。也就是只更改了 \log_2 n 个结点，形成了一条链。这样与每改变一次就建一个树相比空间减少了很多。

但是我们要特别注意主席树不能使用堆式存储法，就是说不能用x\times2，x\times2+1来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。 如果理解了上面的更改以后大家应该都可以理解。

这样我们可以在每次插入的时候进行一次更改存储。

第二部分 查找原理

我们已经存好了每一个版本。现在要求出 \left[1,r\right] 区间内的第 k 小值，我们就可以找到插入 r 的版本，然后用普通权值线段树查询答案就可以了。

那我们现在把范围扩展到 \left[l,r\right] 区间内第 k 小的值，我们怎么办呢？

想一下，我们发现可以应用 前缀和。我们用 \left[1,r\right] 的信息减去 \left[1,l-1\right] 的信息就可以求出 \left[l,r\right] 的信息。运用前缀和后我们也可以在 O\left(log_2n\right) 的时间内做单次查询。

第三部分 空间

这一部分真的要单出来列。。因为你开空间不能吝啬，不然会爆炸。。我们先分析一下：

首先，我们动态开点，线段树会出现 2\times n-1 个结点。然后我们有 n 次修改，每次最多增加 \lceil log_2n\rceil+1 个结点。由于本题 n \le 10^5，\lceil log_2 10^5\rceil+1\approx18，故总结点数为 2\times 10^5-1+18\times 10^5=2\times 10^6-1 个。那么我们最好还是保守一点，所以我们最好开到 2^5\times10^5。或者再大一点（反正别开小，也别开炸。。）

第三部分 代码

终于到了代码部分了。。。（警告：由于快读较长，建议跳过！）

#include<bits/stdc++.h>//万能头
using namespace std; 
using std::cin;
using std::cout;
using std::endl;
namespace IN{//读入优化，建议跳过
    const int MAX_INPUT = 1000000;
    #define getc() (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
    char buf[MAX_INPUT],*p1,*p2;
    template<typename T>inline bool read(T &x) {
        static std::streambuf *inbuf=cin.rdbuf();
        x=0;
        register int f=0,flag=false;
        register char ch=getc();
        while(!isdigit(ch)){
            if (ch=='-') f=1;
            ch=getc();
        }
        if(isdigit(ch)) x=x*10+ch-'0',ch=getc(),flag=true;
        while(isdigit(ch)) {
            x=x*10+ch-48;
            ch=getc();
        }
        x=f?-x:x;
        return flag;
    }
    template<typename T,typename ...Args>inline bool read(T& a,Args& ...args) {
       return read(a)&&read(args...);
    }
    #undef getc
}

namespace OUT{//输出优化，建议跳过
    template<typename T>inline void put(T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top=0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc('\n');
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc('\n');
    }
    inline void putc(const char ch){
        static std::streambuf *outbuf=cout.rdbuf();
        outbuf->sputc(ch);
    }
    inline void putstr(string s){
        for(register int i=0;i<s.length();i++) putc(s[i]);
    }
    template<typename T>inline void put(const char ch,T x){
        static std::streambuf *outbuf=cout.rdbuf();
        static char stack[21];
        static int top = 0;
        if(x<0){
            outbuf->sputc('-');
            x=-x;
        }
        if(!x){
            outbuf->sputc('0');
            outbuf->sputc(ch);
            return;
        }
        while(x){
            stack[++top]=x%10+'0';
            x/=10;
        }
        while(top){
            outbuf->sputc(stack[top]);
            --top;
        }
        outbuf->sputc(ch);
    }
    template<typename T,typename ...Args> inline void put(T a,Args ...args){
        put(a);put(args...);
    }
    template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
        put(ch,a);put(ch,args...);
    }
}
using IN::read;
using OUT::put;
using OUT::putc;
using OUT::putstr;
//定义一些
#define N (int)2e5+5 
#define int long long
#define mid ((l+r)>>1)
int cnt,n,m,p,a[N],b[N],q[N];//cnt表示结点数，n，m，a读入，还有离散序列
struct CTnode{//结构体
    int s,l,r;//s表示数，
}t[N<<5];//结构体数组
namespace Chairman_Tree{//如果写好多东西放在一起有可能分不清
    inline int build(int l,int r){//这里建树
        int rt=++cnt;//保存结点编号
        t[rt].s=0;//初始化
        if(l<r) t[rt].l=build(l,mid),t[rt].r=build(mid+1,r);//可以建树就继续建树
        return rt;  //返回结点编号
    }
    inline int update(int k,int l,int r,int rt){//k表示旧结点位置
        int u=++cnt;//保存一下
        t[u].l=t[k].l,t[u].r=t[k].r,t[u].s=t[k].s+1;//复制，更改。点数为上一课加1
        if(l<r)//可以更新
            if(rt<=mid) t[u].l=update(t[k].l,l,mid,rt);//左儿子更新
            else t[u].r=update(t[k].r,mid+1,r,rt);//右儿子更新
        return u;
    }
    inline int query(int x,int y,int l,int r,int k){//查询第k小数
        if(l>=r) return l;
        int u=t[t[y].l].s-t[t[x].l].s;//区间减法得到左儿子信息
        if(u>=k) return query(t[x].l,t[y].l,l,mid,k);//在左儿子中
        else return query(t[x].r,t[y].r,mid+1,r,k-u);//在右儿子中
    }
    inline void init(){
        read(n,m);//读入
        for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i];//读入并赋值
        sort(b+1,b+n+1);//这里先搜索
        p=unique(b+1,b+n+1)-b-1;//不重复数字的个数
        q[0]=build(1,p);//简历一颗空树，并赋值
        for(int i=1;i<=n;i++){
            int k=lower_bound(b+1,b+p+1,a[i])-b;//查找第一个大于等于a[i]的数
            q[i]=update(q[i-1],1,p,k);//更新并赋值
        }   
    }
    inline void solve(){//主函数（话说都变味了）
        init();//读入初始化
        for(int i=1,x,y,z;i<=m;i++)//m次查询
            read(x,y,z),put('\n',b[query(q[x-1],q[y],1,p,z)]);//改成b的输出。由于有影响，所以是q[x-1]
    }
}
signed main(signed argc, char const *argv[]){
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Chairman_Tree::solve();//运行solve
    return 0;
}

第四步 其他