在一个长度为$N$的数列$a[]$中,$M$次询问区间$[l,r]$中第$k$小的数。即静态区间第$k$小。

$1\leq N,M \leq 2*10^5,|a_i|\leq 10^9$


↑可持久化数组(可持久化基础)

静态主席树是基于权值线段树完成的。我们可以建立$n$棵权值线段树,第$i$棵线段树中,区间$[x,y]$的权值记录的是$[1,i]$中数值的出现次数。

那么有一个很显然的结论,如果我们需要求区间$[x,y]$中$[l,r]$的出现次数,只需要用第$r$棵线段树的$[l,r]$部分减去第$l-1$棵线段树的,其实就是一个简单的前缀和思想。

具体代码实现结合注释看看吧。注意值域较大的时候要记得离散化。

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2e5+10;
struct node{int l,r,w;}t[N*20];
struct ipt{int num,id;}q[N];
int a[N],bk[N];//a:离散化后 bk:离散化前 
bool cmp(ipt a,ipt b){return a.num<b.num;}
int lcnt=1,cnt,rt[N];
//cnt用于动态开点,rt[i]存第i棵线段树的根节点编号,lcnt用于离散化后的数值 
void init(int n)//离散化 
{
    a[q[1].id]=lcnt,bk[lcnt]=q[1].num;
    for(int i=1;i<=n;i++)
    {
        if(q[i].num!=q[i-1].num)lcnt++;
        a[q[i].id]=lcnt,bk[lcnt]=q[i].num;//注意到这里可能多次给bk[lcnt](同样的lcnt)赋值,但是不会影响最终的答案
        //原因是查询区间第k大的下标之后不管是哪一个离散化后的数都可以查询到同一个原数 
    }
}
inline int read()//快读 
{
   int x=0,f=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
   return x*f;
}
int build(int l,int r)
{
    ri m;
    int k=++cnt;
    if(l!=r)
    {
        m=(l+r)>>1;
        t[k].l=build(l,m);
        t[k].r=build(m+1,r); 
    }
    return k;
}//建树只完成开点,不赋值 
int add(int u,int l,int r,int x)
{
    int k=++cnt;
    t[k].w=t[u].w+1;
    //点数喜+1 
    t[k].l=t[u].l,t[k].r=t[u].r;//初始连向u版本的左右儿子 
    if(l!=r)
    {
        ri m=(l+r)>>1;
        if(x<=m)t[k].l=add(t[k].l,l,m,x);
        else t[k].r=add(t[k].r,m+1,r,x);
        //受到影响的区间重新动态开点 
    }
    return k;
    //最后返回新加入的节点编号,整体返回的就是新树根节点 
}
int ask(int u,int v,int l,int r,int x)
{
    if(l==r)return l;
    int tmp=t[t[v].l].w-t[t[u].l].w;
    //两者相减就是区间[x,y]中[u+1,v]出现次数
    int m=(l+r)>>1;
    //如果在[x,y]范围内,[u+1,v]出现了超过k次,那么其中的第k小肯定超过了mid(y-x+1肯定是>=k的),所以在右儿子边 
    //反之,如果出现了小于或等于k次,就走左儿子边
    //特殊的,如果走了右儿子边,实际求的就是右儿子中(k-[左儿子中区间出现的次数])小的数字,所以传下去的是x-tmp
    //当然,如果走的是左儿子,那么没有变化,还是求第k小即可 
    if(x<=tmp)return ask(t[u].l,t[v].l,l,m,x);
    else return ask(t[u].r,t[v].r,m+1,r,x-tmp);
    //分别表示向左右儿子走 
}
int main()
{
    //第i棵权值线段树中区间[x,y]记录区间[x,y]中[1,i]值出现的次数 
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        q[i].num=read(),q[i].id=i;
    sort(q+1,q+1+n,cmp);
    init(n);//把输入的n个数通过离散化放到a[1,lcnt]范围内 
    rt[0]=build(1,n);//建立范围[1,n]的空树 
    for(int i=1;i<=n;i++)
        rt[i]=add(rt[i-1],1,lcnt,a[i]);//挨着把新的点加进去,注意加的是离散化后的a数组 
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read(),k=read();
        printf("%d\n",bk[ask(rt[l-1],rt[r],1,lcnt,k)]);//查询先通过ask找到[l,r]区间第k小在离散化后的下标,然后输出原数 
    }
    return 0;
}
最后修改:2020 年 09 月 27 日 08 : 28 PM