题目来源：HDU 3726 Graph and Queries

题意：见白书

思路：刚学treap 參考白皮书

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

struct Node
{
    Node *ch[2];
    int r;
    int v;
    int s;
    Node(int v): v(v) {
        ch[0] = ch[1] = NULL; r = rand(); s = 1;
    }
    bool operator < (const Node& rhs) const{
        return r < rhs.r;
    }
    int cmp(int x) const{
        if(x == v) return -1;
        return x < v ?
 0 : 1;
    }
    void maintain(){
        s = 1;
        if(ch[0] != NULL) s += ch[0]->s;
        if(ch[1] != NULL) s += ch[1]->s;
    }
};

void rotate(Node* &o, int d){
    Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
    o->maintain(); k->maintain(); o = k;
}

void insert(Node* &o, int x){
    if(o == NULL){
        o = new Node(x);
    }
    else{
        int d = (x < o->v ? 0 : 1);
        insert(o->ch[d], x);
        if(o->ch[d] > o) rotate(o, d^1);
    }
    o->maintain();
    //printf("--------+%d\n", o->s);
}

void remove(Node* &o, int x){
    int d = o->cmp(x);
    if(d == -1){
        Node* u = o;    
        if(o->ch[0] != NULL && o->ch[1] != NULL){            
            int d2 = o->ch[0] > o->ch[1] ? 1 : 0;
            rotate(o, d2); remove(o->ch[d2], x);
        }
        else{
            if(o->ch[0] == NULL) o = o->ch[1];
            else o = o->ch[0];
            delete u;
        }
    }
    else
        remove(o->ch[d], x);
    if(o != NULL) o->maintain();
}

const int maxn = 20010;
const int maxc = 500010;
int n, m, w[maxn], from[maxn*3], to[maxn*3], removed[maxn*3];
int f[maxn];

Node* root[maxn];

struct Command
{
    char type;
    int x, p;
    Command(){}
    Command(char type, int x, int p): type(type), x(x), p(p) { }
}commands[maxc];

int find(int x)
{
    if(x != f[x])
        return f[x] = find(f[x]);
    return f[x];
}
int kth(Node* o, int k){
    if(o == NULL || k <= 0 || k > o->s)
        return 0;
    int s = (o->ch[1] == NULL ? 0 : o->ch[1]->s);
    if(k == s+1) return o->v;
    else if(k <= s) return kth(o->ch[1], k);
    else return kth(o->ch[0], k-s-1);
}

void mergeto(Node* &src, Node* &dest){
    
    if(src->ch[0] != NULL) mergeto(src->ch[0], dest);
    if(src->ch[1] != NULL) mergeto(src->ch[1], dest);
    insert(dest, src->v);
    delete src;
    src = http://www.mamicode.com/NULL;>