题目传送门(BZOJ)
>原文链接<

题解 :

带修主席树模板

维护一个数据结构, 支持单点修改, 区间查询K大.

区间第K大可以方便的用主席树维护, 但是若要改某个版本的主席树, 则其后面所有的主席树都要做此修改.

利用树状数组维护前缀的性质, 把要修的x及其在树状数组后面的点一起扔到数组里, 从上到下一起更新.

对于查询, 把l-1r的在树状数组中的点都扔到树状数组里, 每层用\sum\limits_i t[r[i]]-\sum\limits_j t[l-1[j]]来判断当前权值线段树左儿子权值和, 按照一般的方法去选择递归左右子树, 选择之后把所有的当前点都置成其对应的ls/rs.

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define mid ((l+r)/2)using namespace std;const int N = 120000;const int INF = 1e9;int t[N*50], ls[N*50], rs[N*50], root[N];int ax[N], ay[N], a[N], n, m;void insert(int l, int r, int &x, int y, int pos, int c) { static int _ = 0; if(!x) x = ++_; if(l == r) return t[x] = t[y]+c, void(); if(pos <= mid) rs[x] = rs[y], insert(l, mid, ls[x], ls[y], pos, c); else ls[x] = ls[y], insert(mid+1, r, rs[x], rs[y], pos, c); t[x] = t[ls[x]] + t[rs[x]];}int query(int l, int r, int k) { if(l == r) return l; int sizl = 0; for(int i = 1; i <= *ay; i ++ ) sizl += t[ls[ay[i]]]; for(int i = 1; i <= *ax; i ++ ) sizl -= t[ls[ax[i]]]; if(k <= sizl) { for(int i = 1; i <= *ay; i ++ ) ay[i] = ls[ay[i]]; for(int i = 1; i <= *ax; i ++ ) ax[i] = ls[ax[i]]; return query(l, mid, k); } else { for(int i = 1; i <= *ay; i ++ ) ay[i] = rs[ay[i]]; for(int i = 1; i <= *ax; i ++ ) ax[i] = rs[ax[i]]; return query(mid+1, r, k-sizl); }}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); for(int j = i; j <= n; j += j&-j) insert(0, INF, root[j], root[j], a[i], 1); } char opt[3]; while(m -- ) { int x, y; scanf("%s%d%d", opt, &x, &y); if(opt[0] == 'C') { for(int j = x; j <= n; j += j&-j) insert(0, INF, root[j], root[j], a[x], -1); a[x] = y; for(int j = x; j <= n; j += j&-j) insert(0, INF, root[j], root[j], a[x], 1); } else { int k; scanf("%d", &k); *ax = *ay = 0; for(int j = y; j; j -= j&-j) ay[++*ay] = root[j]; for(int j = x-1; j; j -= j&-j) ax[++*ax] = root[j]; printf("%d\n", query(0, INF, k)); } }}