Dynamic Rankings
【问题描述】
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。接下来的m行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t。
【输入格式】
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
【样例输入】
5 3
3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3【样例输出】
3
6题解：
树套树裸题
以树状数组作为第一维，以权值线段树作为第二维
树状数组中每个节点代表了一段区间
把这一段区间的信息建立一颗权值线段树，存在对应节点上（存根）
查询时把需要的区间在树状数组中取出（把区间 [ l , r ] 拆成 [ 1 , r ] - [ 1 , l - 1 ]）
有大佬能告诉蒟蒻为什么网上很多大佬用了树状数组套主席树吗
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn = 2e4 + 3; 9 const int lgn = 20; 10 const int nlgn = maxn * lgn * lgn; 11 int n, m; 12 char s[lgn]; 13 int tot; 14 int num, cnt; 15 int val[maxn]; 16 int sum[nlgn]; 17 int rt[nlgn], lc[nlgn], rc[nlgn]; 18 int disc[maxn]; 19 int nu, nv, u[lgn], v[lgn]; 20 struct ask 21 { 22 char c; 23 int l, r, k; 24 }; 25 ask a[maxn]; 26 inline void Scan(int &x) 27 { 28 char c; 29 bool o = false; 30 while(!isdigit(c = getchar())) o = (c != '-') ? o : true; 31 x = c - '0'; 32 while(isdigit(c = getchar())) x = x * 10 + c - '0'; 33 if(o) x = -x; 34 } 35 inline int Get(int x) 36 { 37 return lower_bound(disc + 1, disc + 1 + cnt, x) - disc; 38 } 39 inline void Disc() 40 { 41 sort(disc + 1, disc + 1 + num); 42 ++cnt; 43 for(int i = 2; i <= num; ++i) 44 if(disc[i] != disc[i - 1]) 45 disc[++cnt] = disc[i]; 46 disc[cnt + 1] = 2147483647; 47 } 48 void Insert(int &k, int l, int r, int v) 49 { 50 if(!k) k = ++tot; 51 ++sum[k]; 52 if(l == r) return; 53 int mid = l + r >> 1; 54 if(v <= mid) Insert(lc[k], l, mid, v); 55 else Insert(rc[k], mid + 1, r, v); 56 } 57 void Delete(int k, int l, int r, int v) 58 { 59 --sum[k]; 60 if(l == r) return; 61 int mid = l + r >> 1; 62 if(v <= mid) Delete(lc[k], l, mid, v); 63 else Delete(rc[k], mid + 1, r, v); 64 } 65 void Add(int x, int v) 66 { 67 while(x <= n) 68 { 69 Insert(rt[x], 1, cnt, v); 70 x += x & (-x); 71 } 72 } 73 inline void Change(int x, int c, int v) 74 { 75 while(x <= n) 76 { 77 Delete(rt[x], 1, cnt, c); 78 Insert(rt[x], 1, cnt, v); 79 x += x & (-x); 80 } 81 } 82 int Query(int l, int r, int x) 83 { 84 if(l == r) return l; 85 int mid = l + r >> 1; 86 int amo = 0; 87 for(int i = 1; i <= nu; ++i) amo += sum[lc[u[i]]]; 88 for(int i = 1; i <= nv; ++i) amo -= sum[lc[v[i]]]; 89 if(amo >= x) 90 { 91 for(int i = 1; i <= nu; ++i) u[i] = lc[u[i]]; 92 for(int i = 1; i <= nv; ++i) v[i] = lc[v[i]]; 93 return Query(l, mid, x); 94 } 95 else 96 { 97 for(int i = 1; i <= nu; ++i) u[i] = rc[u[i]]; 98 for(int i = 1; i <= nv; ++i) v[i] = rc[v[i]]; 99 return Query(mid + 1, r, x - amo);100 }101 }102 inline int Ask(int l, int r, int k)103 {104 int x = l - 1;105 nu = nv = 0;106 while(x)107 {108 v[++nv] = rt[x];109 x -= x & (-x);110 }111 x = r;112 while(x)113 {114 u[++nu] = rt[x];115 x -= x & (-x);116 }117 return disc[Query(1, cnt, k)];118 }119 void Print(int k, int l, int r)120 {121 if(!sum[k]) return;122 int mid = l + r >> 1;123 Print(lc[k], l, mid);124 printf("k=%d l=%d r=%d lc=%d rc=%d sum=%d\n", k, l, r, lc[k], rc[k], sum[k]);125 Print(rc[k], mid + 1, r);126 }127 int main()128 {129 Scan(n), Scan(m);130 for(int i = 1; i <= n; ++i)131 {132 Scan(val[i]);133 disc[++num] = val[i];134 }135 for(int i = 1; i <= m; ++i)136 {137 scanf("%s", s);138 a[i].c = s[0];139 if(a[i].c == 'C') Scan(a[i].l), Scan(a[i].k), disc[++num] = a[i].k;140 else Scan(a[i].l), Scan(a[i].r), Scan(a[i].k);141 }142 Disc();143 for(int i = 1; i <= n; ++i)144 {145 int x = Get(val[i]);146 Add(i, x);147 }148 for(int i = 1; i <= m; ++i)149 {150 int l = a[i].l, r = a[i].r, k = a[i].k;151 if(a[i].c == 'C') Change(l, Get(val[l]), Get(k)), val[l] = k;152 else printf("%d\n", Ask(l, r, k));153 }154 }