q l, r, k
查询[l, r] 第k小。
m pos, x; 把pos位置的改为x。
每次询问就是对O(logn) 棵树加加减减后求第k 大。修改也会同时修改O(logn) 棵树，所以总的复杂度是：O((m+n)log^2 n)。
#include "cstdio" #include "cctype" #include "cstdlib" #include "cstring" #define lowbit(x) (x & (-x)) #define min(a, b) ((a) < (b) ? (a) : (b)) #define rep(i, m, n) for(register int i = (m); i <= (n); ++i) template <class T> inline bool readIn(T &x) { T flag = 1; char ch; while(!(isdigit(ch = (char) getchar())) && ch != EOF) if( ch == '-' ) flag = -1; if(ch == EOF) return false; for(x = ch - 48; isdigit(ch = (char) getchar()); x = (x << 1) + (x << 3) + ch - 48); x *= flag; return true; } template <class T> inline void write(T x) { if (x > 9) write(x / 10); putchar(x % 10 + 48); } template <class T> inline bool writeIn(T x) { if (x < 0) { putchar('-'); x = -x; } write(x); return true; } class io { public: io() { freopen("intkth.in", "r", stdin); freopen("intkth.out", "w", stdout); } ~io() { fclose(stdin); fclose(stdout); } } M; const int MAXN = 100005; struct Node { int cnt; Node *ls, *rs; Node(int cnt = 0, Node *ls = NULL, Node *rs = NULL) : cnt(cnt), ls(ls), rs(rs) { } } pool[MAXN * 200], *tail = pool, *roots[MAXN], *null; int ca, cb, n, m, l, r, k, pos, val, a[MAXN]; Node *va[10001], *vb[10001]; inline void init() { null = ++tail; null -> ls = null; null -> rs = null; null -> cnt = 0; } inline Node *newnode() { Node *nd = ++tail; nd->ls = null; nd->rs = null; nd->cnt = 0; return nd; } void modify( int lf, int rg, int pos, int delta ) { for(register int i = 0; i < ca; va[i]->cnt += delta, ++i); if( lf ^ rg ) { int mid = (lf + rg) >> 1; if( pos <= mid ) { for( int t = 0; t < ca; t++ ) { if( va[t]->ls == null ) va[t]->ls = newnode(); va[t] = va[t]->ls; } modify( lf, mid, pos, delta ); } else { for(register int i = 0; i < ca; ++i) { if( va[i] -> rs == null ) va[i] -> rs = newnode(); va[i] = va[i] -> rs; } modify( mid + 1, rg, pos, delta ); } } } int query_seg( int lf, int rg, int k ) { if( lf == rg ) return lf; int mid = (lf + rg) >> 1; int lz = 0; for(register int i = 0; i < ca; ++i) lz += va[i] -> ls -> cnt; for(register int i = 0; i < cb; ++i) lz -= vb[i] -> ls -> cnt; if( k <= lz ) { for(register int i = 0; i < ca; ++i) va[i] = va[i]->ls; for(register int i = 0; i < cb; ++i) vb[i] = vb[i]->ls; return query_seg( lf, mid, k ); } else { for(register int i = 0; i < ca; ++i) va[i] = va[i] -> rs; for(register int i = 0; i < cb; ++i) vb[i] = vb[i] -> rs; k -= lz; return query_seg( mid + 1, rg, k ); } } inline void modify( int u, int x, int delta ) { ca = 0; for( register int i = u; i <= n; i += lowbit(i) ) va[ca++] = roots[i]; modify( 1, n, x, delta ); } inline void modify( int u, int x ) { modify( u, a[u], -1 ); modify( u, x, +1 ); a[u] = x; } inline int query( int l, int r, int k ) { ca = cb = 0; for( register int i = r; i; i -= lowbit(i) ) va[ca++] = roots[i]; for( register int i = l - 1; i; i -= lowbit(i) ) vb[cb++] = roots[i]; return query_seg(1, n, k); } int main() { readIn(n);readIn(m); rep(i, 1, n) readIn(a[i]); init(); rep(i, 1, n) roots[i] = newnode(); rep(i, 1, n) modify( i, a[i], +1 ); while( m-- ) { static char s; while((s = (char) getchar()) == ' ' || s == '\n'); if( s == 'q' ) { readIn(l);readIn(r);readIn(k); writeIn(query(l, r, k)); putchar(10); } else { readIn(pos);readIn(val); modify( pos, val ); } } return 0; }