fork(1) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 3e5 + 5;
  4. struct node{
  5.     node* left;
  6.     node* right;
  7.     int cnt;
  8.     node(){
  9.         left = NULL;
  10.         right = NULL;
  11.         cnt = 0;
  12.     }
  13.     node* insert(int l , int r , int val){
  14.         ++cnt;
  15.         if(l < r){
  16.             int mid = l + r >> 1;
  17.             if(val <= mid){
  18.                 if(left == NULL){
  19.                     left = new node();
  20.                 }
  21.                 left = left -> insert(l , mid , val);
  22.             }
  23.             else{
  24.                 if(right == NULL){
  25.                     right = new node();
  26.                 }
  27.                 right = right -> insert(mid + 1 , r , val);
  28.             }
  29.         }
  30.         return this;
  31.     }
  32.     int kth(int l , int r , int k){
  33.         if(l == r){
  34.             return l;
  35.         }
  36.         int mid = l + r >> 1;
  37.         int count = (left == NULL) ? 0 : left -> cnt;
  38.         if(count >= k){
  39.             return left -> kth(l , mid , k);
  40.         }
  41.         return right -> kth(mid + 1 , r , k - count);
  42.     }
  43.     node* merge(node* other){
  44.         cnt += other -> cnt;
  45.         if(other -> left != NULL){
  46.             if(left == NULL){
  47.                 left = other -> left;
  48.             }
  49.             else{
  50.                 left = left -> merge(other -> left);
  51.             }
  52.         }
  53.         if(other -> right != NULL){
  54.             if(right == NULL){
  55.                 right = other -> right;
  56.             }
  57.             else{
  58.                 right = right -> merge(other -> right);
  59.             }
  60.         }
  61.         return this;
  62.     }
  63. };
  64. node* rdtree[N];
  65. int n , q;
  66. int idx1 , idx2 , cur , k;
  67. char arr[6];
  68. int main(){
  69.     scanf("%d %d" , &n , &q);
  70.     for(int i = 1 ; i <= n ; ++i){
  71.         rdtree[i] = new node();
  72.         rdtree[i] = rdtree[i] -> insert(1 , n , i);
  73.     }
  74.     cur = n;
  75.     while(q--){
  76.         scanf("%s" , arr);
  77.         if(arr[0] == 'U'){
  78.             scanf("%d %d" , &idx1 , &idx2);
  79.             rdtree[++cur] = rdtree[idx1];
  80.             rdtree[cur] = rdtree[cur] -> merge(rdtree[idx2]);
  81.         }
  82.         else{
  83.             scanf("%d %d" , &idx1 , &k);
  84.             printf("%d\n" , rdtree[idx1] -> kth(1 , n , k));
  85.         }
  86.     }
  87. }
Success #stdin #stdout 0s 4464KB
comments ()
stdin
copy 
7 8
UNION 1 2
UNION 8 3
GET 4 1
UNION 4 5
GET 10 2
GET 9 3
GET 9 2
GET 9 1
stdout
copy 
4
5
3
2
1
https://ideone.com/zhnLKC
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!