?
ZOJ 2112 Dynamic Rankings（线段树树套平衡树）(二)
<'0'||c>'9')&&c!='-'); if(c == '-') { flag = 1; c = getchar(); } while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar(); if(flag) ret = -ret; } const int maxn = 50000+10; const int maxm = 10000+10; struct Node { Node* ch[2]; int r,v,s; int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } void maintain() { s = ch[0]->s+ch[1]->s+1; } }treap[maxn*18]; int nodecnt; Node* null = &treap[0]; Node* newnode() { Node* p = &treap[nodecnt++]; return p; } void nodeinit(Node* &o, int v) { o->r = rand(); o->s = 1; o->v = v; o->ch[0] = o->ch[1] = null; } void rotate(Node* &o, int d) { Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(Node* &o, int v) { if(o == null) { o = newnode(); nodeinit(o,v); return; } int d = v < o->v ? 0 : 1;//有重复值 insert(o->ch[d],v); if(o->ch[d]->r > o->r) rotate(o,d^1); o->maintain(); } void remove(Node* &o, int v) { int d = o->cmp(v); if(d == -1) { if(o->ch[0] != null && o->ch[1] != null) { int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0; rotate(o,d2); remove(o->ch[d2],v); } else { if(o->ch[0] != null) o = o->ch[0]; else o = o->ch[1]; } } else remove(o->ch[d],v); if(o != null) o->maintain(); } int query1(Node* &o, int k)//
v < k) return o->ch[0]->s+1+query1(o->ch[1],k); return query1(o->ch[0],k); } int query2(Node* &o, int k)//<=k有几个 { if(o == null) return 0; if(o->v <= k) return o->ch[0]->s+1+query2(o->ch[1],k); return query2(o->ch[0],k); } Node* T[maxn<<2]; int a[maxn],n; void build(int l, int r, int rt) { T[rt] = null; if(l == r) return; int mid = (l+r)>>1; build(lson); build(rson); } void insertit(int L, int k, int l, int r, int rt) { insert(T[rt],k); if(l == r) return; int mid = (l+r)>>1; if(L <= mid) insertit(L, k, lson); else insertit(L, k, rson); } int querytree(int L, int R, int k, int flag, int l, int r, int rt) { if(L <= l && R >= r) { if(flag == 1) return query1(T[rt],k); else return query2(T[rt],k); } int mid = (l+r)>>1,ans = 0; if(L <= mid) ans += querytree(L,R,k,flag,lson); if(R > mid) ans += querytree(L,R,k,flag,rson); return ans; } int query(int L, int R, int k) { int x = 0,y = 1000000000; while(x <= y) { int m = (x+y) >> 1; int p1 = querytree(L,R,m,1,1,n,1),p2 = querytree(L,R,m,2,1,n,1); if(p1 <= k-1) { if(p2 >= k) return m; else x = m+1; } else y = m-1; } } void removeit(int L, int k, int l, int r, int rt) { remove(T[rt],k); if(l == r) return; int mid = (l+r) >> 1; if(L <= mid) removeit(L,k,lson); else removeit(L,k,rson); } int main() { #ifdef GLQ freopen("input.txt","r",stdin); // freopen("o.txt","w",stdout); #endif srand(time(NULL)); null->s = 0; int t,m; scanf("%d",&t); while(t--) { nodecnt = 1; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); // scan_d(a[i]); build(1,n,1); for(int i = 1; i <= n; i++) insertit(i,a[i],1,n,1); while(m--) { char tmp[2]; scanf("%s",tmp); if(tmp[0] == 'Q') { int l,r,k; scanf("%d%d%d",&l,&r,&k); // scan_d(l); scan_d(r); scan_d(k); printf("%d\n",query(l,r,k)); } else { int pos,k; scanf("%d%d",&pos,&k); // scan_d(pos); scan_d(k); removeit(pos,a[pos],1,n,1); insertit(pos,k,1,n,1); a[pos] = k; } } } return 0; }