首页 > 代码库 > SPOJ ORDERSET - Order statistic set

SPOJ ORDERSET - Order statistic set

2024-08-22 15:24:13   220人阅读

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 }
SegTree.cpp

 

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 }
Treap.cpp

 

@Author: YouSiki

 

SPOJ ORDERSET - Order statistic set


联系
我们