Description：
H国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。伸展树（splay）是一种数据结构，因为代码好写，功能多，效率高，掌握这种数据结构成为了H国的必修技能。有一天，邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说，splay如果写成单旋的，将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理，但还是有H国的人相信了，小H就是其中之一，spaly马上成为他的信仰。而H国的国王，自然不允许这样的风气蔓延，国王构造了一组数据，数据由m（不超过$10^5$）个操作构成，他知道这样的数据肯定打垮spaly，但是国王还有很多很多其他的事情要做，所以统计每个操作
所需要的实际代价的任务就交给你啦。数据中的操作分为5种：
1.插入操作：向当前非空spaly中插入一个关键码为key的新孤立节点。插入方法为，先让key和根比较，如果key比根小，则往左子树走，否则往右子树走，如此反复，直到某个时刻，key比当前子树根x小，而x的左子树为空，那就让key成为x的左孩子；或者key比当前子树根x大，而x的右子树为空，那就让key成为x的右孩子。该操作的代价为：插入后，key的深度。特别地，若树为空，则直接让新节点成为一个单个节点的树。（各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。）
2.单旋最小值:将spaly中关键码最小的元素xmin单旋到根。操作代价为：单旋前xmin的深度。（对于单旋操作的解释见末尾对spaly的描述。）
3.单旋最大值:将spaly中关键码最大的元素xmax单旋到根。操作代价为：单旋前xmax的深度。
4.单旋删除最小值：先执行2号操作，然后把根删除。由于2号操作之后，根没有左子树，所以直接切断根和右子树的联系即可。（具体见样例解释）。操作代价同2号操作。
5.单旋删除最大值：先执行3号操作，然后把根删除。操作代价同3号操作。
对于不是 H 国的人，你可能需要了解一些 spaly 的知识，才能完成国王的任务： a. spaly 是一棵二叉树，满足对于任意一个节点 x，它如果有左孩子 lx，那么 lx 的关键码小于 x 的关键码。 如果有右孩子 rx，那么 rx 的关键码大于 x 的关键码。 b. 一个节点在 spaly 的深度定义为：从根节点到该节点的路径上一共有多少个节点（包括自己）。 c. 单旋操作是对于一棵树上的节点 x 来说的。一开始,设 f 为 x 在树上的父亲。如果 x 为 f 的左孩子，那么 执行 zig(x) 操作（如上图中，左边的树经过 zig(x) 变为了右边的树），否则执行 zag(x) 操作（在上图中，将右边的树经过 zag(f) 就变成了左边的树）。每当执 行一次 zig(x) 或者 zag(x)，x 的深度减小 1，如此反复，直到 x 为根。总之，单旋 x 就是通过反复执行 zig 和 zag 将 x 变为根。
Input：
第一行单独一个正整数 m。 接下来 m 行，每行描述一个操作：首先是一个操作编号 c∈[1,5]，即问题描述中给出的五种操作中的编号，若 c = 1，则再输入一个非负整数 key，表示新插入节点的关键码。 $1≤m≤10^5,1≤key≤10^9$ 所有出现的关键码互不相同。任何一个非插入操作，一定保证树非空。在未执行任何操作之前，树为空
Output：
输出共 m 行，每行一个整数，第 i 行对应第 i 个输入的操作的代价。
Analysis：
本题有多种方法可解，具体来说分为两类：LCT与区间动态维护序列
首先我们来分析一下题目对于树所旋转的性质，
因为是只旋转最大或最小值，可以发现，其在旋转的时候并没有太多的破坏原树的形态，假设我们要删除的节点为X，如下图所示：
一.
LCT的方法应该是最明了好写的，直接cut掉X以前的父亲和儿子和它所连的边，然后link它和根，以及它的儿子和它的父亲。中间随意维护到根的深度和某个数前驱后继即可(关于前驱后继的具体说明见后)
二.
另一种方法是动态维护序列，并在其上记录信息。我所用的方法是Splay，似乎是常数最大并且代码最长的(orz 线段树和树状数组)，大概思路就是把点们加进去后，每次预先算好影响的是哪一段区间(X的子树，根据splay的性质可知其一定是连续的一段数区间)，然后把它对应在Splay中打打标记什么的就可以了。删除的话，也是splay的基本操作了。感觉前面预先算是也算是建了一棵虚树。
一些说明:
在插入的时候(前面讲的“虚树”)我们不能直接插入的。用一个set维护每个数的前驱后继是谁，然后这个数要么是它前驱的右儿子要么是它后继的左儿子，并且这两个位置在除树为空的情况下有且仅有一个是合法的。这个可以用反证法自己YY一下。(好像新发现了splay的一个有趣的性质呢！)
那么找最大值最小值的话就直接用set取出来处理即可。然后说明一下在我的程序中splay也使用了上述插入方法，似乎不必要。事实证明太快了><(splay中因为就是随便转的所以树的形态比较好就可以直接插了)
Thoughts：
本题在考场上打了一个大暴力，然后暴力写错了。。。 没有深入了解splay。。。并且不敢YY。。。 于是最前面的那个性质都没想到。。。 然后改题改死了。。感觉自己应总结一下方法><
于是乎：
1.碰见一些有非常”巧妙“特殊限制操作的题，勇于手玩几组样例，通常会有很不错的收获
2.想清楚再写程序(一定要想清楚！！！)，不要急，尽量每一步确保无误，会对调试有很大帮助
3.如果程序层次分明，可以考虑写一部分就调一部分，这样也可以节省许多时间
4.静态查错非常重要，在程序错了的时候先静态查错！
Code：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define Ite set<int>::iterator
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define N (100000+5)
map<int, int> ms;
set<int> mynum;
Ite ite, it, tt;
int tp, st[N], all;
#define lc ch[o][0]
#define rc ch[o][1]
struct SPLAY{
int Rt, Tot, fa[N], Tag[N], Sum[N], ch[N][2];
void Init(int v){
Rt = ++Tot; Sum[Tot] = 1;
}
void Push(int o){
Sum[o] += Tag[o];
if(lc) Tag[lc] += Tag[o]; if(rc) Tag[rc] += Tag[o];
Tag[o] = 0;
}
void Rotate(int o){
int f = fa[o], g = fa[f];
int c = ch[f][1]==o;
if(g) ch[g][ch[g][1]==f] = o;
fa[o] = g; fa[f] = o; fa[ch[o][c^1]] = f;
ch[f][c] = ch[o][c^1]; ch[o][c^1] = f;
}
int Splay(int o, int aim){
tp = 0;
for(int i = o; i; i = fa[i]) st[++tp] = i;
while(tp) Push(st[tp--]);
int f, g;
while(fa[o] != aim){
f = fa[o], g = fa[f];
if(g != aim) Rotate(f);
Rotate(o);
}
if(!aim) Rt = o;
return Sum[o];
}
int Insert(int trueF){
int o = ++Tot, F, c;
if(it != mynum.begin() && !ch[F=ms[*(--(ite=it))]][1]){
ch[F][c=1] = o; fa[o] = F;
}else{
F = ms[*(++(ite=it))]; ch[F][c=0] = o; fa[o] = F;
}
Splay(o, 0);
Sum[o] = Splay(trueF, 0)+1;
return Sum[o];
}
void Add(int u, int v, int add){
if(u == v) return;
Splay(u, 0); Splay(v, u);
if(ch[v][0]) Tag[ch[v][0]] += add;
}
void Del(){
Push(Rt);
Rt = ch[Rt][0]? ch[Rt][0]: ch[Rt][1];
fa[Rt] = 0;
}
}SP;
#undef lc
#undef rc
struct RTree{
int Rt, Tot, fa[N], Val[N], ls[N], rs[N];
int Insert(int v){
++Tot; ++all; mynum.insert(v);
it = mynum.lower_bound(v); ms[*it] = Tot;
Val[Tot] = v;
if(all==1){
Rt = Tot; SP.Init(v);
return 1;
}
int tm;
if(it != mynum.begin() && !rs[tm=ms[*(--(ite=it))]]){
rs[tm] = Tot; fa[Tot] = tm; return SP.Insert(tm);
}else{
tm = ms[*(++(ite=it))];
ls[tm] = Tot; fa[Tot] = tm; return SP.Insert(tm);
}
}
int Turn(bool fl, bool iscut){
all -= iscut;
int me = ms[fl? *(--(tt=mynum.end())): *mynum.begin()],
myson = fl? ls[me]: rs[me], myfa = fa[me];
int ret = SP.Splay(me, 0);
if(myfa){
SP.Sum[me] = 0; SP.Tag[SP.Rt] += !iscut;
if(!fl){
if(!iscut) rs[me] = Rt, fa[Rt] = me, Rt = me, fa[Rt] = 0;
ls[myfa] = myson; if(myson) fa[myson] = myfa;
if(myson){
SP.Add(me, myfa, -1);
}
}else{
if(!iscut) ls[me] = Rt, fa[Rt] = me, Rt = me, fa[Rt] = 0;
rs[myfa] = myson; if(myson) fa[myson] = myfa;
if(myson)
SP.Add(myfa, me, -1);
}
}else if(iscut){
Rt = ls[me]? ls[me]: rs[me]; fa[Rt] = 0;
--SP.Tag[SP.Rt];
}
SP.Splay(me, 0);
if(iscut) SP.Del(), mynum.erase(mynum.lower_bound(Val[me]));
return ret;
}
}RT;
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int m, op, key, ans;
scanf("%d", &m);
For(i, 1, m){
scanf("%d", &op);
if(op == 1) scanf("%d", &key), ans = RT.Insert(key);
else if(op == 2) ans = RT.Turn(0, 0);
else if(op == 3) ans = RT.Turn(1, 0);
else if(op == 4) ans = RT.Turn(0, 1);
else ans = RT.Turn(1, 1);
printf("%d\n", ans);
}
return 0;
}