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套可持久化线段树。
/* ***********************************************
Author :111qqz
Created Time :2017年10月16日 星期一 23时50分14秒
File Name :1901.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N = 2E5+7;
7int n,m;
8int a[N],H[N];
9int root[N];
10int cnt,p[2];
11int num;
12int prefix_l[100],prefix_r[100];
1struct node
2{
3 int a,b,c;
4 char opt[3];
5}querys[N];
6struct PTree
7{
8 int sum;
9 int left,right;
10}tree[N*30];
11int Hash( int x){ return lower_bound(H+1,H+num+1,x)-H;}
12inline int lowbit( int x) { return x&(-x);}
13inline int add_node( int _sum,int _left,int _right)
14{
15 int idx = ++cnt;
16 tree[idx].sum = _sum;
17 tree[idx].left = _left;
18 tree[idx].right = _right;
19 return idx;
20}
21void build( int &root,int pre_rt,int pos,int l,int r)
22{
23 root = add_node(tree[pre_rt].sum+1,tree[pre_rt].left,tree[pre_rt].right);
24 if (l==r) return;
25 int mid = (l+r)>>1;
26 if (pos<=mid)
27 build(tree[root].left,tree[root].left,pos,l,mid);
28 else
29 build(tree[root].right,tree[root].right,pos,mid+1,r);
30}
31void Insert( int &root,int pos,int l,int r,int val)
32{
33 if (!root) root = add_node(0,0,0);
34 tree[root].sum += val;
35 if (l==r) return;
36 int mid = (l+r)>>1;
37 if (pos<=mid)
38 Insert(tree[root].left,pos,l,mid,val);
39 else
40 Insert(tree[root].right,pos,mid+1,r,val);
41}
42int query(int l,int r,int k)
43{
44 if (l==r) return l;
45 int mid = (l+r)>>1,sum=0;
46 for ( int i = 0 ; i < p[0] ; i++)
47 sum += tree[tree[prefix_r[i]].left].sum;
48 for ( int i = 0 ; i < p[1] ; i++)
49 sum -= tree[tree[prefix_l[i]].left].sum;
50 if (k<=sum)
51 {
52 for (int i = 0 ; i < p[0] ; i++)
53 prefix_r[i] = tree[prefix_r[i]].left;
54 for ( int i = 0 ; i < p[1] ; i++)
55 prefix_l[i] = tree[prefix_l[i]].left;
56 return query(l,mid,k);
57 }
58 else
59 {
60 for ( int i = 0 ; i < p[0] ; i++)
61 prefix_r[i] = tree[prefix_r[i]].right;
62 for ( int i = 0 ; i < p[1] ; i++)
63 prefix_l[i] = tree[prefix_l[i]].right;
64 return query(mid+1,r,k-sum);
65 }
66}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6 scanf("%d %d",&n,&m);
7 int p_val = n;
8 ms(root,0);
9 for ( int i = 1 ; i <= n ; i++) scanf("%d",a+i),H[i] = a[i];
10 cnt = 0;
11 for ( int i = 0 ; i < m; i++) //读入所有操作是为了离散化
12 {
13 scanf("%s %d %d",querys[i].opt,&querys[i].a,&querys[i].b);
14 if (querys[i].opt[0]=='Q') scanf("%d",&querys[i].c);
15 else H[++p_val] = querys[i].b;
16 }
17 sort(H+1,H+p_val+1);
18 num = unique(H+1,H+p_val+1)-(H+1);
19 for ( int i = 1 ; i <= n ; i++)
20 {
21 a[i] = Hash(a[i]);
22 }
23// for ( int i = 1 ; i <= n ; i++) printf("a[%d]=%d\n",i,a[i]);
24 for ( int i = 1 ; i <= n ; i++)
25 {
26 build(root[i+n],root[(i-1)+n],a[i],1,num);
27 }
28 for ( int i = 0 ; i < m ; i++)
29 {
30 if (querys[i].opt[0]=='Q')
31 {
32 p[0] = p[1] = 1;
33 prefix_r[0] = root[querys[i].b + n];
34 prefix_l[0] = root[querys[i].a-1==0?0:querys[i].a-1+n];
35 for ( int arr = querys[i].b; arr ; arr-=lowbit(arr))
36 prefix_r[p[0]++] = root[arr];
37 for ( int arr = querys[i].a-1 ; arr ; arr-=lowbit(arr))
38 prefix_l[p[1]++] = root[arr];
39 int id = query(1,num,querys[i].c);
40 printf("%d\n",H[id]);
41 }
42 else
43 {
44 for ( int j = querys[i].a ; j <= n ; j+=lowbit(j))
45 Insert(root[j],a[querys[i].a],1,num,-1);
46 a[querys[i].a] = Hash(querys[i].b);
47 for ( int j = querys[i].a ; j <= n ; j+=lowbit(j))
48 Insert(root[j],a[querys[i].a],1,num,1);
49 }
50 }
51 #ifndef ONLINE_JUDGE
52 fclose(stdin);
53 #endif
54 return 0;
55}