# 一无所|知的小|J f

### 题解 P3834 【【模板】可持久化线段树 1（主席树）】

posted on 2019-03-15 22:03:31 | under 题解 |

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define maxn 200010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, k;
int sq, sq2;
int nw[maxn], a[maxn], b1[maxn], b2[maxn], cnt1[500][500], cnt2[480][maxn], q[maxn][4], z[maxn];
int san[500], san2[maxn];

inline void in(re int &x){
x=0;int bl = 1;char c=getchar();
while(c<'0'||c>'9'){
if(c == '-')
bl = -1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x *= bl;
}

void out(re int a){
if(a < 0) {
putchar('-');
a = -a;
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

int get_val(int x, int y, int k) {
int res = 0, pd = 0;
FOR(i, x, min(y, b1[x]*sq))
++san[b2[nw[i]]], ++san2[nw[i]];
if(b1[x] != b1[y])
FOR(i, (b1[y]-1)*sq+1, y)
++san[b2[nw[i]]], ++san2[nw[i]];
FOR(i, 1, b2[z[0]]) {
int ld = cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
if(ld < 0) ld = 0;
if(res+(ld+san[i]) < k) {
res += san[i];
if(cnt1[b1[y]-1][i]-cnt1[b1[x]][i] > 0)
res += cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
}
else {
pd = i;
break;
}
}
int anss = -1;
FOR(i, (pd-1)*sq2+1, pd*sq2) {
res += san2[i];
if(cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0)
res += cnt2[b1[y]-1][i]-cnt2[b1[x]][i];
if(res >= k) {
anss = z[i];
break;
}
}
FOR(i, x, min(y, b1[x]*sq))
--san[b2[nw[i]]], --san2[nw[i]];
if(b1[x] != b1[y])
FOR(i, (b1[y]-1)*sq+1, y)
--san[b2[nw[i]]], --san2[nw[i]];
return anss;
}

int main() {
in(n), in(m);
sq = sqrt(n);
FOR(i, 1, n)
in(a[i]), b1[i] = (i-1)/sq+1, z[++z[0]] = a[i];
FOR(i, 1, m) {
in(q[i][1]),
in(q[i][2]),
in(q[i][3]);
}
sort(z+1, z+z[0]+1);
z[0] = unique(z+1, z+z[0]+1)-z-1;
sq2 = sqrt(z[0]);
FOR(i, 1, z[0])
b2[i] = (i-1)/sq2+1;
FOR(i, 1, n) {
nw[i] = lower_bound(z+1, z+z[0]+1, a[i])-z; //nw为a排序后的位置，处理cnt1， cnt2
++cnt1[b1[i]][b2[nw[i]]];
++cnt2[b1[i]][nw[i]];
}
FOR(i, 1, b1[n]) { //处理前缀和
FOR(j, 1, b2[z[0]])
cnt1[i][j] += cnt1[i-1][j];
FOR(j, 1, z[0])
cnt2[i][j] += cnt2[i-1][j];
}
FOR(i, 1, m) {
out(get_val(q[i][1], q[i][2], q[i][3]));
putchar(10);
}
}