题面
具体题目不再叙述，参考洛谷
题目大意，求区间[l,r]中第k大的数
题解
主席树很经典的运用
首先将值离散化之后，构建一颗值域线段树
储存区间和
0版本的线段树是空树
每次在值域上增加1就重构一颗线段树
很显然，任意两颗相邻线段树的值得和差为1
而相同的区间内要么相等要么多1
那么，我们也很容易的可以推出，区间第k大可以通过第r版本和第（l-1）版本的线段树算出来
每次计算左儿子
如果r的左儿子已经比(l-1)的左儿子多出来的和大于k
那么在左儿子查找k大值
否则则在右儿子上查找第(k-val)大值，其中，val是和的差
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
#define MAXN 10000000
#define MAX 500000
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct Node
{
int ch[2];
int l,r;
int val;
}c[MAXN];
int N,M,a[MAX],b[MAX],NN,mm[MAX];
int cnt,Root[MAX];
map<int,int> MM;
void build(int now,int l,int r)
{
++cnt;c[now].l=l;c[now].r=r;
if(l==r)return;
int mid=(l+r)>>1;
c[now].ch[0]=cnt+1;
build(cnt+1,l,mid);
c[now].ch[1]=cnt+1;
build(cnt+1,mid+1,r);
}
void update(int now,int k,int x)
{
++cnt;//int tt=cnt;
c[cnt]=c[now];c[cnt].val+=x;
int l=c[now].l,r=c[now].r;
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid){c[cnt].ch[0]=cnt+1;update(c[now].ch[0],k,x);}
else {c[cnt].ch[1]=cnt+1;update(c[now].ch[1],k,x);}
}
int Query(int now1,int now2,int k)
{
if(c[now1].l==c[now1].r)return c[now1].l;
int rr=c[c[now2].ch[0]].val-c[c[now1].ch[0]].val;
if(rr<k)return Query(c[now1].ch[1],c[now2].ch[1],k-rr);
else return Query(c[now1].ch[0],c[now2].ch[0],k);
}
int main()
{
N=read();M=read();
for(int i=1;i<=N;++i)a[i]=b[i]=read();
sort(&b[1],&b[N+1]);
NN=unique(&b[1],&b[N+1])-b-1;
for(int i=1;i<=NN;++i)MM[b[i]]=i;
for(int i=1;i<=NN;++i)mm[i]=b[i];
for(int i=1;i<=N;++i)a[i]=MM[a[i]];
Root[0]=1;build(1,1,NN);
for(int i=1;i<=N;++i){Root[i]=cnt+1;update(Root[i-1],a[i],1);}
for(int i=1;i<=M;++i)
{
int u=read(),v=read(),w=read();
int ans=Query(Root[u-1],Root[v],w);
printf("%dn",mm[ans]);
}
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
