习题 ：静态区间第K大（主席树&动态开点）

题目

传送门

思路

很经典的一道主席树入门题
这个区间是不是静态的其实没有多大影响
如果不考虑空间的话
对于前i个数建一棵权值线段树
再将两颗树相减即可得到区间中有哪些数
且在相减的过程中我们就能将第k大的数拿到
主席树就呼之欲出了
注意一些细节，相减的两颗树应是\(r\)和\(l-1\)
同时，
要相同的数要占据排名
比如
2 2 1当中1是第3大的，不是第2大的

另外
数的范围很大
需要将其离散化，或者动态开点
笔者的代码为动态开点

代码

#include<iostream>
using namespace std;
struct node
{
    int s;
    int l;
    int r;
    int lson;
    int rson;
}tre[300005<<5];
int n,m;
int tot;
int root[200005];
int change(int u,int k)
{
    int now=++tot;
    tre[now].l=tre[u].l;
    tre[now].r=tre[u].r;
    if(tre[now].l==tre[now].r)
    {
        tre[now].s=tre[u].s+1;
        return now;
    }
    int mid=(tre[now].l+tre[now].r)>>1;
    if(tre[now].l<=k&&k<=mid)
    {
        if(tre[u].lson==0)
        {
            tre[u].lson=++tot;
            tre[tot].l=tre[u].l;
            tre[tot].r=mid;
        }
        tre[now].lson=change(tre[u].lson,k);
        tre[now].rson=tre[u].rson;
    }
    else
    {
        if(tre[u].rson==0)
        {
            tre[u].rson=++tot;
            tre[tot].l=mid+1;
            tre[tot].r=tre[u].r;
        }
        tre[now].lson=tre[u].lson;
        tre[now].rson=change(tre[u].rson,k);
    }
    tre[now].s=tre[tre[now].lson].s+tre[tre[now].rson].s;
    return now;
}
int solve(int u,int v,int k)
{
    if(tre[v].l==tre[v].r)
        return tre[v].l;
    int t=tre[tre[v].lson].s-tre[tre[u].lson].s;
    if(t>=k)
        return solve(tre[u].lson,tre[v].lson,k);
    else
        return solve(tre[u].rson,tre[v].rson,k-t);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    tre[++tot].l=-1e9;
    tre[tot].r=1e9;
    root[0]=tot;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        root[i]=change(root[i-1],x);
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<solve(root[l-1],root[r],k)<<endl;
    }
    return 0;
}