首页 > 代码库 > SPOJ ORDERSET - Order statistic set
SPOJ ORDERSET - Order statistic set
ORDERSET - Order statistic set
In this problem, you have to maintain a dynamic set of numbers which support the two fundamental operations
- INSERT(S,x): if x is not in S, insert x into S
- DELETE(S,x): if x is in S, delete x from S
and the two type of queries
- K-TH(S) : return the k-th smallest element of S
- COUNT(S,x): return the number of elements of S smaller than x
Input
- Line 1: Q (1 ≤ Q ≤ 200000), the number of operations
- In the next Q lines, the first token of each line is a character I, D, K or C meaning that the corresponding operation is INSERT, DELETE, K-TH or COUNT, respectively, following by a whitespace and an integer which is the parameter for that operation.
If the parameter is a value x, it is guaranteed that 0 ≤ |x| ≤ 109. If the parameter is an index k, it is guaranteed that 1 ≤ k ≤ 109.
Output
For each query, print the corresponding result in a single line. In particular, for the queries K-TH, if k is larger than the number of elements in S, print the word ‘invalid‘.
Example
Input 8 I -1 I -1 I 2 C 0 K 2 D -1 K 1 K 2 Output 1 2 2 invalid
Submit solution!
分析
可以用Treap做,也可以Splay什么的,先用权值线段树水一水,再用Treap水一水。
代码
权值线段树
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7 8 using namespace std; 9 10 #define N 200005 11 12 struct node 13 { 14 int lt, rt, cnt; 15 }tree[N << 2]; 16 17 void build(int p, int l, int r) 18 { 19 node &t = tree[p]; 20 21 t.lt = l; 22 t.rt = r; 23 t.cnt = 0; 24 25 if (l == r) 26 return; 27 28 int mid = (l + r) >> 1; 29 30 build(p << 1, l, mid); 31 build(p << 1 | 1, mid + 1, r); 32 } 33 34 void insert(int p, int pos, int val) 35 { 36 node &t = tree[p]; 37 38 t.cnt += val; 39 40 if (t.lt == t.rt) 41 return; 42 43 int mid = (t.lt + t.rt) >> 1; 44 45 if (pos <= mid) 46 insert(p << 1, pos, val); 47 else 48 insert(p << 1 | 1, pos, val); 49 } 50 51 int query(int p, int l, int r) 52 { 53 if (l > r)return 0; 54 55 node &t = tree[p]; 56 57 if (t.lt == l && t.rt == r) 58 return t.cnt; 59 60 int mid = (t.lt + t.rt) >> 1; 61 62 if (r <= mid) 63 return query(p << 1, l, r); 64 if (l > mid) 65 return query(p << 1 | 1, l, r); 66 return query(p << 1, l, mid) + query(p << 1 | 1, mid + 1, r); 67 } 68 69 int rnk(int p, int rk) 70 { 71 node &t = tree[p]; 72 73 if (t.lt == t.rt) 74 return t.lt; 75 76 if (tree[p << 1].cnt >= rk) 77 return rnk(p << 1, rk); 78 79 else 80 return rnk(p << 1 | 1, rk - tree[p << 1].cnt); 81 } 82 83 int n; 84 int a[N]; 85 int b[N]; 86 87 char s[N][5]; 88 89 signed main(void) 90 { 91 scanf("%d", &n); 92 93 for (int i = 1; i <= n; ++i) 94 scanf("%s%d", s[i], &a[i]); 95 96 memcpy(b, a, sizeof(b)); 97 98 sort(b + 1, b + 1 + n); 99 100 int m = unique(b + 1, b + 1 + n) - b; 101 102 build(1, 1, m); 103 104 for (int i = 1; i <= n; ++i)if (s[i][0] != ‘K‘) 105 a[i] = lower_bound(b + 1, b + m, a[i]) - b; 106 107 for (int i = 1; i <= n; ++i) 108 { 109 char &c = s[i][0]; 110 111 if (c == ‘I‘) 112 { 113 if (!query(1, a[i], a[i])) 114 insert(1, a[i], 1); 115 } 116 else if (c == ‘D‘) 117 { 118 if (query(1, a[i], a[i])) 119 insert(1, a[i], -1); 120 } 121 else if (c == ‘K‘) 122 { 123 if (query(1, 1, m) >= a[i]) 124 printf("%d\n", b[rnk(1, a[i])]); 125 else printf("invalid\n"); 126 } 127 else if (c == ‘C‘) 128 { 129 printf("%d\n", query(1, 1, a[i] - 1)); 130 } 131 } 132 }
Treap
1 #include <bits/stdc++.h> 2 3 class treap 4 { 5 private: 6 7 struct node 8 { 9 int key; 10 int tag; 11 int siz; 12 node *lson; 13 node *rson; 14 node(int k = 0, int t = rand()) : 15 key(k), tag(t), siz(1), lson(0), rson(0) {}; 16 }; 17 18 int getSize(node *&t) 19 { 20 if (t == NULL)return 0; 21 t->siz = 1; 22 if (t->lson) 23 t->siz += t->lson->siz; 24 if (t->rson) 25 t->siz += t->rson->siz; 26 return t->siz; 27 } 28 29 void rotateLeft(node *&t) 30 { 31 node *r = t->rson; 32 t->rson = r->lson; 33 r->lson = t; 34 getSize(t); 35 getSize(r); 36 t = r; 37 } 38 39 void rotateRight(node *&t) 40 { 41 node *l = t->lson; 42 t->lson = l->rson; 43 l->rson = t; 44 getSize(t); 45 getSize(l); 46 t = l; 47 } 48 49 void insertNode(node *&t, int k) 50 { 51 if (t == NULL) 52 t = new node(k); 53 else 54 { 55 if (k < t->key) 56 { 57 insertNode(t->lson, k); 58 if (t->lson->tag > t->tag) 59 rotateRight(t); 60 } 61 else if (k > t->key) 62 { 63 insertNode(t->rson, k); 64 if (t->rson->tag > t->tag) 65 rotateLeft(t); 66 } 67 } 68 getSize(t); 69 } 70 71 void deleteNode(node *&t) 72 { 73 if (t->lson == NULL) 74 t = t->rson; 75 else if (t->rson == NULL) 76 t = t->lson; 77 else 78 { 79 if (t->lson->tag > t->rson->tag) 80 rotateRight(t), deleteNode(t->rson); 81 else 82 rotateLeft(t), deleteNode(t->lson); 83 } 84 getSize(t); 85 } 86 87 void deleteNode(node *&t, int k) 88 { 89 if (t != NULL) 90 { 91 if (k == t->key) 92 deleteNode(t); 93 else if (k < t->key) 94 deleteNode(t->lson, k); 95 else 96 deleteNode(t->rson, k); 97 getSize(t); 98 } 99 } 100 101 node *findElement(node *&t, int k) 102 { 103 if (k == t->key) 104 return t; 105 else if (k < t->key) 106 return findElement(t->lson, k); 107 else 108 return findElement(t->rson, k); 109 } 110 111 node *kthElement(node *&t, int k) 112 { 113 int leftSize = getSize(t->lson); 114 if (k == leftSize + 1) 115 return t; 116 else if (k <= leftSize) 117 return kthElement(t->lson, k); 118 else 119 return kthElement(t->rson, k - leftSize - 1); 120 } 121 122 int countSmaller(node *&t, int k) 123 { 124 if (t == NULL)return 0; 125 if (k == t->key) 126 return getSize(t->lson); 127 else if (k < t->key) 128 return countSmaller(t->lson, k); 129 else 130 return countSmaller(t->rson, k) + getSize(t->lson) + 1; 131 } 132 133 int countBigger(node *&t, int k) 134 { 135 if (t == NULL)return 0; 136 if (k == t->key) 137 return getSize(t->rson); 138 else if (k > t->key) 139 return countBigger(t->rson, k); 140 else 141 return countBigger(t->lson, k) + getSize(t->rson) + 1; 142 } 143 144 node *treapRoot; 145 146 public: 147 148 treap(void) 149 { 150 treapRoot = NULL; 151 srand(time(0) + 5264); 152 } 153 154 int size(void) 155 { 156 return getSize(treapRoot); 157 } 158 159 void insert(int key) 160 { 161 insertNode(treapRoot, key); 162 } 163 164 void erase(int key) 165 { 166 deleteNode(treapRoot, key); 167 } 168 169 int kthElement(int key) 170 { 171 return kthElement(treapRoot, key)->key; 172 } 173 174 int countSmaller(int key) 175 { 176 return countSmaller(treapRoot, key); 177 } 178 179 }t; 180 181 signed main(void) 182 { 183 using namespace std; 184 185 int n; scanf("%d", &n); 186 187 char s[10]; int num; 188 189 while (n--) 190 { 191 scanf("%s%d", s, &num); 192 193 char c = s[0]; 194 195 if (c == ‘I‘) 196 t.insert(num); 197 else if (c == ‘D‘) 198 t.erase(num); 199 else if (c == ‘C‘) 200 printf("%d\n", t.countSmaller(num)); 201 else 202 { 203 if (num <= t.size()) 204 printf("%d\n", t.kthElement(num)); 205 else 206 puts("invalid"); 207 } 208 } 209 }
@Author: YouSiki
SPOJ ORDERSET - Order statistic set
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。