11056: 【原1056】二哥吃糖
题目
题目描述
author: zyz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1056
Description
二哥有N个盒子，每个盒子里面都有一块糖。
二哥无聊的时候就做以下几种事情：
-
把某两个盒子里面的糖拿出来放在一个新的盒子里面
-
吃掉某一个盒子里面的所有的糖
-
数数当前糖果数第P多的盒子里面有几块糖
后来二哥觉得总吃糖不好，但是还忍不住要做这些事，所以就只好写程序来模拟这些……
Input Format
第一行两个数N(初始糖果数)和M(操作数)，糖果编号为1到N
下面M行，每行表示一个操作
C x y 把糖果x所在盒子与和糖果y所在盒子进行合并。如果x或者y已经被吃掉，或者x与y本来就在同一个盒子里，则什么也不做
D x 吃掉糖果x所在的盒子里面的糖，同样，如果x已经被吃掉，则什么也不做
Q p 询问当前糖果数第p多的盒子里面的糖果数量，如果剩下的有糖果的盒子数量小于p，则输出0。所有的p都在1到10之间
Output Format
对于每个Q操作，输出一个数(糖果数量)，占一行
说明
\( 1 \leq M \leq 50000，1 \leq N \leq 500000 \)
其他数字都在1到N之间
Sample Input
20 10
C 1 2
C 3 4
Q 2
Q 7
C 1 5
C 2 5
Q 1
D 5
Q 2
Q 1
Sample Output
2
1
3
1
2
FineArtz's solution
/* 二哥吃糖 */
#include <iostream>
using namespace std;
class Node{
public:
int size = 1, ind = 0;
};
bool b[500005];
Node a[500005];
int p[500005], pos[500005];
int n, m, Size = 0;
int getParent(int x){
if (p[x] != x)
p[x] = getParent(p[x]);
return p[x];
}
void siftdown(int i){
int x = i, mx = a[i].size;
if (i * 2 <= Size){
if (a[i * 2].size > mx){
x = i * 2;
mx = a[i * 2].size;
}
}
if (i * 2 + 1 <= Size){
if (a[i * 2 + 1].size > mx){
x = i * 2 + 1;
mx = a[i * 2 + 1].size;
}
}
if (x != i){
a[0] = a[x];
a[x] = a[i];
a[i] = a[0];
pos[a[i].ind] = i;
pos[a[x].ind] = x;
siftdown(x);
}
}
void siftup(int i){
while (i >= 2){
if (a[i].size <= a[i / 2].size)
break;
a[0] = a[i];
a[i] = a[i / 2];
a[i / 2] = a[0];
pos[a[i].ind] = i;
pos[a[i / 2].ind] = i / 2;
i /= 2;
}
}
void del(int i){
a[i] = a[Size--];
siftdown(i);
}
int findk(int k){
int tmp = Size;
for (int i = 1; i <= k - 1; ++i){
a[0] = a[1];
a[1] = a[Size];
a[Size] = a[0];
pos[a[1].ind] = 1;
pos[a[Size].ind] = Size;
--Size;
siftdown(1);
}
int ret = a[1].size;
while (Size < tmp){
++Size;
siftup(Size);
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
a[i].ind = i;
p[i] = i;
pos[i] = i;
b[i] = true;
}
Size = n;
while (m--){
char ch;
int x, y;
cin >> ch;
switch(ch){
case 'C':{
cin >> x >> y;
int px = getParent(x), py = getParent(y);
if (!b[px] || !b[py] || px == py) break;
p[px] = py;
a[pos[py]].size += a[pos[px]].size;
del(pos[px]);
siftup(pos[py]);
break;
}
case 'D':{
cin >> x;
int px = getParent(x);
if (!b[px]) break;
del(pos[px]);
b[px] = false;
break;
}
case 'Q':{
cin >> x;
if (Size < x)
cout << "0\n";
else
cout << findk(x) << '\n';
break;
}
default:
break;
}
}
return 0;
}
ligongzzz's solution
#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;
int mmax(int a, int b) {
return a > b ? a : b;
}
int mmin(int a, int b) {
return a < b ? a : b;
}
//记录元素在优先队列里面的位置
int queue_pos[500009] = { 0 };
class type {
public:
int pos = 0;
int val = 0;
};
class mqueue {
public:
type queue_data[500009];
int _size = 0;
void push_up(int pos) {
for (; pos > 1 && queue_data[pos].val > queue_data[pos >> 1].val; pos >>= 1) {
swap(queue_pos[queue_data[pos].pos], queue_pos[queue_data[pos >> 1].pos]);
swap(queue_data[pos], queue_data[pos >> 1]);
}
}
void push_down(int pos) {
for (; pos * 2 <= _size;) {
if (pos * 2 == _size) {
if (queue_data[pos].val < queue_data[pos << 1].val) {
swap(queue_pos[queue_data[pos].pos], queue_pos[queue_data[pos * 2].pos]);
swap(queue_data[pos], queue_data[pos << 1]);
}
break;
}
else {
if (queue_data[pos].val < mmax(queue_data[pos * 2].val, queue_data[pos * 2 + 1].val)) {
if (queue_data[pos * 2].val < queue_data[pos * 2 + 1].val) {
swap(queue_pos[queue_data[pos].pos], queue_pos[queue_data[pos * 2 + 1].pos]);
swap(queue_data[pos], queue_data[pos * 2 + 1]);
pos = pos * 2 + 1;
}
else {
swap(queue_pos[queue_data[pos].pos], queue_pos[queue_data[pos * 2].pos]);
swap(queue_data[pos], queue_data[pos * 2]);
pos <<= 1;
}
}
else
break;
}
}
}
void push(const type& val) {
queue_data[++_size] = val;
queue_pos[val.pos] = _size;
push_up(_size);
}
type pop() {
auto temp = queue_data[1];
queue_data[1] = queue_data[_size];
queue_pos[queue_data[1].pos] = 1;
--_size;
push_down(1);
queue_pos[temp.pos] = 0;
return temp;
}
int size() {
return _size;
}
void erase(int pos) {
queue_pos[queue_data[pos].pos] = 0;
queue_pos[queue_data[_size].pos] = pos;
queue_data[pos] = queue_data[_size];
--_size;
push_up(pos);
push_down(pos);
}
};
//并查集
class disjointSet {
public:
//数组
int* parent;
int length = 0;
//构造函数
disjointSet() = default;
disjointSet(int size) :length(size) {
parent = new int[size];
memset(parent, -1, length * sizeof(int));
}
//析构函数
~disjointSet() {
length = 0;
delete[] parent;
}
//寻找
int find(int x) {
if (parent[x] < 0)
return x;
return parent[x] = find(parent[x]);
}
//合并
void set_union(int root1, int root2) {
if (root1 == root2)
return;
if (parent[root1] > parent[root2]) {
parent[root2] += parent[root1];
parent[root1] = root2;
}
else {
parent[root1] += parent[root2];
parent[root2] = root1;
}
}
int size(int pos) {
return -parent[find(pos)];
}
};
bool cleared[500009] = { 0 };
mqueue queue_data;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
disjointSet set_data(n + 1);
for (int i = 1; i <= n; ++i) {
type temp;
temp.pos = i;
temp.val = 1;
queue_data.push(temp);
}
for (; m > 0;) {
char op;
cin >> op;
if (op == 'C') {
--m;
int x, y;
cin >> x >> y;
if (set_data.find(x) == set_data.find(y) || cleared[set_data.find(x)] || cleared[set_data.find(y)]) {
continue;
}
queue_data.erase(queue_pos[set_data.find(x)]);
queue_data.erase(queue_pos[set_data.find(y)]);
set_data.set_union(set_data.find(x), set_data.find(y));
type temp;
temp.pos = set_data.find(x);
temp.val = set_data.size(x);
queue_data.push(temp);
}
else if (op == 'D') {
--m;
int x;
cin >> x;
if (cleared[set_data.find(x)]) {
continue;
}
queue_data.erase(queue_pos[set_data.find(x)]);
cleared[set_data.find(x)] = true;
}
else if (op == 'Q') {
--m;
int p;
cin >> p;
type temp[12];
for (int i = 0; i < p - 1; ++i) {
temp[i] = queue_data.pop();
}
type ans = queue_data.pop();
cout << ans.val << "\n";
queue_data.push(ans);
for (int i = 0; i < p - 1; ++i) {
queue_data.push(temp[i]);
}
}
}
return 0;
}
Neight99's solution
#include <iostream>
using namespace std;
const int maxN = 5e5 + 100;
int box[maxN], sugar[maxN], moveTo[maxN] = {0}, boxNow, N, M;
template <class T>
class AvlTree {
private:
struct AvlNode {
T data;
AvlNode *left;
AvlNode *right;
int height;
AvlNode(const T &otherdata, AvlNode *l, AvlNode *r)
: data(otherdata), left(l), right(r), height(1) {}
};
public:
AvlTree(AvlNode *t = 0) : root(t) {}
~AvlTree() { makeEmpty(root); }
bool find(const T &x) const { return find(x, root); }
void insert(const T &x) { insert(x, root); }
void remove(const T &x) { remove(x, root); }
T &findkth(int i) { return findkth(i, root); }
private:
AvlNode *root;
void insert(const T &x, AvlNode *&t);
void remove(const T &x, AvlNode *&t);
bool find(const T &x, AvlNode *t) const;
void makeEmpty(AvlNode *&t);
T &findkth(int i, AvlNode *&t);
int height(AvlNode *t) { return t == 0 ? 0 : t->height; }
void LL(AvlNode *&t);
void RR(AvlNode *&t);
void LR(AvlNode *&t);
void RL(AvlNode *&t);
};
template <class T>
void AvlTree<T>::insert(const T &x, AvlNode *&t) {
if (t == 0) {
t = new AvlNode(x, 0, 0);
} else if (x > t->data) {
insert(x, t->left);
if (height(t->left) - height(t->right) == 2) {
if (x > t->left->data) {
LL(t);
} else {
LR(t);
}
}
t->height = height(t->left) + height(t->right) + 1;
} else {
insert(x, t->right);
if (height(t->right) - height(t->left) == 2) {
if (x <= t->right->data) {
RR(t);
} else {
RL(t);
}
}
t->height = height(t->left) + height(t->right) + 1;
}
}
template <class T>
void AvlTree<T>::remove(const T &x, AvlNode *&t) {
if (t == 0) {
return;
}
if (x > t->data) {
remove(x, t->left);
if (height(t->right) - height(t->left) == 2) {
AvlNode *r = t->right;
if (height(r->left) > height(r->right)) {
RL(t);
} else {
RR(t);
}
}
t->height = height(t->left) + height(t->right) + 1;
} else if (x < t->data) {
remove(x, t->right);
if (height(t->left) - height(t->right) == 2) {
AvlNode *r = t->left;
if (height(r->right) > height(r->left)) {
LR(t);
} else {
LL(t);
}
}
t->height = height(t->left) + height(t->right) + 1;
} else if (t->left != 0 && t->right != 0) {
if (height(t->left) <= height(t->right)) {
AvlNode *tmp = t->right;
while (tmp->left != 0) {
tmp = tmp->left;
}
t->data = tmp->data;
remove(t->data, t->right);
t->height = height(t->left) + height(t->right) + 1;
} else {
AvlNode *tmp = t->left;
while (tmp->right != 0) {
tmp = tmp->right;
}
t->data = tmp->data;
remove(t->data, t->left);
t->height = height(t->left) + height(t->right) + 1;
}
} else {
AvlNode *old = t;
t = (t->left != 0) ? t->left : t->right;
delete old;
}
}
template <class T>
bool AvlTree<T>::find(const T &x, AvlNode *t) const {
if (t == 0) {
return false;
}
if (x > t->data) {
return find(x, t->left);
}
if (x < t->data) {
return find(x, t->right);
}
return true;
}
template <class T>
void AvlTree<T>::makeEmpty(AvlNode *&t) {
if (t == 0) return;
AvlNode *tmp = t;
makeEmpty(t->left);
makeEmpty(t->right);
delete tmp;
t = 0;
}
template <class T>
T &AvlTree<T>::findkth(int i, AvlNode *&t) {
int rs = height(t->left);
if (rs == i - 1) {
return t->data;
}
if (rs >= i) {
return findkth(i, t->left);
} else {
return findkth(i - rs - 1, t->right);
}
}
template <class T>
void AvlTree<T>::LL(AvlNode *&t) {
AvlNode *t1 = t->left;
t->left = t1->right;
t1->right = t;
t->height = height(t->left) + height(t->right) + 1;
t1->height = height(t1->left) + height(t) + 1;
t = t1;
}
template <class T>
void AvlTree<T>::RR(AvlNode *&t) {
AvlNode *t1 = t->right;
t->right = t1->left;
t1->left = t;
t->height = height(t->left) + height(t->right) + 1;
t1->height = height(t1->right) + height(t) + 1;
t = t1;
}
template <class T>
void AvlTree<T>::LR(AvlNode *&t) {
RR(t->left);
LL(t);
}
template <class T>
void AvlTree<T>::RL(AvlNode *&t) {
LL(t->right);
RR(t);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x, y;
char order;
AvlTree<int> bst;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
box[i] = 1;
bst.insert(1);
sugar[i] = i;
}
boxNow = N;
for (int times = 0; times < M; times++) {
cin >> order;
switch (order) {
case 'C':
cin >> x >> y;
while (moveTo[sugar[x]] != 0) {
sugar[x] = moveTo[sugar[x]];
}
while (moveTo[sugar[y]] != 0) {
sugar[y] = moveTo[sugar[y]];
}
if (sugar[x] != sugar[y] && box[sugar[x]] != 0 &&
box[sugar[y]] != 0) {
bst.remove(box[sugar[x]]);
bst.remove(box[sugar[y]]);
box[sugar[x]] += box[sugar[y]];
box[sugar[y]] = 0;
bst.insert(box[sugar[x]]);
moveTo[sugar[y]] = sugar[x];
boxNow--;
}
break;
case 'D':
cin >> x;
while (moveTo[sugar[x]] != 0) {
sugar[x] = moveTo[sugar[x]];
}
if (box[sugar[x]] != 0) {
bst.remove(box[sugar[x]]);
box[sugar[x]] = 0;
boxNow--;
}
break;
case 'Q':
cin >> x;
if (boxNow < x) {
cout << 0 << '\n';
} else {
cout << bst.findkth(x) << '\n';
}
break;
}
}
return 0;
}
q4x3's solution
#include <iostream>
#include <cstdio>
// 红黑树模板源自于luogu
template<typename T>
class redblacktree {
protected:
struct Node;
Node* _root;
Node* _hot;
void init(T);
void connect34(Node*, Node*, Node*, Node*, Node*, Node*, Node*);
void SolveDoubleRed(Node*);
void SolveDoubleBlack(Node*);
Node* find(T, const int);
Node* rfind(T, const int);
Node* findkth(int, Node*);
int find_rank(T, Node*);
public:
struct iterator;
redblacktree() : _root(NULL), _hot(NULL) {}
int get_rank(T);
iterator insert(T);
bool remove(T);
int size();
bool empty();
iterator kth(int);
iterator lower_bound(T);
iterator upper_bound(T);
};
template <typename T>
struct redblacktree<T>::Node {
T val;
bool RBc;
Node* ftr;
Node* lc;
Node* rc;
int s;
Node( T v = T(), bool RB = true,
Node* f = NULL, Node* l = NULL, Node* r = NULL ,int ss = 1 )
: val(v), RBc(RB), ftr(f), lc(l), rc(r), s(ss) {}
Node* succ() {
Node* ptn = rc;
while(ptn->lc != NULL) {
--(ptn->s);
ptn = ptn->lc;
}
return ptn;
}
Node* left_node() {
Node* ptn = this;
if(!lc) {
while(ptn->ftr && ptn->ftr->lc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
} else {
ptn = ptn->lc;
while(ptn->rc) {
ptn = ptn->rc;
}
}
return ptn;
}
Node* right_node() {
Node* ptn = this;
if(!rc) {
while(ptn->ftr && ptn->ftr->rc == ptn)
ptn = ptn->ftr;
ptn = ptn->ftr;
} else {
ptn = ptn->rc;
while(ptn->lc) {
ptn = ptn->lc;
}
}
return ptn;
}
void maintain() {
s = 1;
if(lc) s += lc->s;
if(rc) s += rc->s;
}
};
template <typename T>
struct redblacktree<T>::iterator {
private:
Node* _real__node;
public:
iterator& operator++() {
_real__node = _real__node->right_node();
return *this;
}
iterator& operator--() {
_real__node = _real__node->left_node();
return *this;
}
T operator*() {
return _real__node->val;
}
iterator(Node* node_nn = NULL) : _real__node(node_nn) {}
iterator(T const& val_vv) : _real__node(rfind(val_vv, 0)) {}
iterator(iterator const& iter) : _real__node(iter._real__node) {}
};
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::insert(T v) {
Node* ptn = find(v, 1);
if(_hot == NULL) {
init(v);
return iterator(_root);
}
ptn = new Node(v, true, _hot, NULL, NULL, 1);
if( _hot->val <= v )
_hot->rc = ptn;
else
_hot->lc = ptn;
SolveDoubleRed(ptn);
return iterator(ptn);
}
template <typename T>
void redblacktree<T>::init(T v) {
_root = new Node(v, false, NULL, NULL, NULL, 1);
}
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::find(T v, const int op) {
Node* ptn = _root;
_hot = NULL;
while(ptn != NULL) {
_hot = ptn;
ptn->s += op;
if(ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}
return ptn;
}
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::rfind(T v, const int op) {
Node* ptn = _root;
_hot = NULL;
while(ptn != NULL && ptn->val != v) {
_hot = ptn;
ptn->s += op;
if(ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}
return ptn;
}
template <typename T>
void redblacktree<T>::SolveDoubleRed(Node* nn) {
while((!(nn->ftr)) || nn->ftr->RBc) {
if(nn == _root) {
_root->RBc = false;
return;
}
Node* pftr = nn->ftr;
if(!(pftr->RBc)) return;
Node* uncle = (((nn->ftr)->ftr->lc == (nn->ftr)) ? ((nn->ftr)->ftr->rc) : ((nn->ftr)->ftr->lc));
Node* grdftr = nn->ftr->ftr;
if(uncle != NULL && uncle->RBc) {
grdftr->RBc = true;
uncle->RBc = false;
pftr->RBc = false;
nn = grdftr;
} else {
if(((pftr) != NULL && (pftr)->ftr->lc == (pftr))) {
if(((nn) != NULL && (nn)->ftr->lc == (nn))) {
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->rc = pftr;
connect34(pftr, nn, grdftr, nn->lc, nn->rc, pftr->rc, uncle);
pftr->RBc = false;
grdftr->RBc = true;
} else {
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, pftr, grdftr, pftr->lc, nn->lc, nn->rc, uncle);
nn->RBc = false;
grdftr->RBc = true;
}
} else {
if(((nn) != NULL && (nn)->ftr->lc == (nn))) {
nn->ftr = grdftr->ftr;
if(grdftr == _root) _root = nn;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = nn;
else grdftr->ftr->rc = nn;
connect34(nn, grdftr, pftr, uncle, nn->lc, nn->rc, pftr->rc);
nn->RBc = false;
grdftr->RBc = true;
} else {
pftr->ftr = grdftr->ftr;
if(grdftr == _root) _root = pftr;
else if(grdftr->ftr->lc == grdftr) grdftr->ftr->lc = pftr;
else grdftr->ftr->rc = pftr;
connect34(pftr, grdftr, nn, uncle, pftr->lc, nn->lc, nn->rc);
pftr->RBc = false;
grdftr->RBc = true;
}
}
return;
}
}
}
template <typename T>
void redblacktree<T>::connect34( Node* nroot, Node* nlc, Node* nrc,
Node* ntree1, Node* ntree2, Node* ntree3, Node* ntree4) {
nlc->lc = ntree1;
if(ntree1 != NULL) ntree1->ftr = nlc;
nlc->rc = ntree2;
if(ntree2 != NULL) ntree2->ftr = nlc;
nrc->lc = ntree3;
if(ntree3 != NULL) ntree3->ftr = nrc;
nrc->rc = ntree4;
if(ntree4 != NULL) ntree4->ftr = nrc;
nroot->lc = nlc;
nlc->ftr = nroot;
nroot->rc = nrc;
nrc->ftr = nroot;
nlc->maintain();
nrc->maintain();
nroot->maintain();
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::lower_bound(T v) {
Node* ptn = _root;
while(ptn) {
_hot = ptn;
if(ptn->val < v) {
ptn = ptn->rc;
} else {
ptn = ptn->lc;
}
}
if(_hot->val < v) {
ptn = _hot;
} else {
ptn = _hot->left_node();
}
return iterator(ptn);
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::upper_bound(T v) {
Node* ptn = _root;
while(ptn) {
_hot = ptn;
if(ptn->val > v) {
ptn = ptn->lc;
} else {
ptn = ptn->rc;
}
}
if(_hot->val > v) {
ptn = _hot;
} else {
ptn = _hot->right_node();
}
return iterator(ptn);
}
template <typename T>
typename
redblacktree<T>::iterator redblacktree<T>::kth(int rank) {
return iterator(findkth(rank, _root));
}
template <typename T>
typename
redblacktree<T>::Node* redblacktree<T>::findkth(int rank, Node* ptn) {
if(!(ptn->lc)) {
if(rank == 1) {
return ptn;
} else {
return findkth(rank - 1, ptn->rc);
}
} else {
if(ptn->lc->s == rank - 1) return ptn;
else if(ptn->lc->s >= rank) return findkth(rank, ptn->lc);
else return findkth(rank - (ptn->lc->s) - 1, ptn->rc);
}
}
template <typename T>
int redblacktree<T>::get_rank(T v) {
return find_rank(v, _root);
}
template <typename T>
int redblacktree<T>::find_rank(T v, Node* ptn) {
if(!ptn) return 1;
else if(ptn->val >= v) return find_rank(v, ptn->lc);
else return (1 + ((ptn->lc) ? (ptn->lc->s) : 0) + find_rank(v, ptn->rc));
}
template <typename T>
int redblacktree<T>::size() {
return _root->s;
}
template <typename T>
bool redblacktree<T>::empty() {
return !_root;
}
template <typename T>
bool redblacktree<T>::remove(T v) {
Node* ptn = rfind(v, -1);
if(!ptn) return false;
Node* node_suc;
while(ptn->lc || ptn->rc) {
if(!(ptn->lc)) {
node_suc = ptn->rc;
} else if(!(ptn->rc)) {
node_suc = ptn->lc;
} else {
node_suc = ptn->succ();
}
--(ptn->s);
ptn->val = node_suc->val;
ptn = node_suc;
}
if(!(ptn->RBc)) {
--(ptn->s);
SolveDoubleBlack(ptn);
}
if(ptn == _root) {
_root = NULL;
delete ptn;
return true;
}
if(ptn->ftr->lc == ptn)
ptn->ftr->lc = NULL;
else
ptn->ftr->rc = NULL;
delete ptn;
return true;
}
template <typename T>
void redblacktree<T>::SolveDoubleBlack(Node* nn) {
while(nn != _root) {
Node* pftr = nn->ftr;
Node* bthr = (((nn)->ftr->lc == (nn)) ? ((nn)->ftr->rc) : ((nn)->ftr->lc));
if(bthr->RBc) {
bthr->RBc = false;
pftr->RBc = true;
if(_root == pftr) _root = bthr;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(((nn) != NULL && (nn)->ftr->lc == (nn))) {
connect34(bthr, pftr, bthr->rc, nn, bthr->lc, bthr->rc->lc, bthr->rc->rc);
} else {
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, nn);
}
bthr = (((nn)->ftr->lc == (nn)) ? ((nn)->ftr->rc) : ((nn)->ftr->lc));
pftr = nn->ftr;
}
if(bthr->lc && bthr->lc->RBc) {
bool oldRBc = pftr->RBc;
pftr->RBc = false;
if(pftr->lc == nn) {
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->lc;
else
pftr->ftr->rc = bthr->lc;
}
bthr->lc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->lc;
connect34(bthr->lc, pftr, bthr, pftr->lc, bthr->lc->lc, bthr->lc->rc, bthr->rc);
} else {
bthr->lc->RBc = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, bthr->lc, pftr, bthr->lc->lc, bthr->lc->rc, bthr->rc, pftr->rc);
}
pftr->ftr->RBc = oldRBc;
return;
} else if(bthr->rc && bthr->rc->RBc) {
bool oldRBc = pftr->RBc;
pftr->RBc = false;
if(pftr->lc == nn) {
bthr->rc->RBc = false;
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr;
else
pftr->ftr->rc = bthr;
}
bthr->ftr = pftr->ftr;
if(_root == pftr) _root = bthr;
connect34(bthr, pftr, bthr->rc, pftr->lc, bthr->lc, bthr->rc->lc, bthr->rc->rc);
} else {
if(pftr->ftr) {
if(pftr->ftr->lc == pftr)
pftr->ftr->lc = bthr->rc;
else
pftr->ftr->rc = bthr->rc;
}
bthr->rc->ftr = pftr->ftr;
if(_root == pftr) _root = bthr->rc;
connect34(bthr->rc, bthr, pftr, bthr->lc, bthr->rc->lc, bthr->rc->rc, pftr->rc);
}
pftr->ftr->RBc = oldRBc;
return;
}
if(pftr->RBc) {
pftr->RBc = false;
bthr->RBc = true;
return;
} else {
bthr->RBc = true;
nn = pftr;
}
}
}
int N, M, cnt, fa[500233], box[500233];
bool eaten[500233];
redblacktree<int> t;
int init() {
for(int i = 1;i <= N;++ i)
fa[i] = i;
}
int find(int x) {
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
int bind(int x, int y) {
fa[find(x)] = find(y);
}
int main() {
int maxi = 1;
scanf("%d%d", &N, &M);
cnt = N;
init();
for(int i = 1;i <= N;++ i)
box[i] = 1;
for(int i = 1;i <= N;++ i)
t.insert(1);
for(int i = 1;i <= M;++ i) {
char op[2];
scanf("%s", op);
if(op[0] == 'C') {
int x, y;
scanf("%d%d", &x, &y);
int fx = find(x), fy = find(y);
if(eaten[fx] | eaten[fy]) continue;
if(fx == fy) continue;
bind(fx, fy);
t.remove(box[fx]);
t.remove(box[fy]);
t.insert(box[fx] + box[fy]);
box[fy] += box[fx];
-- cnt;
} else if(op[0] == 'D') {
int x;
scanf("%d", &x);
int tmp = find(x);
if(eaten[tmp]) continue;
else {
t.remove(box[tmp]);
eaten[tmp] = 1;
-- cnt;
}
} else {
int p;
scanf("%d", &p);
if(cnt < p) {
printf("0\n");
continue;
}
printf("%d\n", *t.kth(cnt - p + 1));
}
}
}
victrid's solution
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int cinbox[500010],
cbox[500010],
father[500010] = {0};
template <class T>
class AVL_mset {
// allow duplicate avl
public:
struct node {
T data;
node* left;
node* right;
int size;
node(const T& other, node* l, node* r) : data(other), left(l), right(r), size(1) {}
};
AVL_mset() : root(nullptr) {}
bool find(const T& a) const { return find(a, root); }
void insert(const T& a) { insert(a, root); }
void remove(const T& a) { remove(a, root); }
T& findi(int i) { return findi(i, root); }
node* root;
void insert(const T& a, node*& t) {
if (t == 0) {
t = new node(a, 0, 0);
} else if (a > t->data) {
insert(a, t->left);
if (size(t->left) - size(t->right) == 2) {
if (a > t->left->data)
LL(t);
else
LR(t);
}
t->size = size(t->left) + size(t->right) + 1;
} else {
insert(a, t->right);
if (size(t->right) - size(t->left) == 2) {
if (a <= t->right->data)
RR(t);
else
RL(t);
}
t->size = size(t->left) + size(t->right) + 1;
}
}
void remove(const T& a, node*& t) {
if (t == nullptr)
return;
if (a > t->data) {
remove(a, t->left);
if (size(t->right) - size(t->left) == 2) {
node* r = t->right;
if (size(r->left) > size(r->right))
RL(t);
else
RR(t);
}
t->size = size(t->left) + size(t->right) + 1;
} else if (a < t->data) {
remove(a, t->right);
if (size(t->left) - size(t->right) == 2) {
node* r = t->left;
if (size(r->right) > size(r->left))
LR(t);
else
LL(t);
}
t->size = size(t->left) + size(t->right) + 1;
} else if (t->left != 0 && t->right != 0) {
if (size(t->left) <= size(t->right)) {
node* tmp = t->right;
while (tmp->left != 0)
tmp = tmp->left;
t->data = tmp->data;
remove(t->data, t->right);
t->size = size(t->left) + size(t->right) + 1;
} else {
node* tmp = t->left;
while (tmp->right != 0)
tmp = tmp->right;
t->data = tmp->data;
remove(t->data, t->left);
t->size = size(t->left) + size(t->right) + 1;
}
} else {
node* orig = t;
t = (t->left != nullptr) ? t->left : t->right;
delete orig;
}
}
bool find(const T& a, node* t) const {
if (t == nullptr)
return false;
if (a > t->data)
return find(a, t->left);
if (a < t->data)
return find(a, t->right);
return true;
}
T& findi(int i, node*& t) {
int rs = size(t->left);
if (rs == i - 1)
return t->data;
if (rs >= i)
return findi(i, t->left);
else
return findi(i - rs - 1, t->right);
}
int size(node* t) { return t == nullptr ? 0 : t->size; }
void LL(node*& t) {
node* t1 = t->left;
t->left = t1->right;
t1->right = t;
t->size = size(t->left) + size(t->right) + 1;
t1->size = size(t1->left) + size(t) + 1;
t = t1;
}
void RR(node*& t) {
node* t1 = t->right;
t->right = t1->left;
t1->left = t;
t->size = size(t->left) + size(t->right) + 1;
t1->size = size(t1->right) + size(t) + 1;
t = t1;
}
void LR(node*& t) {
RR(t->left);
LL(t);
}
void RL(node*& t) {
LL(t->right);
RR(t);
}
};
AVL_mset<int> mset;
int main() {
int mbox, N, M, a, b, op;
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++) {
cinbox[i] = 1;
mset.insert(1);
cbox[i] = i;
}
mbox = N;
for (int i = 1; i <= M; i++) {
scanf("\n%c", &op);
switch (op) {
case 'C':
scanf("%d%d", &a, &b);
while (father[cbox[a]] != 0)
cbox[a] = father[cbox[a]];
while (father[cbox[b]] != 0)
cbox[b] = father[cbox[b]];
if (cbox[a] == cbox[b] || cinbox[cbox[a]] == 0 || cinbox[cbox[b]] == 0)
break;
mset.remove(cinbox[cbox[a]]);
mset.remove(cinbox[cbox[b]]);
cinbox[cbox[a]] += cinbox[cbox[b]];
cinbox[cbox[b]] = 0;
mset.insert(cinbox[cbox[a]]);
father[cbox[b]] = cbox[a];
mbox--;
break;
case 'D':
scanf("%d", &a);
while (father[cbox[a]] != 0)
cbox[a] = father[cbox[a]];
if (cinbox[cbox[a]] == 0)
break;
mset.remove(cinbox[cbox[a]]);
cinbox[cbox[a]] = 0;
mbox--;
break;
case 'Q':
scanf("%d", &a);
printf("%d\n", a > mbox ? 0 : mset.findi(a));
break;
}
}
return 0;
}
yyong119's solution
#include <cstdio>
int N, M, x, y, rt1, rt2, rt, size, cnt;
int treeArr[500001], father[500001];
char op;
void add(int x, int y) {
for (int i = x; i <= N; i += i&(-i))
treeArr[i] += y;
}
int query(int x) {
int sum = 0;
for (int i = x; i > 0; i -= i&(-i))
sum += treeArr[i];
return sum;
}
int find(int x) {
if (father[x] < 0) return x;
else if (father[x] == 0) return 0;
else return father[x] = find(father[x]);
}
void merge(int root1, int root2) {
if (root1 == root2) return;
add(-father[root1], -1);
add(-father[root2], -1);
if (father[root1] > father[root2]) {
father[root2] += father[root1];
father[root1] = root2;
add(-father[root2], 1);
}
else {
father[root1] += father[root2];
father[root2] = root1;
add(-father[root1], 1);
}
--cnt;
}
int findK(int k) {
if (cnt < k) return 0;
k = cnt - k + 1;
int l = 1, r = N;
while (l <= r) {
int mid = (l + r) >> 1;
if (query(mid) < k) l = mid + 1; else r = mid - 1;
}
return l;
}
void eat(int root) {
if(father[root]) {
add(-father[root], -1);
father[root] = 0;
}
--cnt;
}
int main() {
scanf("%d%d", &N, &M);
size = N; cnt = N;
for (int i = 0; i < size; ++i) father[i + 1] = -1;
father[0] = 0;
add(1, size);
for (int i = 0; i < M; ++i) {
scanf("%s", &op);
if (op == 'C') {
scanf("%d%d", &x, &y);
rt1 = find(x);
rt2 = find(y);
if (rt1 != 0 && rt2 != 0 && rt1 != rt2) merge(rt1, rt2);
} else if (op == 'D') {
scanf("%d", &x);
rt = find(x);
if (rt != 0) eat(rt);
} else {
scanf("%d", &x);
printf("%d\n", findK(x));
}
}
return 0;
}
zqy2018's solution
/*
See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu1056.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, m, unused;
multiset<int> st;
int fa[500005], siz[500005];
bool vis[500005] = {0};
char opt[3];
void reduce(int pos){
st.erase(st.find(pos));
}
void append(int pos){
st.insert(pos);
}
// things above can be replaced by a BST, if STL is banned
int Find(int x){
return (fa[x] == x ? x: (fa[x] = Find(fa[x])));
}
void Union(int x, int y){
int u = Find(x), v = Find(y);
if (u == v || !u || !v) return ;
if (!vis[u]) append(1), vis[u] = true, --unused;
if (!vis[v]) append(1), vis[v] = true, --unused;
reduce(siz[u]);
reduce(siz[v]);
append(siz[u] + siz[v]);
if (siz[u] > siz[v])
fa[v] = u, siz[u] += siz[v];
else
fa[u] = v, siz[v] += siz[u];
}
void init(){
n = read(), m = read();
for (int i = 1; i <= n; ++i)
fa[i] = i, siz[i] = 1;
fa[0] = 0, siz[0] = 0;
unused = n;
}
void solve(){
while (m--) {
scanf("%s", opt);
if (opt[0] == 'C'){
int x = read(), y = read();
Union(x, y);
}
if (opt[0] == 'D'){
int x = Find(read());
if (!x) continue;
if (vis[x]) reduce(siz[x]);
fa[x] = 0;
}
if (opt[0] == 'Q'){
int t = read();
if (st.size() < t) {
t -= st.size();
printf("%d\n", (t > unused ? 0: 1));
}else {
multiset<int>::iterator iter = st.end();
while (t--)
--iter;
printf("%d\n", *iter);
}
}
}
}
int main(){
init();
solve();
return 0;
}