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>
int rand()
{
    static int seed=23323323;
    seed+=seed<<1|1;
    return seed&0x7fffffff;
}
struct node
{
    node*l,*r;
    int x,rnd;
    node(int xx=0)
    {
        l=r=0;
        x=xx;
        rnd=rand();
    }
}*root;
void rr(node*&cur)
{
    node*t=cur->l;
    cur->l=t->r;
    t->r=cur;
    cur=t;
}
void lr(node*&cur)
{
    node*t=cur->r;
    cur->r=t->l;
    t->l=cur;
    cur=t;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX