2020牛客NOIP赛前集训提高组#5-C-经典字符串问题(主席树，权值线段树)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
struct node{
string s;int x,num;
}p[MAXN];
int cmp(node a,node b){return a.s<b.s;}
int a[MAXN],l[MAXN*40],r[MAXN*40],v[MAXN*40],rt[MAXN],tot=0;
int build(int a,int b){
int y=++tot;
if(a==b) return y;
int mid=(a+b)>>1;
l[y]=build(a,mid);
r[y]=build(mid+1,b);
return y;
}
int update(int x,int a,int b,int z,int c){
int y=++tot;
v[y]=v[x]+c;
if(a==b) return y;
int mid=(a+b)>>1;
if(mid>=z) l[y]=update(l[x],a,mid,z,c),r[y]=r[x];
else l[y]=l[x],r[y]=update(r[x],mid+1,b,z,c);
return y;
}
int query(int a,int b,int k,int x,int y){
if(a==b) return a;
int mid=(a+b)>>1;
if(k<=v[l[x]]-v[l[y]]) return query(a,mid,k,l[x],l[y]);//与差比较
else return query(mid+1,b,k-(v[l[x]]-v[l[y]]),r[x],r[y]);
}//主席树
int main()
{
int n,q,u,v,k,ans;cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>p[i].s;p[i].x=i;
}sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++) a[p[i].x]=i;//记下第p[i].x个字符串是排序后的第i个
//由于题目保证是1~n的排列，可以直接离散化成排名
rt[n+1]=build(1,n);
for(int i=n;i>=1;i--) rt[i]=update(rt[i+1],1,n,a[i],1);
//在a[i]的位置+1，即有一个大小为i的数字
while(q--){
cin>>u>>v>>k;
if(v-u+1<k){puts("-1");continue;}
ans=query(1,n,k,rt[u],rt[v+1]);//找到答案，然后还原成字符串
//前缀和常识要减去后一位
cout<<p[ans].s<<endl;
}
}