[文章目录]
Description
给出含n个数的序列，给出m次询问，每次询问区间[l,r]中第k大的数是什么。n<=100000,m<=50000
主席树求区间第k大值。
主席树，是一种维护前缀区间中各种值出现次数的权值线段树。
考虑先将数离散化。然后对于每个前缀维护每个数出现的次数。发现[1,i]区间的线段树与[1,i+1]区间的线段树只在点hash_w[i]不同，大部分节点不变，于是为了节省空间，直接将这个seg与前面节点相同的位置放上前面的节点。
根据每个节点到根的路径长度可知，开了至多logn个新节点。所以空间复杂度(但好像开的太满会RE)。
对于每个询问，调用1~r,1~l-1的权值线段树，每个节点[a,b]进行作差，差的值即为数a~b中在区间[l,r]出现的次数。那么一直递归求解直到到达叶子节点。
预处理时间复杂度O()，询问复杂度O()。
代码难度还可以吧。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
using namespace std;
int n,m,root[N],w[N],b[N],c[N],tot,cnt;
struct seg
{
int l,r,sum;
}tre[N*20];
int hash(int x)
{
int mid,l=1,r=tot+1;
while(l<r)
{
mid=l+r>>1;
if(c[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
void updata(int l,int r,int &x,int y,int z)
{
tre[++cnt]=tre[y]; tre[cnt].sum++; x=cnt;
if(l==r) return ;
int mid=l+r>>1;
if(z<=mid) updata(l,mid,tre[x].l,tre[y].l,z);
else updata(mid+1,r,tre[x].r,tre[y].r,z);
}
int query(int l,int r,int x,int y,int z)
{
if(l==r) return r;
int mid=l+r>>1,tmp=tre[tre[y].l].sum-tre[tre[x].l].sum;
if(tmp>=z) query(l,mid,tre[x].l,tre[y].l,z);
else query(mid+1,r,tre[x].r,tre[y].r,z-tmp);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {scanf("%d",w+i);b[i]=w[i];}
sort(b+1,b+n+1); c[++tot]=b[1];
for(int i=2;i<=n;i++) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(int i=1;i<=n;i++) updata(1,tot,root[i],root[i-1],hash(w[i]));
int l,r,k;
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",c[query(1,tot,root[l-1],root[r],k)]);
}
return 0;
}