题解
- 主席树(划分树)入门
主席树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
const int N=1e5+7;
typedef pair<int,int> q;
int rt[N*20],root[N],rk[N],lson[N*20],rson[N*20],cnt=1,n,m,T;
q nm[N];
inline void update(int &o,int l,int r,int num){
rt[cnt]=rt[o];lson[cnt]=lson[o];rson[cnt++]=rson[o];o=cnt-1;rt[o]++;
if(l==r)return ;
int mid=l+r>>1;
if(num<=mid)update(lson[o],l,mid,num);
else update(rson[o],mid+1,r,num);
}
inline int query(int i,int j,int l,int r,int k){
int t=rt[lson[j]]-rt[lson[i]];
if(l==r)return l;
int mid=l+r>>1;
if(k<=t)return query(lson[i],lson[j],l,mid,k);
else return query(rson[i],rson[j],mid+1,r,k-t);
}
int main(){
scanf("%d",&n);
rep(i,1,n){
int x;
scanf("%d",&x);
nm[i]=q(x,i);
}
scanf("%d",&m);
sort(nm+1,nm+n+1);
rep(i,1,n)rk[nm[i].second]=i;
rep(i,1,n){root[i]=root[i-1];update(root[i],1,n,rk[i]);}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a++;b++;
c=b-a+2-c;
printf("%d\n",nm[query(root[a-1],root[b],1,n,c)].first);
}
return 0;
}