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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <bits/stdc++.h>
using namespace std;
int read(){
int res=0,sign=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-'){sign=-sign;}
for(;ch>='0'&&ch<='9';ch=getchar()){res=(res<<3)+(res<<1)+(ch^'0');}
return res*sign;
}
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define dep(i,r,l) for(int i=r;i>=l;--i)
const int N=2e5+10;
int n,m;
int a[N],rk[N],len;
void init(){
rep(i,1,n)rk[i]=a[i];
sort(rk+1,rk+1+n);
len=unique(rk+1,rk+1+n)-rk-1;
}
int getidx(int x){
return lower_bound(rk+1,rk+1+len,x)-rk;
}
int d[N];
void ins(int x,int c){
for(;x<N;x+=x&-x){
d[x]+=c;
}
}
int query(int x){
int res=0;
for(;x;x-=x&-x){
res+=d[x];
}
return res;
}
struct query_t{
int l,r,k,id;
};
query_t q[N<<1],q1[N<<1],q2[N<<1];
int tot;
int ans[N];
void solve(int s,int t,int ql,int qr){
if(ql>qr)return;
if(s==t){
rep(i,ql,qr)if(q[i].id)ans[q[i].id]=s;
return;
}
int mid=s+t>>1,tot1=0,tot2=0;
rep(i,ql,qr)if(!q[i].id){
if(q[i].k<=mid){
ins(q[i].l,1);
q1[++tot1]=q[i];
}else{
q2[++tot2]=q[i];
}
}else{
int x=query(q[i].r)-query(q[i].l-1);
if(q[i].k<=x){
q1[++tot1]=q[i];
}else{
q[i].k-=x;
q2[++tot2]=q[i];
}
}
rep(i,1,tot1)if(!q1[i].id)ins(q1[i].l,-1);
rep(i,1,tot1)q[ql+i-1]=q1[i];
rep(i,1,tot2)q[ql+tot1+i-1]=q2[i];
solve(s,mid,ql,ql+tot1-1);
solve(mid+1,t,ql+tot1,qr);
}
int main(){
n=read(),m=read();
rep(i,1,n){
a[i]=read();
}
init();
rep(i,1,n){
q[++tot]={i,0,getidx(a[i]),0};
}
rep(i,1,m){
int l=read(),r=read(),k=read();
q[++tot]={l,r,k,i};
}
solve(1,len,1,tot);
rep(i,1,m)printf("%d\n",rk[ans[i]]);
return 0;
}
|