正文
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水一水。
代码
权值线段树
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> using namespace std; #define N 200005 struct node
{
int lt, rt, cnt;
}tree[N << ]; void build(int p, int l, int r)
{
node &t = tree[p]; t.lt = l;
t.rt = r;
t.cnt = ; if (l == r)
return; int mid = (l + r) >> ; build(p << , l, mid);
build(p << | , mid + , r);
} void insert(int p, int pos, int val)
{
node &t = tree[p]; t.cnt += val; if (t.lt == t.rt)
return; int mid = (t.lt + t.rt) >> ; if (pos <= mid)
insert(p << , pos, val);
else
insert(p << | , pos, val);
} int query(int p, int l, int r)
{
if (l > r)return ; node &t = tree[p]; if (t.lt == l && t.rt == r)
return t.cnt; int mid = (t.lt + t.rt) >> ; if (r <= mid)
return query(p << , l, r);
if (l > mid)
return query(p << | , l, r);
return query(p << , l, mid) + query(p << | , mid + , r);
} int rnk(int p, int rk)
{
node &t = tree[p]; if (t.lt == t.rt)
return t.lt; if (tree[p << ].cnt >= rk)
return rnk(p << , rk); else
return rnk(p << | , rk - tree[p << ].cnt);
} int n;
int a[N];
int b[N]; char s[N][]; signed main(void)
{
scanf("%d", &n); for (int i = ; i <= n; ++i)
scanf("%s%d", s[i], &a[i]); memcpy(b, a, sizeof(b)); sort(b + , b + + n); int m = unique(b + , b + + n) - b; build(, , m); for (int i = ; i <= n; ++i)if (s[i][] != 'K')
a[i] = lower_bound(b + , b + m, a[i]) - b; for (int i = ; i <= n; ++i)
{
char &c = s[i][]; if (c == 'I')
{
if (!query(, a[i], a[i]))
insert(, a[i], );
}
else if (c == 'D')
{
if (query(, a[i], a[i]))
insert(, a[i], -);
}
else if (c == 'K')
{
if (query(, , m) >= a[i])
printf("%d\n", b[rnk(, a[i])]);
else printf("invalid\n");
}
else if (c == 'C')
{
printf("%d\n", query(, , a[i] - ));
}
}
}
SegTree.cpp
Treap
#include <bits/stdc++.h> class treap
{
private: struct node
{
int key;
int tag;
int siz;
node *lson;
node *rson;
node(int k = , int t = rand()) :
key(k), tag(t), siz(), lson(), rson() {};
}; int getSize(node *&t)
{
if (t == NULL)return ;
t->siz = ;
if (t->lson)
t->siz += t->lson->siz;
if (t->rson)
t->siz += t->rson->siz;
return t->siz;
} void rotateLeft(node *&t)
{
node *r = t->rson;
t->rson = r->lson;
r->lson = t;
getSize(t);
getSize(r);
t = r;
} void rotateRight(node *&t)
{
node *l = t->lson;
t->lson = l->rson;
l->rson = t;
getSize(t);
getSize(l);
t = l;
} void insertNode(node *&t, int k)
{
if (t == NULL)
t = new node(k);
else
{
if (k < t->key)
{
insertNode(t->lson, k);
if (t->lson->tag > t->tag)
rotateRight(t);
}
else if (k > t->key)
{
insertNode(t->rson, k);
if (t->rson->tag > t->tag)
rotateLeft(t);
}
}
getSize(t);
} void deleteNode(node *&t)
{
if (t->lson == NULL)
t = t->rson;
else if (t->rson == NULL)
t = t->lson;
else
{
if (t->lson->tag > t->rson->tag)
rotateRight(t), deleteNode(t->rson);
else
rotateLeft(t), deleteNode(t->lson);
}
getSize(t);
} void deleteNode(node *&t, int k)
{
if (t != NULL)
{
if (k == t->key)
deleteNode(t);
else if (k < t->key)
deleteNode(t->lson, k);
else
deleteNode(t->rson, k);
getSize(t);
}
} node *findElement(node *&t, int k)
{
if (k == t->key)
return t;
else if (k < t->key)
return findElement(t->lson, k);
else
return findElement(t->rson, k);
} node *kthElement(node *&t, int k)
{
int leftSize = getSize(t->lson);
if (k == leftSize + )
return t;
else if (k <= leftSize)
return kthElement(t->lson, k);
else
return kthElement(t->rson, k - leftSize - );
} int countSmaller(node *&t, int k)
{
if (t == NULL)return ;
if (k == t->key)
return getSize(t->lson);
else if (k < t->key)
return countSmaller(t->lson, k);
else
return countSmaller(t->rson, k) + getSize(t->lson) + ;
} int countBigger(node *&t, int k)
{
if (t == NULL)return ;
if (k == t->key)
return getSize(t->rson);
else if (k > t->key)
return countBigger(t->rson, k);
else
return countBigger(t->lson, k) + getSize(t->rson) + ;
} node *treapRoot; public: treap(void)
{
treapRoot = NULL;
srand(time() + );
} int size(void)
{
return getSize(treapRoot);
} void insert(int key)
{
insertNode(treapRoot, key);
} void erase(int key)
{
deleteNode(treapRoot, key);
} int kthElement(int key)
{
return kthElement(treapRoot, key)->key;
} int countSmaller(int key)
{
return countSmaller(treapRoot, key);
} }t; signed main(void)
{
using namespace std; int n; scanf("%d", &n); char s[]; int num; while (n--)
{
scanf("%s%d", s, &num); char c = s[]; if (c == 'I')
t.insert(num);
else if (c == 'D')
t.erase(num);
else if (c == 'C')
printf("%d\n", t.countSmaller(num));
else
{
if (num <= t.size())
printf("%d\n", t.kthElement(num));
else
puts("invalid");
}
}
}
Treap.cpp
@Author: YouSiki
