[JSK]动态数列II

[JSK]动态数列II

大意

每次在一段序列的末尾加一个数 \(x\)，每次查询序列从大到小排序后的第 \(x\) 个的数。

思路

考虑动态开点的权值线段树，由于不是每一个点都需要用，我们考虑用的时候再给他开出来。

直接在结构体里面存上你该点的左右儿子的编号。

一般来说我们动态开点都是在 pushdown 里面做的，这个题不需要 pushdown，所以直接在 update 里面做了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 * 40 + 10;
const int INF = (1<<30);
struct node {int val, l, r;
} a[N];
int n, m, tot = 1;
void pushup(int rt) {a[rt].val = a[a[rt].l].val + a[a[rt].r].val;
}
void update(int rt, int l, int r, int pos, int x) {if (l == r) {a[rt].val ++;return;}int mid = (l + r) / 2;if (pos <= mid) {if(!a[rt].l){a[rt].l = ++ tot;}update(a[rt].l, l, mid, pos, x);} else {if(!a[rt].r){a[rt].r = ++ tot;}update(a[rt].r, mid + 1, r, pos, x);}pushup(rt);
}
int query(int rt, int l, int r, int x) {if (l == r) return r;int mid = (l + r) / 2;if(a[a[rt].r].val >= x){return query(a[rt].r, mid + 1, r, x);}else{return query(a[rt].l, l, mid, x - a[a[rt].r].val);}
}
int main() {std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int op, x;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> x;update(1, 1, INF, x, 1);}for (int i = 0; i < m; i++) {cin >> op >> x;if (op == 1) {update(1, 1, INF, x, 1);} else {cout << query(1, 1, INF, x) << endl;}}return 0;
}