zoj 2112 Dynamic Rankings，zojrankings
原題鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1112
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #define lc root<<1
6 #define rc root<<1|1
7 #define INF 0x3f3f3f3f
8 const int Max_N = 50010;
9 struct SBT{
10 int key, size, cnt;
11 SBT *ch[2];
12 inline void push_up(){
13 size = ch[0]->size + ch[1]->size + cnt;
14 }
15 int cmp(int v) const{
16 if (v == key) return -1;
17 return v > key;
18 }
19 }*null, stack[Max_N * 18], *ptr[Max_N << 2];
20 int sz = 0, sum = 0, arr[Max_N];
21 void init(){
22 null = &stack[sz++];
23 null->key = null->size = null->cnt = 0;
24 }
25 void rotate(SBT* &x, int d){
26 SBT *k = x->ch[!d];
27 x->ch[!d] = k->ch[d];
28 k->ch[d] = x;
29 k->size = x->size;
30 x->push_up();
31 x = k;
32 }
33 void Maintain(SBT* &x, int d){
34 if (x->ch[d] == null) return;
35 if (x->ch[d]->ch[d]->size > x->ch[!d]->size){
36 rotate(x, !d);
37 } else if (x->ch[d]->ch[!d]->size > x->ch[!d]->size){
38 rotate(x->ch[d], d), rotate(x, !d);
39 } else {
40 return;
41 }
42 Maintain(x, 0), Maintain(x, 1);
43 }
44 void insert(SBT* &x, int key){
45 if (x == null){
46 x = &stack[sz++];
47 x->ch[0] = x->ch[1] = null;
48 x->key = key, x->size = x->cnt = 1;
49 } else {
50 int d = x->cmp(key);
51 x->size++;
52 if (-1 == d){
53 x->cnt++;
54 return;
55 }
56 insert(x->ch[d], key);
57 x->push_up();
58 Maintain(x, d);
59 }
60 }
61 void del(SBT* &x, int key){
62 if (x == null) return;
63 int d = x->cmp(key);
64 x->size--;
65 if (-1 == d){
66 if (x->cnt > 1){
67 x->cnt--;
68 } else if (x->ch[0] == null || x->ch[1] == null){
69 x = x->ch[0] != null ? x->ch[0] : x->ch[1];
70 } else {
71 SBT *ret = x->ch[1];
72 for (; ret->ch[0] != null; ret = ret->ch[0]);
73 del(x->ch[1], x->key = ret->key);
74 }
75 } else {
76 del(x->ch[d], key);
77 }
78 if (x != null) x->push_up();
79 }
80 int sbt_rank(SBT *x, int key){
81 int t, cur;
82 for (t = cur = 0; x != null;){
83 t = x->ch[0]->size;
84 if (key < x->key) x = x->ch[0];
85 else if (key >= x->key) cur += x->cnt + t, x = x->ch[1];
86 }
87 return cur;
88 }
89 void seg_built(int root, int l, int r){
90 for (int i = l; i <= r; i++) insert(ptr[root], arr[i]);
91 if (l == r) return;
92 int mid = (l + r) >> 1;
93 seg_built(lc, l, mid);
94 seg_built(rc, mid + 1, r);
95 }
96 void seg_query(int root, int l, int r, int x, int y, int val){
97 if (x > r || y < l) return;
98 if (x <= l && y >= r){
99 sum += sbt_rank(ptr[root], val);
100 return;
101 }
102 int mid = (l + r) >> 1;
103 seg_query(lc, l, mid, x, y, val);
104 seg_query(rc, mid + 1, r, x, y, val);
105 }
106 void seg_del(int root, int l, int r, int pos, int val){
107 if (pos > r || pos < l) return;
108 del(ptr[root], val);
109 if (l == r) return;
110 int mid = (l + r) >> 1;
111 seg_del(lc, l, mid, pos, val);
112 seg_del(rc, mid + 1, r, pos, val);
113 }
114 void seg_insert(int root, int l, int r, int pos, int val) {
115 if (pos > r || pos < l) return;
116 insert(ptr[root], val);
117 if (l == r) return;
118 int mid = (l + r) >> 1;
119 seg_insert(lc, l, mid, pos, val);
120 seg_insert(rc, mid + 1, r, pos, val);
121 }
122 void gogo(int n, int a, int b, int k){
123 int l = 0, r = INF;
124 while (l < r){
125 sum = 0;
126 int mid = (l + r) >> 1;
127 seg_query(1, 1, n, a, b, mid);
128 if (sum < k) l = mid + 1;
129 else r = mid;
130 }
131 printf("%d\n", l);
132 }
133 int main(){
134 #ifdef LOCAL
135 freopen("in.txt", "r", stdin);
136 freopen("out.txt", "w+", stdout);
137 #endif
138 char ch;
139 int t, n, m, a, b, k;
140 scanf("%d", &t);
141 while (t--){
142 sz = 0, init();
143 scanf("%d %d", &n, &m);
144 for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
145 std::fill(ptr, ptr + (n << 2), null);
146 seg_built(1, 1, n);
147 while (m--){
148 getchar();
149 scanf("%c", &ch);
150 if (ch == 'Q'){
151 scanf("%d %d %d", &a, &b, &k);
152 gogo(n, a, b, k);
153 }
154 else {
155 scanf("%d %d", &a, &b);
156 seg_del(1, 1, n, a, arr[a]);
157 seg_insert(1, 1, n, a, arr[a] = b);
158 }
159 }
160 }
161 return 0;
162 }
View Code
