Description
Solution
这道题似乎能用很多种方法来做,我用的 \(fhq-treap\)。
本来我想的是维护两只平衡树,一个用来找区间,另一个来找区间最大值。
想了一会发现想假了。这样做完全不对。
于是去题解区看了一眼题解,发现似乎可以用莫队来做,但是没找到 \(fhq-treap\) 的题解。
仔细思考一下,发现确实可以用莫队做(我还是第一次见到莫队+平衡树的题)。
下面我们来分析一下:
我们发现询问保证区间 \([i,j]\) 不互相包含,由此我们可以推出一个性质:
对于两个询问 \([x_1,y_1]\) 和 \([x_2,y_2]\),必定有 \(x_2 \geq x_1\), \(y_2 \geq y_1\),且不能同时取等(反过来一样)。
所以我们可以套用莫队的做法,即,不停的往平衡树里插入点,同时删除掉不用的点。
当然,首先还是要把询问记录下来,并从小到大排序啦。
然后这道题就做完了。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define ls(x) t[x].l
#define rs(x) t[x].r
using namespace std;
const int N = 3e5 + 10;
const int M = 5e4 + 10;
int n, m;
int v[N], ans[M];
struct FHQ_treap{
int siz, val, l, r, wei;
}t[N];
int tot, root;
int a, b, c;
struct Query{
int id, l, r, k;
bool operator < (const Query &b) const{
return l != b.l ? l < b.l : r < b.r;
}
}q[M];
inline void pushup(int x){
t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}
inline void split(int x, int k, int &a, int &b){
if(!x){
a = b = 0;
return;
}
if(t[x].val <= k){
a = x;
split(rs(x), k, rs(x), b);
}else{
b = x;
split(ls(x), k, a, ls(x));
}
pushup(x);
}
inline int merge(int x, int y){
if(!x || !y) return x | y;
if(t[x].wei <= t[y].wei){
rs(x) = merge(rs(x), y);
pushup(x);
return x;
}else{
ls(y) = merge(x, ls(y));
pushup(y);
return y;
}
}
inline int newnode(int k){
t[++tot].val = k, t[tot].siz = 1, t[tot].wei = rand();
return tot;
}
inline void add(int k){
split(root, k, a, b);
root = merge(a, merge(newnode(k), b));
}
inline void del(int k){
split(root, k, a, b);
split(a, k - 1, a, c);
c = merge(ls(c), rs(c));
root = merge(a, merge(c, b));
}
inline int query_val(int x, int k){
if(k == t[ls(x)].siz + 1) return t[x].val;
if(k < t[ls(x)].siz + 1) return query_val(ls(x), k);
else return query_val(rs(x), k - t[ls(x)].siz - 1);
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
q[i].id = i;
}
sort(q + 1, q + 1 + m);
int l = 1, r = 0;
for(int i = 1; i <= m; i++){
while(r < q[i].r) add(v[++r]);
while(l < q[i].l) del(v[l++]);
ans[q[i].id] = query_val(root, q[i].k);
}
for(int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}