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<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#define For(i,n) for(int i=1; i<=n; i++)
#define Rep(i,n) for(int i=0; i<n; i++)
#define N 200010
using namespace std;
struct Node{
  int ch[2],fa,path_fa,sz;
  void maintain();
}nodes[N];
void Node::maintain(){
  sz=1+nodes[ch[0]].sz+nodes[ch[1]].sz;
}
void rotate(int o,int d){
  int k=nodes[o].ch[d];
  int k2=nodes[k].ch[1^d];
  nodes[k].path_fa=nodes[o].path_fa;
  nodes[o].path_fa=0;
  nodes[nodes[o].fa].ch[o==nodes[nodes[o].fa].ch[1]]=k;
  nodes[o].ch[d]=k2;
  nodes[k].ch[1^d]=o;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX