Skip to content

11056: 【原1056】二哥吃糖

题目

题目描述

author: zyz 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1056

Description

二哥有N个盒子,每个盒子里面都有一块糖。

二哥无聊的时候就做以下几种事情:

  1. 把某两个盒子里面的糖拿出来放在一个新的盒子里面

  2. 吃掉某一个盒子里面的所有的糖

  3. 数数当前糖果数第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;
}