1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <string.h>
using namespace std;
struct Node{
    Node *ch[2];
    int r,s;int b;
    char v;
    void pushdown(){if(b){b=0;swap(ch[0],ch[1]);ch[0]->b^=1;ch[1]->b^=1;}}
    Node(char v,Node *nl):v(v){r=rand();b=0;ch[0]=ch[1]=nl;s=1;}
    void maintain(){s=1;s+=ch[0]->s;s+=ch[1]->s;}
}*root,*null;
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,char x){
    if(o==null){o=new Node(x,null);return;}
    insert(o->ch[1],x);
    if(o->ch[1]->r>o->r) rotate(o,0);
    else o->maintain();
}
int cmprk(Node* o,int k){
    if(o->ch[0]->s+1==k) return -1;
    if(o->ch[0]->s>=k) return 0;else return 1;
}
void splay(Node* &o,int k){
    if(o==null) return;
    o->pushdown();
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX