题目
毒瘤的(HNOI)，其实想清楚了不难
做法
首先这题不去考虑单纯(splay)的做法，单旋肯定会卡掉，不知道具体卡了多少分
这题是只用单旋，当然去手玩一下，这时候你就知道上旋最小值和最大值的子树变化规律了，线段树维护深度
然后其实就只考虑插入就好了，把(splay)的权值排列一下，显然相邻两个在(splay)里也相邻
也就是只有两种形态，每种形态能插的地方只有一个，且另一种形态这个地方不为空，枚举一下就好了
用(LCT)维护深度也是种经典套路，但用线段树更有意思
My complete code
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
typedef int LL;
const LL maxn=1e6;
inline LL Read(){
LL x(0),f(1);char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
set<LL> Set;
struct node{
LL op,a;
}q[maxn];
LL n,tot,root,Root,nod;
LL lazy[maxn],dep[maxn],lc[maxn],rc[maxn],b[maxn],son[maxn][2],fa[maxn];
inline void Pushdown(LL now){
if(lazy[now]){
LL val(lazy[now]); lazy[now]=0;
if(!lc[now])lc[now]=++nod;
if(!rc[now])rc[now]=++nod;
lazy[lc[now]]+=val,dep[lc[now]]+=val;
lazy[rc[now]]+=val,dep[rc[now]]+=val;
}
}
void Add(LL &now,LL l,LL r,LL lt,LL rt,LL val){
if(!now) now=++nod;
if(lt<=l&&rt>=r){
dep[now]+=val,lazy[now]+=val;
return;
}
Pushdown(now);
LL mid(l+r>>1);
if(lt<=mid) Add(lc[now],l,mid,lt,rt,val);
if(rt>mid) Add(rc[now],mid+1,r,lt,rt,val);
}
void Change(LL &now,LL l,LL r,LL c,LL val){
if(!now) now=++nod;
if(l==r){
dep[now]=val;
return;
}
Pushdown(now);
LL mid(l+r>>1);
if(c<=mid) Change(lc[now],l,mid,c,val);
else Change(rc[now],mid+1,r,c,val);
}
LL Query(LL now,LL l,LL r,LL c){
if(l==r) return dep[now];
Pushdown(now);
LL mid(l+r>>1);
if(c<=mid)
return Query(lc[now],l,mid,c);
else
return Query(rc[now],mid+1,r,c);
}
inline LL Insert(LL x){
set<LL> ::iterator it=Set.insert(x).first;
if(!root){
Root=x; Change(root,1,tot,x,1); return 1;
}
if(it!=Set.begin()){
if(!son[*--it][1]){
son[*it][1]=x;
fa[x]=*it;
}
++it;
}
if(!fa[x]){
son[*++it][0]=x;
fa[x]=*it;
}
LL deep(Query(root,1,tot,fa[x])+1);
Change(root,1,tot,x,deep);
return deep;
}
inline LL Splaymin(){
LL x=*Set.begin(),deep(Query(root,1,tot,x));
if(x==Root) return 1;
if(x+1<=fa[x]-1)
Add(root,1,tot,x+1,fa[x]-1,-1);
Add(root,1,tot,1,tot,1);
son[fa[x]][0]=son[x][1];
fa[son[x][1]]=fa[x];
son[x][1]=Root;
fa[Root]=x;
Root=x;
Change(root,1,tot,Root,1);
return deep;
}
inline void Delmin(){
printf("%d
",Splaymin());
Add(root,1,tot,1,tot,-1);
Set.erase(Root);
LL tmp(son[Root][1]); son[Root][1]=fa[Root]=0; Root=tmp;
fa[Root]=0;
}
inline LL Splaymax(){
LL x=*Set.rbegin(),deep(Query(root,1,tot,x));
if(x==Root) return 1;
if(fa[x]+1<=x-1)
Add(root,1,tot,fa[x]+1,x-1,-1);
Add(root,1,tot,1,tot,1);
son[fa[x]][1]=son[x][0];
fa[son[x][0]]=fa[x];
son[x][0]=Root;
fa[Root]=x;
Root=x;
Change(root,1,tot,Root,1);
return deep;
}
inline void Delmax(){
printf("%d
",Splaymax());
Add(root,1,tot,1,tot,-1);
Set.erase(Root);
LL tmp(son[Root][0]); son[Root][0]=fa[Root]=0; Root=tmp;
fa[Root]=0;
}
int main(){
n=Read();
for(LL i=1;i<=n;++i){
q[i].op=Read();
if(q[i].op==1)
b[++tot]=q[i].a=Read();
}
sort(b+1,b+1+tot),tot=unique(b+1,b+1+tot)-b-1;
for(LL i=1;i<=n;++i){
if(q[i].op==1) printf("%d
",Insert(lower_bound(b+1,b+1+tot,q[i].a)-b));
else if(q[i].op==2) printf("%d
",Splaymin());
else if(q[i].op==3) printf("%d
",Splaymax());
else if(q[i].op==4) Delmin();
else Delmax();
}
return 0;
}