bzoj 1901: Zju2112 Dynamic Rankings (可持久化线段树，区间动态第k大)
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继续回答上面的问题。
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
m,n≤10000
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
思路：
现在我们已经会了用可持久化线段树，去做静态区间第k大的问题。
考虑一次修改，修改的元素会影响后面所有建好的线段树，时间代价是无法承受的。
我们考虑root[i]表示的这颗线段树，它保存的是从第一个元素开始插入到第i个元素后的数字区间。也就是说每次我们进行线段树区间相减时，我们是对两个前缀和[1, l - 1]和[1, r]进行了相减。
所以我们需要的是，以一个可以接受的时间代价，维护一个前缀和。
显然是用BIT来维护。
所以带修改的可持久化线段树，本质上应该是BIT套可持久化线段树。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月16日 星期一 23时50分14秒
4File Name :1901.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N = 2E5+7;
35int n,m;
36int a[N],H[N];
37int root[N];
38int cnt,p[2];
39int num;
40int prefix_l[100],prefix_r[100];
41
42struct node
43{
44 int a,b,c;
45 char opt[3];
46}querys[N];
47struct PTree
48{
49 int sum;
50 int left,right;
51}tree[N*30];
52int Hash( int x){ return lower_bound(H+1,H+num+1,x)-H;}
53inline int lowbit( int x) { return x&(-x);}
54inline int add_node( int _sum,int _left,int _right)
55{
56 int idx = ++cnt;
57 tree[idx].sum = _sum;
58 tree[idx].left = _left;
59 tree[idx].right = _right;
60 return idx;
61}
62void build( int &root,int pre_rt,int pos,int l,int r)
63{
64 root = add_node(tree[pre_rt].sum+1,tree[pre_rt].left,tree[pre_rt].right);
65 if (l==r) return;
66 int mid = (l+r)>>1;
67 if (pos<=mid)
68 build(tree[root].left,tree[root].left,pos,l,mid);
69 else
70 build(tree[root].right,tree[root].right,pos,mid+1,r);
71}
72void Insert( int &root,int pos,int l,int r,int val)
73{
74 if (!root) root = add_node(0,0,0);
75 tree[root].sum += val;
76 if (l==r) return;
77 int mid = (l+r)>>1;
78 if (pos<=mid)
79 Insert(tree[root].left,pos,l,mid,val);
80 else
81 Insert(tree[root].right,pos,mid+1,r,val);
82}
83int query(int l,int r,int k)
84{
85 if (l==r) return l;
86 int mid = (l+r)>>1,sum=0;
87 for ( int i = 0 ; i < p[0] ; i++)
88 sum += tree[tree[prefix_r[i]].left].sum;
89 for ( int i = 0 ; i < p[1] ; i++)
90 sum -= tree[tree[prefix_l[i]].left].sum;
91 if (k<=sum)
92 {
93 for (int i = 0 ; i < p[0] ; i++)
94 prefix_r[i] = tree[prefix_r[i]].left;
95 for ( int i = 0 ; i < p[1] ; i++)
96 prefix_l[i] = tree[prefix_l[i]].left;
97 return query(l,mid,k);
98 }
99 else
100 {
101 for ( int i = 0 ; i < p[0] ; i++)
102 prefix_r[i] = tree[prefix_r[i]].right;
103 for ( int i = 0 ; i < p[1] ; i++)
104 prefix_l[i] = tree[prefix_l[i]].right;
105 return query(mid+1,r,k-sum);
106 }
107}
108
109int main()
110{
111 #ifndef ONLINE_JUDGE
112 freopen("./in.txt","r",stdin);
113 #endif
114 scanf("%d %d",&n,&m);
115 int p_val = n;
116 ms(root,0);
117 for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i),H[i] = a[i];
118 cnt = 0;
119 for ( int i = 0 ; i < m; i++) //读入所有操作是为了离散化
120 {
121 scanf("%s %d %d",querys[i].opt,&querys[i].a,&querys[i].b);
122 if (querys[i].opt[0]=='Q') scanf("%d",&querys[i].c);
123 else H[++p_val] = querys[i].b;
124 }
125 sort(H+1,H+p_val+1);
126 num = unique(H+1,H+p_val+1)-(H+1);
127 for ( int i = 1 ; i <= n ; i++)
128 {
129 a[i] = Hash(a[i]);
130 }
131// for ( int i = 1 ; i <= n ; i++) printf("a[%d]=%d\n",i,a[i]);
132 for ( int i = 1 ; i <= n ; i++)
133 {
134 build(root[i+n],root[(i-1)+n],a[i],1,num);
135 }
136 for ( int i = 0 ; i < m ; i++)
137 {
138 if (querys[i].opt[0]=='Q')
139 {
140 p[0] = p[1] = 1;
141 prefix_r[0] = root[querys[i].b + n];
142 prefix_l[0] = root[querys[i].a-1==0?0:querys[i].a-1+n];
143 for ( int arr = querys[i].b; arr ; arr-=lowbit(arr))
144 prefix_r[p[0]++] = root[arr];
145 for ( int arr = querys[i].a-1 ; arr ; arr-=lowbit(arr))
146 prefix_l[p[1]++] = root[arr];
147 int id = query(1,num,querys[i].c);
148 printf("%d\n",H[id]);
149 }
150 else
151 {
152 for ( int j = querys[i].a ; j <= n ; j+=lowbit(j))
153 Insert(root[j],a[querys[i].a],1,num,-1);
154 a[querys[i].a] = Hash(querys[i].b);
155 for ( int j = querys[i].a ; j <= n ; j+=lowbit(j))
156 Insert(root[j],a[querys[i].a],1,num,1);
157 }
158 }
159 #ifndef ONLINE_JUDGE
160 fclose(stdin);
161 #endif
162 return 0;
163}