题解 P3721 【[AH/HNOI2017]单旋】
标签：线段树+set
题解：
此题的标题为splay，所以我们可以排除这道题的正解是splay的可能性。然后我们发现只有最值的单旋，而且，三点一线不需要先旋转父亲。通过手玩我们可以发现，就是把最值直接移到最顶端作为根节点，然后其他的点以及他们之间的父子关系全部都没有变化。于是就只要求深度了。
我们发现，最小值，他没有左子树，而右子树在单旋之后深度不变（-1+1），而其他的点深度全部+1。如果再删掉根节点，全部的点深度-1。于是就可以使用线段树，维护每一个点的深度。
首先输入所有的操作，对于全部的值进行离散化，然后线段树就是对应离散化之后的点的深度。
最小值x，他的右子树的范围为[x+1,fa]。于是我们对这段区间-1，对全部区间+1。然后将x深度修改为1。最大值类似。如果要删除，全部区间-1。这样就可以解决问题了。
但是我们发现不好插入，具体来说应该是对于x，他的fa不好找，那么我们就记下来。然后在插入的时候，同时插入到set中，利用set来找fa。如果插入的不是最小值，那么可能为右子树，我们就把it--，判断这个点是否有右儿子，如果没有，就找到父亲了。否则，再找（it++）++。这个就是他的父亲，然后标记好。
set的insert()返回一个pair类型，first代表指针，指向插入的位置，second是bool，代表是否已有此元素。
<http://www.cnblogs.com/D-O-Time/p/7922491.html>
1 #include<set>
2 #include<cstdio>
3 #include<iostream>
4 #include<algorithm>
5 #define ls k*2
6 #define rs (k*2+1)
7 using namespace std;
8 const int MAXN=210000;
9 int m,sz,root,tp;
10 int v[MAXN],q[MAXN],op[MAXN];
11 int dep[MAXN*4],fa[MAXN],ch[MAXN][2];
12 set<int>st;
13 inline int gi() { int res; scanf("%d",&res); return res; }
14 void down(int k)
15 {
16 if(!dep[k])return ;
17 dep[ls]+=dep[k];
18 dep[rs]+=dep[k];
19 dep[k]=0;
20 }
21 void add(int k,int ll,int rr,int L,int R,int Val)
22 {
23 if(ll==L && rr==R) { dep[k]+=Val; return; }
24 down(k);
25 int mid=(ll+rr)/2;
26 if(R<=mid)
27 add(ls,ll,mid,L,R,Val);
28 else if(mid<L)
29 add(rs,mid+1,rr,L,R,Val);
30 else
31 {
32 add(ls,ll,mid,L,mid,Val);
33 add(rs,mid+1,rr,mid+1,R,Val);
34 }
35 }
36 void modify(int k,int ll,int rr,int p,int Val)
37 {
38 if(ll==rr) { dep[k]=Val; return;}
39 down(k);
40 int mid=(ll+rr)/2;
41 if(p<=mid)
42 return modify(ls,ll,mid,p,Val);
43 else
44 return modify(rs,mid+1,rr,p,Val);
45 }
46 int query(int k,int ll,int rr,int p)
47 {
48 if(ll==rr) return dep[k];
49 down(k);
50 int mid=(ll+rr)/2;
51 if(p<=mid)
52 return query(ls,ll,mid,p);
53 else
54 return query(rs,mid+1,rr,p);
55 }
56 int insert(int x)
57 {
58 set<int>::iterator it=st.insert(x).first;
59 if(root==0) {root=x; modify(1,1,tp,x,1); return 1;}
60 if(it!=st.begin())
61 {
62 if(!ch[*--it][1]) ch[fa[x]=*it][1]=x;
63 it++;
64 }
65 if(!fa[x]) ch[fa[x]=*++it][0]=x;
66 int deep=query(1,1,tp,fa[x])+1;
67 modify(1,1,tp,x,deep);
68 return deep;
69 }
70 int findmin()
71 {
72 int x=*st.begin(),res=query(1,1,tp,x);
73 if(x==root)return 1;
74 if(x+1<=fa[x]-1)
75 add(1,1,tp,x+1,fa[x]-1,-1);
76 add(1,1,tp,1,tp,1);
77 ch[fa[x]][0]=ch[x][1];
78 fa[ch[x][1]]=fa[x];
79 ch[fa[root]=x][1]=root;
80 root=x;
81 modify(1,1,tp,x,1);
82 return res;
83 }
84 void delmin()
85 {
86 printf("%d\n",findmin());
87 add(1,1,tp,1,tp,-1);
88 st.erase(root);
89 root=ch[root][1];
90 fa[root]=0;
91 }
92 int findmax()
93 {
94 int x=*st.rbegin(),res=query(1,1,tp,x);
95 if(x==root)return 1;
96 if(fa[x]+1<=x-1)
97 add(1,1,tp,fa[x]+1,x-1,-1);
98 add(1,1,tp,1,tp,1);
99 ch[fa[x]][1]=ch[x][0];
100 fa[ch[x][0]]=fa[x];
101 ch[fa[root]=x][0]=root;
102 root=x;
103 modify(1,1,tp,x,1);
104 return res;
105 }
106 void delmax()
107 {
108 printf("%d\n",findmax());
109 add(1,1,tp,1,tp,-1);
110 st.erase(root);
111 root=ch[root][0];
112 fa[root]=0;
113 }
114 int main()
115 {
116 scanf("%d",&m);
117 for(int i=1;i<=m;i++)
118 {
119 scanf("%d",&op[i]);
120 if(op[i]==1) q[++tp]=v[i]=gi();
121 }
122 sort(q+1,q+1+tp);
123 for(int i=1;i<=m;i++)
124 if(op[i]==1)
125 v[i]=lower_bound(q+1,q+1+tp,v[i])-q;
126 for(int i=1;i<=m;i++)
127 {
128 if(op[i]==1) { printf("%d\n",insert(v[i])); }
129 else if(op[i]==2) printf("%d\n",findmin());
130 else if(op[i]==3) printf("%d\n",findmax());
131 else if(op[i]==4) delmin();
132 else if(op[i]==5) delmax();
133 }
134 }