The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There're NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])
There're NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
树套树做的真是excited。
比较难理解的就是要把树状数组里面的元素看出一棵树，虽然这句话看着很好懂，但实际上码代码是必须时时提醒自己，否则太容易写错了。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 using namespace std; 6 const int N = 50000 + 11 , M = 10000 + 11 ; 7 struct node 8 { 9 int sum ; 10 int l , r; 11 12 } tree[N*40] ; 13 int bit[N] ,root[N] , use[N] , tot; 14 int t , n , m , cnt , a[N], b[N+M]; 15 struct id 16 { 17 bool op; 18 int l , r , k ; 19 } que[M] ; 20 21 void Init( ) 22 { 23 cnt = root[0] = root[1] = tot = 0 ; 24 scanf("%d%d",&n,&m); 25 for(int x = 1 ; x <= n ; ++x) scanf("%d",a+x) , b[x] = a[x]; 26 char ch[3]; tot = n ; 27 for( int x = 1 ; x <= m ; ++x ) 28 { 29 scanf("%s",ch); 30 if(ch[0] == 'Q') que[x].op = false , scanf("%d%d%d",&que[x].l,&que[x].r,&que[x].k); 31 else 32 que[x].op = true , scanf("%d%d",&que[x].l,&que[x].k) , b[++tot] = que[x].k; 33 } 34 sort(b + 1 , b + 1 + tot); 35 int now = tot ; tot = 1 ; 36 for( int x = 2 ; x <= now ; ++x ) if( b[x] != b[tot] ) b[++tot] = b[x]; 37 } 38 39 int binary_search( int num ) 40 { 41 int l = 1 , r = tot ; 42 while( l <= r ) 43 { 44 int mid = l + ((r-l)>>1); 45 if( b[mid] == num ) return mid; 46 if( b[mid] < num ) l = mid + 1 ; 47 else r = mid - 1; 48 } 49 return -1; 50 } 51 52 void updata( int l , int r , int &x , int y , int pos , int c ) 53 { 54 tree[++cnt] = tree[y] , x = cnt , tree[cnt].sum += c ; 55 if( l == r ) return ; 56 int mid = l + ((r-l)>>1); 57 if( pos <= mid ) updata(l,mid,tree[x].l,tree[y].l,pos,c); 58 else updata(mid+1,r,tree[x].r,tree[y].r,pos,c); 59 } 60 61 int lowbit( int x ) { return x & -x; } 62 63 int Sum( int x ) 64 { 65 int ret = 0 ; 66 for( int i = x ; i > 0 ; i -= lowbit(i)) ret += tree[tree[use[i]].l].sum; 67 return ret ; 68 } 69 70 int queryf(int l,int r,int k) 71 { 72 int L = 1 , R = tot , root_l = root[l] , root_r = root[r]; 73 for(int i = l ; i; i -= lowbit(i) ) use[i] = bit[i]; 74 for(int i = r ; i; i -= lowbit(i)) use[i] = bit[i] ; 75 while(L <= R) 76 { 77 if( L == R ) return L ; 78 int mid = L+((R-L)>>1); 79 int tmp = Sum(r) - Sum(l) + tree[tree[root_r].l].sum - tree[tree[root_l].l].sum; 80 if(tmp >= k) 81 { 82 R = mid; 83 for(int i = l ; i ; i -= lowbit(i) ) use[i] = tree[use[i]].l ; 84 for(int i = r; i ; i -= lowbit(i)) use[i] = tree[use[i]].l; 85 root_l = tree[root_l].l , root_r = tree[root_r].l; 86 } 87 else 88 { 89 L = mid + 1 ; 90 for(int i = l ; i ; i -= lowbit(i)) use[i] = tree[use[i]].r; 91 for(int i = r ; i ; i -= lowbit(i)) use[i] = tree[use[i]].r; 92 k -= tmp; root_l = tree[root_l].r , root_r = tree[root_r].r; 93 } 94 } 95 96 } 97 98 void insert( int x , int pos, int c ) 99 { 100 for( int i = x ; i <= n; i += lowbit(i) ) 101 updata(1,tot,bit[i],bit[i],pos,c); 102 } 103 104 void Solve( ) 105 { 106 for( int x = 1 ; x <= n ; ++x ) updata( 1 , tot , root[x] , root[x-1] , binary_search(a[x]) , 1 ) ; 107 for(int i = 1; i <= n; i++) bit[i] = root[0]; 108 for( int x = 1 ; x <= m ; ++x ) 109 { 110 if(!que[x].op) printf("%d ",b[queryf(que[x].l - 1 , que[x].r , que[x].k)]) ; 111 else 112 { 113 insert(que[x].l,binary_search(a[que[x].l]),-1); 114 insert(que[x].l,binary_search(que[x].k),1); 115 a[que[x].l] = que[x].k; 116 } 117 } 118 } 119 120 int main() 121 { 122 scanf("%d",&t); 123 while(t--) 124 { 125 Init(); 126 Solve(); 127 } 128 return 0; 129 }