[Luogu P3721] [BZOJ 4825] [AH2017 HNOI2017]单旋

洛谷传送门

BZOJ传送门

题目描述

H国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。伸展树（splay）是一种数据结构，因为代码好写，功能多，效率高，掌握这种数据结构成为了H国的必修技能。有一天，邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说，splay如果写成单旋的，将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理，但还是有H国的人相信了，小H就是其中之一，spaly马上成为他的信仰。而H国的国王，自然不允许这样的风气蔓延，国王构造了一组数据，数据由$m$m（不超过$10^5$105）个操作构成，他知道这样的数据肯定打垮spaly，但是国王还有很多很多其他的事情要做，所以统计每个操作

所需要的实际代价的任务就交给你啦。数据中的操作分为$5$5种：

1. 插入操作：向当前非空spaly中插入一个关键码为$key$key的新孤立节点。插入方法为，先让$key$key和根比较，如果$key$key比根小，则往左子树走，否则往右子树走，如此反复，直到某个时刻，$key$key比当前子树根$x$x小，而$x$x的左子树为空，那就让$key$key成为x的左孩子；或者$key$key比当前子树根$x$x大，而$x$x的右子树为空，那就让$key$key成为$x$x的右孩子。该操作的代价为：插入后，$key$key的深度。特别地，若树为空，则直接让新节点成为一个单个节点的树。（各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。）

2. 单旋最小值:将spaly中关键码最小的元素$x_{min}$xmin​单旋到根。操作代价为：单旋前$x{min}$xmin的深度。（对于单旋操作的解释见末尾对spaly的描述。）

3. 单旋最大值:将spaly中关键码最大的元素$x_{max}$xmax​单旋到根。操作代价为：单旋前$x_{max}$xmax​的深度。

4. 单旋删除最小值：先执行$2$2号操作，然后把根删除。由于$2$2号操作之后，根没有左子树，所以直接切断根和右子树的联系即可。（具体见样例解释）。操作代价同$2$2号操作。

5. 单旋删除最大值：先执行$3$3号操作，然后把根删除。操作代价同3号操作。

   

对于不是H国的人，你可能需要了解一些spaly的知识，才能完成国王的任务：

1. spaly是一棵二叉树，满足对于任意一个节点$x$x，它如果有左孩子$l_x$lx​，那么$l_x$lx​的关键码小于$x$x的关键码。如果有右孩子$r_x$rx​，那么$r_x$rx​的关键码大于$x$x的关键码。
2. 一个节点在spaly的深度定义为：从根节点到该节点的路径上一共有多少个节点（包括自己）。
3. 单旋操作是对于一棵树上的节点$x$x来说的。一开始，设$f$f为$x$x在树上的父亲。如果$x$x为$f$f的左孩子，那么执行$zig(x)$zig(x)操作（如上图中，左边的树经过$zig(x)$zig(x)变为了右边的树）,否则执行$zag(x)$zag(x)操作（在上图中，将右边的树经过$zag(f)$zag(f)就变成了左边的树）。每当执行一次$zig(x)$zig(x)或者$zag(x)$zag(x),$x$x的深度减小$1$1，如此反复，直到$x$x为根。总之，单旋$x$x就是通过反复执行$zig$zig和$zag$zag将$x$x变为根。

输入输出格式

输入格式：

输入文件名为 splay.in。

第一行单独一个正整数 $m$m ($1 \le m \le 10^5$1≤m≤105)。

接下来 $m$m 行，每行描述一个操作：首先是一个操作编号 $c$c（ $1\le c\le 5$1≤c≤5），既问题描述中给出的 $5$5 种操作中的编号，若 $c = 1$c=1，则再输入一个非负整数 $key$key，表示新插入节点的关键码。

输出格式：

输出文件名为 splay.out。

输出共 $m$m 行，每行一个整数，第 $i$i 行对应第 $i$i 个输入的操作的代价。

输入输出样例

输入样例#1：

5
1 2
1 1
1 3
4 
5

输出样例#1：

1 
2 
2
2 
2

说明

20%的数据满足： $1 \le m \le 1000$1≤m≤1000。

另外 30%的数据满足： 不存在 $4,5$4,5 操作。

100%的数据满足： $1\le m\le 10^5$1≤m≤105； $1\le key\le 10^9$1≤key≤109。 所有出现的关键码互不相同。 任何一个非插入操作，一定保证树非空。 在未执行任何操作之前，树为空。

解题分析

可以手玩一组单旋的样例：

然后我们发现在单旋最大/最小值的时候似乎改变了父子关系的只有最大/最小点及它们的父节点、子节点和根节点？ 我们就可以方便地用$LCT$LCT维护整棵$spaly$spaly的形态， 直接$link、cut$link、cut完成一个操作。

至于插入， 很容易发现我们将会把这个点插在其前驱后继深度更深的一个点上。我们直接用$LCT$LCT维护链上点数量即可。

细节很多， 注意理清思路， 不然就会又$WA$WA又$TLE$TLE 又$RE$RE…

代码如下：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <set>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 100500
template <class T>
IN void in(T &x)
{
    x = 0; static char c; c = gc;
    for (; !isdigit(c); c = gc);
    for (;  isdigit(c); c = gc)
    x = (x << 1) + (x << 3) + c - 48;
}
int q, cnt, top, len, root;
int sta[MX], buf[MX], son[MX][2], fat[MX];
std::set <int> st;
std::set <int>::iterator it;
struct Node {int son[2], fat, siz; bool rev;} tree[MX];
struct OPT {int typ, val;} opt[MX];
namespace LCT
{
    #define ls tree[now].son[0]
    #define rs tree[now].son[1]
    #define dad tree[now].fat
    IN bool get(R int now) {return tree[dad].son[1] == now;}
    IN bool nroot(R int now) {return tree[dad].son[0] == now || tree[dad].son[1] == now;}
    IN void pushup(R int now) {tree[now].siz = 1 + tree[ls].siz + tree[rs].siz;}
    IN void pushrev(R int now) {std::swap(ls, rs), tree[now].rev ^= 1;}
    IN void pushdown(R int now) {if(tree[now].rev) pushrev(ls), pushrev(rs), tree[now].rev = false;}
    IN void rotate(R int now)
    {
        R int fa = dad, grand = tree[fa].fat;
        R bool dir = get(now);
        tree[fa].son[dir] = tree[now].son[dir ^ 1];
        tree[tree[now].son[dir ^ 1]].fat = fa;
        tree[now].fat = grand;
        if(nroot(fa)) tree[grand].son[get(fa)] = now;
        tree[fa].fat = now;
        tree[now].son[dir ^ 1] = fa;
        pushup(fa);
    }
    IN void splay(R int now)
    {
        R int tmp = now, fa;
        sta[top = 1] = now;
        W (nroot(now)) sta[++top] = now = dad;
        W (top) pushdown(sta[top--]);
        now = tmp;
        W (nroot(now))
        {
            fa = dad;
            if(nroot(fa)) rotate(get(now) == get(fa) ? fa : now);
            rotate(now);
        }
        pushup(now);
    }
    IN void access(R int now)
    {
        for (R int x = 0; now; x = now, now = dad)
        splay(now), rs = x, pushup(now);
    }
    IN void makeroot(R int x)
    {
        access(x);
        splay(x);
        pushrev(x);
    }
    IN void split(R int x, R int y)
    {
        makeroot(x);
        access(y);
        splay(y);
    }
    IN void link(R int x, R int y) {if(!x || !y) return; makeroot(x); tree[x].fat = y;}
    IN void cut(R int x, R int y) {if(!x || !y) return; split(x, y); tree[y].son[0] = tree[x].fat = 0; pushup(y); }
    IN int query(R int x) {split(root, x); return tree[x].siz;}
    #undef ls
    #undef rs
    #undef dad
}
int main(void)
{
    int best, pos, bf, lson, rson, dad; in(q);
    for (R int i = 1; i <= q; ++i)
    {
        in(opt[i].typ);
        if(opt[i].typ == 1) in(opt[i].val), buf[++len] = opt[i].val;
    }
    std::sort(buf + 1, buf + 1 + len);
    for (R int i = 1; i <= q; ++i) if(opt[i].typ == 1) opt[i].val = std::lower_bound(buf + 1, buf + 1 + len, opt[i].val) - buf;
    for (R int i = 1; i <= q; ++i)
    {
        if(opt[i].typ == 1)
        {
            best = 0;
            if(st.empty()) {puts("1"); st.insert(opt[i].val), root = opt[i].val; continue;}
            it = st.lower_bound(opt[i].val);
            if(it != st.end())
            {
                best = LCT::query(*it);
                pos = *it;
            }
            if(it != st.begin())
            {
                it--;
                if(best < (bf = LCT::query(*it))) best = bf, pos = *it;
            }
            printf("%d\n", best + 1);
            st.insert(opt[i].val), LCT::link(opt[i].val, pos);
            fat[opt[i].val] = pos, son[pos][opt[i].val > pos] = opt[i].val;
        }
        else if(opt[i].typ == 2)
        {
            pos = *st.begin(), rson = son[pos][1], dad = fat[pos];
            printf("%d\n", LCT::query(pos));
            if(root ^ pos)
            {
                LCT::cut(pos, dad), LCT::cut(pos, rson), LCT::link(pos, root), LCT::link(rson, dad);
                fat[root] = pos, fat[pos] = 0, fat[rson] = dad, son[pos][1] = root;
                root = pos, son[dad][0] = rson;
            }
        }
        else if(opt[i].typ == 3)
        {
            pos = *st.rbegin(), lson = son[pos][0], dad = fat[pos];
            printf("%d \n", LCT::query(pos));
            if(root ^ pos)
            {
                LCT::cut(pos, dad), LCT::cut(pos, lson), LCT::link(pos, root), LCT::link(lson, dad);
                fat[root] = pos, fat[pos] = 0, fat[lson] = dad, son[pos][0] = root;
                root = pos, son[dad][1] = lson;
            }
        }
        else if(opt[i].typ == 4)
        {
            pos = *st.begin(), rson = son[pos][1], dad = fat[pos];
            st.erase(st.begin()); printf("%d\n", LCT::query(pos));
            LCT::cut(pos, dad);
            LCT::cut(pos, rson);
            LCT::link(rson, dad);
            fat[rson] = dad, son[pos][0] = son[pos][1] = fat[pos] = 0;
            son[dad][0] = rson;
            if(root == pos) root = rson;
        }
        else if(opt[i].typ == 5)
        {
            it = st.end(); it--;//st.rbegin()不能直接erase...... 会CE
            pos = *it, lson = son[pos][0], dad = fat[pos];
            st.erase(it); printf("%d\n", LCT::query(pos));
            LCT::cut(pos, dad), LCT::cut(pos, lson), LCT::link(lson, dad);
            fat[lson] = dad, son[pos][0] = son[pos][1] = fat[pos] = 0;
            son[dad][1] = lson;
            if(root == pos) root = lson;
        }
    }
}