首页 > 代码库 > ZOJ2112--Dynamic Rankings (动态区间第k大)

ZOJ2112--Dynamic Rankings (动态区间第k大)

Dynamic Rankings

Time Limit: 10 Seconds      Memory Limit: 32768 KB

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

主席树动态第k大基本可以手写,,但是感觉理解还不是很深。另外定义两个数组,一个用来新建一颗主席树,所有修改的结果都在这个上面进行,而另一个是记录中间值,相当于temp的效果,不改变原始数组。。(挖个坑)

附主席树专题链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=63941#overview

  1 #include <cstdio>  2 #include <cstdlib>  3 #include <cstring>  4 #include <algorithm>  5 #include <iostream>  6 using namespace std;  7 typedef long long ll;  8 const int maxn = 5e4+10;  9 int n,m,tot,idx; 10 ll a[maxn],vec[maxn*2]; 11 struct 12 { 13     int x,y,k,flag,idx; 14 } Q[maxn]; 15  16 //   主席树 17 int lson[maxn*50],rson[maxn*50],c[maxn*50],root[maxn]; //依次为左儿子 右儿子 线段树  根节点 18 int build (int l,int r) 19 { 20     int root = tot++; 21     c[root] = 0; 22     if (l != r) 23     { 24         int mid = (l + r) >> 1; 25         lson[root] = build(l,mid); 26         rson[root] = build(mid+1,r); 27     } 28     return root; 29 } 30 int update(int root,int pos,int val) 31 { 32     int new_root = tot++; 33     int tmp = new_root; 34     int l = 1,r = idx; 35     c[new_root] = c[root] + val; 36     while (l < r) 37     { 38         int mid = (l + r) >> 1; 39         if (pos <= mid) 40         { 41             rson[new_root] = rson[root]; 42             root = lson[root]; 43             lson[new_root] = tot++; 44             new_root = lson[new_root]; 45             r = mid; 46         } 47         else 48         { 49             lson[new_root] = lson[root]; 50             root = rson[root]; 51             rson[new_root] = tot++; 52             new_root = rson[new_root]; 53             l = mid + 1; 54         } 55         c[new_root] = c[root] + val; 56     } 57     return tmp; 58 } 59 //  树状数组维护 60 int s[maxn],use[maxn]; 61 inline int lowbit (int x) 62 { 63     return x & -x; 64 } 65 void add(int k,int pos,int d) 66 { 67     while (k <= n) 68     { 69         s[k] = update(s[k],pos,d); 70         k += lowbit(k); 71     } 72 } 73 int sum(int pos) 74 { 75     int res = 0; 76     while (pos) 77     { 78         res += c[lson[use[pos]]]; 79         pos -= lowbit(pos); 80     } 81     return res; 82 } 83 int query(int left,int right,int k) 84 { 85     int l_root = root[left-1]; 86     int r_root = root[right]; 87     for (int i = left-1; i > 0; i -= lowbit(i)) 88         use[i] = s[i]; 89     for (int i = right; i > 0; i -= lowbit(i)) 90         use[i] =s[i]; 91     int l = 1,r = idx; 92     while (l < r) 93     { 94         int t = sum(right) - sum(left-1) + c[lson[r_root]] - c[lson[l_root]]; 95         int mid = (l + r) >> 1; 96         if (t >= k) 97         { 98             for (int i = left-1; i > 0; i -= lowbit(i)) 99                 use[i] = lson[use[i]];100             for (int i = right; i > 0; i -= lowbit(i))101                 use[i] = lson[use[i]];102             l_root = lson[l_root];103             r_root = lson[r_root];104             r = mid;105         }106         else107         {108             for (int i = left-1; i > 0; i -= lowbit(i))109                 use[i] = rson[use[i]];110             for (int i = right; i > 0; i -= lowbit(i))111                 use[i] = rson[use[i]];112             l_root = rson[l_root];113             r_root = rson[r_root];114             k -= t;115             l = mid + 1;116         }117     }118     return l;119 }120 121 void read()122 {123     scanf ("%d%d",&n,&m);124     for (int i = 1; i <= n; i++)125     {126         scanf ("%lld",a+i);127         vec[idx++] = a[i];128     }129     for (int i = 0; i < m; i++)130     {131         char op[3];132         scanf ("%s",op);133         if (op[0] == C)134         {135             scanf ("%d%d",&Q[i].x,&Q[i].y);136             Q[i].flag = 0;137             vec[idx++] = Q[i].y;138         }139         if (op[0] == Q)140         {141             scanf ("%d%d%d",&Q[i].x,&Q[i].y,&Q[i].k);142             Q[i].flag = 1;143         }144     }145 }146 int main(void)147 {148 #ifndef ONLINE_JUDGE149     freopen("in.txt","r",stdin);150 #endif151     int T;152     scanf ("%d",&T);153     while (T--)154     {155         idx = tot = 0;156         read();157         sort(vec,vec+idx);                   //离散化158         idx = unique(vec,vec+idx) - vec;159         root[0] = build(1,idx);160         for (int i = 1; i <= n; i++)161         {162             int tmp = lower_bound(vec,vec+idx,a[i]) - vec ;163             root[i] = update(root[i-1],tmp,1);164         }165         for (int i = 0; i <= n; i++)166             s[i] = root[0];167         for (int i = 0; i < m; i++)168         {169             if (Q[i].flag == 0)170             {171                 int tmp1 = lower_bound(vec,vec+idx,a[Q[i].x]) - vec ;172                 int tmp2 = lower_bound(vec,vec+idx,Q[i].y) - vec ;173                 add(Q[i].x,tmp1,-1);174                 add(Q[i].x,tmp2,1);175                 a[Q[i].x] = Q[i].y;176             }177             if (Q[i].flag == 1)178             {179                 printf("%lld\n",vec[query(Q[i].x,Q[i].y,Q[i].k)]);180             }181         }182     }183     return 0;184 }

 

ZOJ2112--Dynamic Rankings (动态区间第k大)