Description
给定一个含有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，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。
（带修改的区间第K小）
Input
第一行有两个正整数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。
Output
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Sample Input
5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3
Sample Output
3 6
HINT
20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中，m,n≤10000。
分析：
求出区间第K小要用到可持久化线段树，最重要的一个思想就是区间加减法。
我们可以这样想，如果求的是区间的和，在不修改的情况下，每一个数对应线段树的版本是根据前一个数的版本创建的，这就相对于做前缀和。显然前缀和不支持修改，但是我们不难想到支持修改的数据结构——树状数组。
按树状数组修改和查询前缀和的方式来更新线段树的版本，以及查询左子树内数的个数之和，就可以解决我们的问题了。
代码：
1 #include2 #include 3 4 const int maxn = 25000; 5 const int maxm = 5000000; 6 7 int ch[maxm][2], cnt[maxm], root[maxn], size; 8 int n, m, tmp, num[maxn], id[maxn], back[maxn]; 9 int d[maxn], now[2][maxn], p1, p2;10 //d表示某数字在所有数字中第几小11 int a[maxn], act_i[maxn], act_j[maxn], act_k[maxn];12 char act[3];13 14 inline int lowbit (int x)15 {16 return x & (-x);17 }18 19 #define MID (left + right >> 1)20 21 int modify (int left, int right, int pos, int data, int prev)22 {23 int i = ++size;24 if (left < right)25 {26 int c = pos > MID;27 ch[i][!c] = ch[prev][!c];28 c ? left = MID + 1 : right = MID;29 ch[i][c] = modify (left, right, pos, data, ch[prev][c]);30 cnt[i] = cnt[ch[i][0]] + cnt[ch[i][1]];31 }else cnt[i] = cnt[prev] + data;32 return i;33 }34 35 int query (int left, int right, int k)36 {37 if (left == right) return num[id[left]];38 int sum = 0;39 for (int i = 0; i < p2; i++) sum += cnt[ch[now[1][i]][0]];40 for (int i = 0; i < p1; i++) sum -= cnt[ch[now[0][i]][0]];41 int c = (k > sum); c ? left = MID + 1 : right = MID;42 for (int i = 0; i < p2; i++) now[1][i] = ch[now[1][i]][c];43 for (int i = 0; i < p1; i++) now[0][i] = ch[now[0][i]][c];44 return query (left, right, c ? k - sum : k);45 }46 47 int ask (int l, int r, int k)48 {49 p1 = p2 = 0;50 for (int i = l; i > 0; i -= lowbit (i)) now[0][p1++] = root[i];51 for (int i = r; i > 0; i -= lowbit (i))52 {53 now[1][p2++] = root[i];54 }55 return query (1, n, k);56 }57 58 bool cmp (int a, int b)59 {60 return num[a] < num[b];61 }62 63 int main ()64 {65 scanf ("%d %d", &n, &m);66 for (int i = 1; i <= n; i++)67 scanf ("%d", &num[i]), id[i] = i;68 for (int i = 0; i < m; i++)69 {70 scanf ("%s", act);71 if (act[0] == 'C')72 {73 a[i] = 0, act_j[i] = ++n, id[n] = n;74 scanf ("%d %d", &act_i[i], &num[n]);75 }else 76 {77 a[i] = 1;78 scanf ("%d %d %d", &act_i[i], &act_j[i], &act_k[i]);79 }80 }81 std::sort (id + 1, id + n + 1, cmp);82 for (int i = 1; i <= n; i++)83 d[id[i]] = back[id[i]] = i;84 for (int i = 1; i <= n; i++)85 for (int j = i; j <= n; j += lowbit (j))86 root[j] = modify (1, n, d[i], 1, root[j]);87 for (int i = 0; i < m; i++)88 {89 if (a[i] == 0)90 {91 tmp = d[act_i[i]], d[act_i[i]] = back[act_j[i]];92 for (int j = act_i[i]; j <= n; j += lowbit (j))93 {94 root[j] = modify (1, n, tmp, -1, root[j]);95 root[j] = modify (1, n, d[act_i[i]], 1, root[j]);96 }97 }else printf ("%d\n", ask (act_i[i] - 1, act_j[i], act_k[i]));98 }99 }