Legend
Link ( extrm{to LOJ})。
维护一颗 spaly，支持一些操作并计算操作的代价：
- 插入一个数字 (v)，保证与之前不同，代价为新节点的深度；
- 单旋最小值到根，代价为单旋前的深度；
- 单旋最大值到根，代价为单旋前的深度；
- 单旋并删除最小值，代价为单旋前的深度；
- 单旋并删除最大值，代价为单旋前的深度；
操作总数 (m le 10^5)。
Editorial
手玩一下，发现：
- 插入一定是选前驱或后缀深度较大那个插到儿子去。
- 单旋最小值是把最小值右子树接到父亲去，并把最小值转到根，把整棵树接到它右子树。
- 单旋最大值是把最大值左子树接到父亲去，并把最大值转到根，把整棵树接到它左子树。
直接用 ( m{LCT}) 维护。
Code
随便用个 ( m{set}) 维护前驱后继就行了。
代码无比冗长。
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int root;
const int MX = 1e5 + 233;
namespace LCT{
#define lch(x) ch[x][0]
#define rch(x) ch[x][1]
int fa[MX] ,ch[MX][2] ,rev[MX] ,size[MX];
int get(int x){return x == ch[fa[x]][1];}
int Nroot(int x){return get(x) || x == ch[fa[x]][0];}
void pushup(int x){size[x] = 1 + size[lch(x)] + size[rch(x)];}
void dorev(int x){rev[x] ^= 1; std::swap(lch(x) ,rch(x));}
void pushdown(int x){
if(rev[x]){
if(lch(x)) dorev(lch(x));
if(rch(x)) dorev(rch(x));
rev[x] = 0;
}
}
void rotate(int x){
int f = fa[x] ,gf = fa[f] ,which = get(x) ,W = ch[x][!which];
if(Nroot(f)) ch[gf][get(f)] = x;
ch[x][!which] = f ,ch[f][which] = W;
if(W) fa[W] = f;
fa[f] = x ,fa[x] = gf ,pushup(f) ,pushup(x);
}
int stk[MX] ,dep;
void splay(int x){
int f = x; stk[++dep] = f;
while(Nroot(f)) stk[++dep] = f = fa[f];
while(dep) pushdown(stk[dep--]);
while(Nroot(x)){
if(Nroot(f = fa[x])) rotate(get(x) == get(f) ? f : x);
rotate(x);
}pushup(x);
}
void access(int x){
for(int y = 0 ; x ; x = fa[y = x])
splay(x) ,rch(x) = y ,pushup(x);
}
void makeroot(int x){access(x) ,splay(x) ,dorev(x);}
int qdep(int x){access(x) ,splay(root); return size[root];}
void link(int f ,int son){
makeroot(son);
fa[son] = f;
// debug("link %d %d
" ,f ,son);
}
void cut(int x ,int y){
// debug("cut %d %d
" ,x ,y);
makeroot(x) ,access(y) ,splay(x);
rch(x) = fa[y] = 0; pushup(x);
}
#undef lch
#undef rch
}using namespace LCT;
struct number{
int value ,id;
number(int v ,int _id = -1){value = v ,id = _id;}
bool operator <(const number &B)const{
return value < B.value;
}
};
int tr[MX][2] ,pa[MX];
std::set<number> cur;
void spaly_min(){
auto aim = cur.begin();
if(cur.size() == 1) return;
int x = aim->id;
printf("%d
" ,qdep(aim->id));
if(root != x && tr[x][1]){
pa[tr[x][1]] = pa[x];
tr[pa[x]][0] = tr[x][1];
cut(x ,tr[x][1]);
cut(pa[x] ,x);
link(pa[x] ,tr[x][1]);
tr[x][1] = pa[x] = 0;
link(x ,root);
tr[x][1] = root;
pa[root] = x ,root = x;
makeroot(x);
}
else if(root != x && !tr[x][1]){
cut(pa[x] ,x);
tr[pa[x]][0] = 0;
pa[x] = 0;
link(x ,root);
tr[x][1] = root ,pa[root] = x ,root = x;
makeroot(x);
}
else{}
makeroot(root);
}
void spaly_max(){
auto aim = prev(cur.end());
if(cur.size() == 1) return;
int x = aim->id;
printf("%d
" ,qdep(aim->id));
if(root != x && tr[x][0]){
pa[tr[x][0]] = pa[x];
tr[pa[x]][1] = tr[x][0];
cut(x ,tr[x][0]);
cut(pa[x] ,x);
link(pa[x] ,tr[x][0]);
tr[x][0] = pa[x] = 0;
link(x ,root);
tr[x][0] = root;
pa[root] = x ,root = x;
makeroot(x);
}
else if(root != x && !tr[x][0]){
cut(pa[x] ,x);
tr[pa[x]][1] = 0;
pa[x] = 0;
link(x ,root);
tr[x][0] = root ,pa[root] = x ,root = x;
makeroot(x);
}
else{}
makeroot(root);
}
int main(){
__FILE(danxuan);
int m = read();
for(int I = 1 ; I <= m ; ++I){
debug("%d
" ,I);
int op = read();
if(op == 1){
int k = read();
if(cur.empty()){
cur.insert(number(k ,I));
root = I;
printf("1
");
continue;
}
auto nxt = cur.lower_bound(k);
if(nxt == cur.end()){
--nxt;
tr[nxt->id][1] = I;
pa[I] = nxt->id;
link(nxt->id ,I);
}
else{
if(nxt == cur.begin()){
tr[nxt->id][0] = I;
pa[I] = nxt->id;
link(nxt->id ,I);
}
else{
int predep = qdep(prev(nxt)->id),
nxtdep = qdep(nxt->id);
if(predep > nxtdep){
--nxt;
tr[nxt->id][1] = I;
pa[I] = nxt->id;
link(nxt->id ,I);
}
else{
tr[nxt->id][0] = I;
pa[I] = nxt->id;
link(nxt->id ,I);
}
}
}
printf("%d
" ,qdep(I));
cur.insert(number(k ,I));
}
if(op == 2){
spaly_min();
}if(op == 3){
spaly_max();
}if(op == 4){
spaly_min();
cur.erase(cur.begin());
if(root){
cut(root ,tr[root][1]);
pa[tr[root][1]] = 0;
root = tr[root][1];
makeroot(root);
}else root = 0;
}if(op == 5){
spaly_max();
cur.erase(prev(cur.end()));
if(root){
cut(root ,tr[root][0]);
pa[tr[root][0]] = 0;
root = tr[root][0];
makeroot(root);
}else root = 0;
}
}
return 0;
}