动态区间第k小
想一下:
静态区间第k小 -> 主席树
动态整体第k小 -> 树状数组
所以树套树就行了
事实上这题还真就套一下 也不难写
一共两个操作:
1.插入 原来的一棵树插入变成树状数组插入
2.查询 原来的整体查询变成树状数组查询
修改就先-1再+1就行
可以开一个栈存每一组询问[l,r]中需要统计的主席树编号来统计答案
还是看代码吧 比较好理解
(主要是抄的时候挑了一个好的)
Code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define rep(i,a,n) for(int i = a;i <= n;i++) 6 #define per(i,n,a) for(int i = n;i >= a;i--) 7 using namespace std; 8 typedef long long ll; 9 int read() { 10 int as = 0,fu = 1; 11 char c = getchar(); 12 while(c < '0' || c > '9') { 13 if(c == '-') fu = -1; 14 c = getchar(); 15 } 16 while(c >= '0' && c <= '9') { 17 as = as * 10 + c - '0'; 18 c = getchar(); 19 } 20 return as * fu; 21 } 22 const int N = 400005; 23 const int M = 40000005; 24 //head 25 26 int n,Q,T; 27 int tot; 28 int sze[M]; 29 int a[N],b[N],ca[N],cb[N],cc[N]; 30 int ls[M],rs[M],rt[N]; 31 32 void ins(int l,int r,int &t,int pre,int q,int v) { 33 t = ++tot; 34 sze[t] = sze[pre] + v; 35 ls[t] = ls[pre],rs[t] = rs[pre]; 36 if(l == r) return; 37 int m = l+r >> 1; 38 if(q <= m) ins(l,m,ls[t],ls[pre],q,v); 39 else ins(m+1,r,rs[t],rs[pre],q,v); 40 } 41 42 int tx[N],ty[N]; 43 int query(int l,int r,int k) { 44 if(l == r) return l; 45 int sum = 0,m = l+r >> 1; 46 rep(i,1,tx[0]) sum -= sze[ls[tx[i]]]; 47 rep(i,1,ty[0]) sum += sze[ls[ty[i]]]; 48 if(k <= sum) { 49 rep(i,1,tx[0]) tx[i] = ls[tx[i]]; 50 rep(i,1,ty[0]) ty[i] = ls[ty[i]]; 51 return query(l,m,k); 52 } else { 53 rep(i,1,tx[0]) tx[i] = rs[tx[i]]; 54 rep(i,1,ty[0]) ty[i] = rs[ty[i]]; 55 return query(m+1,r,k - sum); 56 } 57 } 58 59 inline void update(int x,int v) { 60 int k = lower_bound(b + 1,b + T + 1,a[x]) - b; 61 // printf("%d %d %d ",x,v,k); 62 for(int i = x;i <= n;i += (i & (-i))) ins(1,T,rt[i],rt[i],k,v); 63 } 64 65 char cmd[20]; 66 int main() { 67 n = read(),Q = read(); 68 rep(i,1,n) a[i] = b[++T] = read(); 69 rep(i,1,Q) { 70 scanf("%s",cmd); 71 ca[i] = read(),cb[i] = read(); 72 cmd[0] == 'Q' ? cc[i] = read() : b[++T] = cb[i]; 73 } 74 sort(b+1,b+T+1); 75 T = unique(b+1,b+T+1) - b - 1; 76 rep(i,1,n) update(i,1); 77 rep(i,1,Q) { 78 if(cc[i]) { 79 tx[0] = ty[0] = 0; 80 for(int j = ca[i]-1;j;j -= (j & (-j))) tx[++tx[0]] = rt[j]; 81 for(int j = cb[i];j;j -= (j & (-j))) ty[++ty[0]] = rt[j]; 82 printf("%d ",b[query(1,T,cc[i])]); 83 } else update(ca[i],-1),a[ca[i]] = cb[i],update(ca[i],1); 84 } 85 }