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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
#define debugN(var,N) \
do{ \
std::cerr<<#var<<":"; \
FOR(i,1,N){ \
std::cerr<<var[i]<<" "; \
} \
std::cerr<<"\n"; \
}while(0)
#define debugMap(variable) \
do { \
std::cerr << #variable << ":\n"; \
for (const auto& pair : variable) { \
std::cerr << " " << pair.first << " => " << pair.second << "\n"; \
} \
std::cerr << std::endl; \
} while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x)) // vec中大于x的数有几个
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT;
/*
*/
struct persisTree{ // 单点修改区间查询的主席树，处理静态区间第 k 小问题。
// 由于太大了，该结构体只能声明与全局变量作用域
// // maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
static const int maxn=static_cast<ll>(2e5)+7,maxm=static_cast<ll>(2e5)+7;
static const int maxn4=maxn*22; // 这个版本次数一般也不会超过int，给个32绝对够了
int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
ll arr[maxn],sum[maxn4];
int n=0,m=0,idx=1,Cver=0,len=0;
ll li[maxn];
// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
// vector<int> ls,rs,L,R,root,arr,li; // 因为主席树这些数是不能复用的，我们直接就用动态数组吧。
// persisTree(int ln,int lm){
// n=ln,m=lm;
// ll siz=n*4+log2(n)*m+7;
// ls.resize(siz),rs.resize(siz),L.resize(siz),R.resize(siz),root.resize(siz);
// arr.resize(siz);
// }
inline void init(int ln,int lm){
// int lmaxn4=ln*4+log2(ln)*lm+5;
idx=1,n=ln,m=lm,Cver=0;
// for(int i=0;i<=lmaxn4;++i){ // 有build在，init不用干这个事情
// ls[i]=0,rs[i]=0;
// sum[i]=0,L[i]=0,R[i]=0;
// }
// for(int i=0;i<=lm;++i){
// root[i]=0,arr[i]=0;
// }
root[0]=1; // 版本0的根是1
}
inline int initLi(){ // 离散化操作
for(int i=1;i<=n;++i){
li[i]=arr[i];
}
sort(li+1,li+1+n);
len=unique(li+1,li+1+n)-li-1; // 这个len是超了一个的
return len;
}
inline int kth(ll x){
int ret=lower_bound(li+1,li+1+len,x)-li;
return ret;
}
inline void clone(int node){
++idx;
L[idx]=L[node];
R[idx]=R[node];
sum[idx]=sum[node];
ls[idx]=ls[node];
rs[idx]=rs[node];
}
void build(int node,int l,int r){
ls[node]=++idx;
rs[node]=++idx;
L[node]=l;
R[node]=r;
sum[node]=0;
if(l==r) return;
build(ls[node],l,((l+r)>>1));
build(rs[node],(l+r>>1)+1,r);
}
// 处理静态区间第 k 小问题中，因为权值线段树，x=1
void add(int node,int ver,int p,ll x){
clone(node);
sum[idx]+=x;
if(p==L[node] && p==R[node]){
return;
}
// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
if(root[ver]==node){
++Cver;
root[Cver]=idx;
}
if(p>=L[ls[node]] && p<=R[ls[node]]){
int nals=ls[idx];
ls[idx]=idx+1;
add(nals,ver,p,x);
}else{
int nars=rs[idx];
rs[idx]=idx+1;
add(nars,ver,p,x);
}
}
// u v 为node，l，r为区间，k为区间第k小
int query(int u,int v,int l,int r,int k){
if(l==r){
return l;
}
// 我们这样就知道了
int lsum=sum[ls[v]]-sum[ls[u]];
int mid=l+r>>1;
if(lsum>=k){
return query(ls[u],ls[v],l,mid,k);
}else{
return query(rs[u],rs[v],mid+1,r,k-lsum);
}
}
};
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(ll x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
return;
}
persisTree tr; // 由于太大了，该结构体只能声明与全局变量作用域
inline void solve(){
N=read(),M=read();
tr.init(N,N);
FOR(i,1,N){
tr.arr[i]=read();
}
int len=tr.initLi();
// #ifdef LOCAL
// cerr << "build 1" << '\n';
// #endif
tr.build(1,1,len);
// #ifdef LOCAL
// cerr << "build 2" << '\n';
// #endif
FOR(i,1,N){
// 权值线段树单点加
tr.add(tr.root[tr.Cver],tr.Cver,tr.kth(tr.arr[i]),1);
// #ifdef LOCAL
// debug(tr.kth(tr.arr[i]));
// FOR(i,1,tr.idx){
// cerr<<i<<" L:"<<tr.L[i]<<" R:"<<tr.R[i]<<" sum:"<<tr.sum[i]<<"\n";
// }
// cerr<<"\n";
// #endif
// #ifdef LOCAL
// debug(i);
// #endif
}
// #ifdef LOCAL
// cerr << "success add" << '\n';
// #endif
FOR(_,1,M){
ll l=read(),r=read(),k=read();
// 这个l,r是权值线段树中的值域，所以初始传入【1，2】
ll ans=tr.query(tr.root[l-1],tr.root[r],1,len,k);
write(tr.li[ans]),putchar('\n');
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// cin>>lT;
// while(lT--){
// solve();
// }
solve();
return 0;
}
/*
AC
https://www.luogu.com.cn/record/218615977
*/
|