主席树套树状数组的动态区间kth模板题
静态区间的kth就是主席树的独角戏，现在需要支持修改操作，如果只用主席树的话一次会有\(O(n\log n)\)的修改，直接爆炸。
解决方法是套上一个树状数组。
我们这么理解：
原来树状数组的每一段是一个数字是吧，我们现在的每一段直接变成一颗主席树！
这样的话，按照树状数组\(O(\log n)\)一次查询前缀和的修改特性，我们一次修改只需要修改\(\log n\)棵主席树，复杂度直接降下来了。
查询的话直接类似树状数组求前缀和那样，拿到代表历史版本和当前版本的\(\log n\)棵主席树，相减照样能出答案。
这里写到的主席树应该是真正意义上的动态开点线段树了吧。。。
PS：这里的数据你大胆地开大，不然你就只能够拿到暴力分。。。
代码：
#include#include #include const int maxn = 300005;struct Chairman_Tree{ int lson, rson, sum;} s[20000005];// maybe not enoughint tot;int T[maxn];int temp[2][100], cnt[2];struct Questions{ char opt; int x, y, k;} q[maxn];int a[maxn], b[maxn], len;int n, m;inline int lowbit(int x){ return x & -x;}void modify(int &now, int l, int r, int pos, int val){ if(now == 0) now = ++tot; s[now].sum += val; if(l == r) return; int mid = (l + r) >> 1; if(pos <= mid) modify(s[now].lson, l, mid, pos, val); else modify(s[now].rson, mid + 1, r, pos, val);}void prepare_modify(int x, int val){ int pos = std::lower_bound(b + 1, b + len + 1, a[x]) - b; for(int i = x; i <= n; i += lowbit(i)) modify(T[i], 1, len, pos, val);}int query(int l, int r, int k){ if(l == r) return l; int x = 0, mid = (l + r) >> 1; for(int i = 1; i <= cnt[1]; i++) x += s[s[temp[1][i]].lson].sum; for(int i = 1; i <= cnt[0]; i++) x -= s[s[temp[0][i]].lson].sum; if(k <= x) { for(int i = 1; i <= cnt[1]; i++) temp[1][i] = s[temp[1][i]].lson; for(int i = 1; i <= cnt[0]; i++) temp[0][i] = s[temp[0][i]].lson; return query(l, mid, k); } else { for(int i = 1; i <= cnt[1]; i++) temp[1][i] = s[temp[1][i]].rson; for(int i = 1; i <= cnt[0]; i++) temp[0][i] = s[temp[0][i]].rson; return query(mid + 1, r, k - x); }}int prepare_query(int x, int y, int k){ memset(temp, 0, sizeof temp); cnt[0] = cnt[1] = 0; for(int i = y; i; i -= lowbit(i)) temp[1][++cnt[1]] = T[i]; for(int i = x - 1; i; i -= lowbit(i)) temp[0][++cnt[0]] = T[i]; return query(1, len, k);}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[++len] = a[i]; } for(int i = 1; i <= m; i++) { scanf(" %c%d%d", &q[i].opt, &q[i].x, &q[i].y); if(q[i].opt == 'Q') scanf("%d", &q[i].k); else if(q[i].opt == 'C') b[++len] = q[i].y; } std::sort(b + 1, b + len + 1); len = std::unique(b + 1, b + len + 1) - b - 1; for(int i = 1; i <= n; i++) prepare_modify(i, 1); for(int i = 1; i <= m; i++) { if(q[i].opt == 'Q') { printf("%d\n", b[prepare_query(q[i].x, q[i].y, q[i].k)]); } else if(q[i].opt == 'C') { prepare_modify(q[i].x, -1); a[q[i].x] = q[i].y; prepare_modify(q[i].x, 1); } } return 0;}