【LG3721】[HNOI2017]单旋

题面

洛谷

题解

20pts

直接模拟\(spaly\)的过程即可。

100pts

可以发现单旋最大、最小值到根，手玩是有显然规律的，发现只需要几次\(link,cut\)，那么我们维护原树的父子关系以及一颗\(LCT\)。

对于插入操作，由于插入的值肯定在前驱的右儿子或后继的左儿子，用\(set\)维护前驱后继即可。

建议自己独立找出规律，这里不再赘述，这题其实细节还是挺多的。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <map>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar();

    if (ch == '-') w = -1, ch = getchar();

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

    return w * data;

}

const int MAX_N = 2e5 + 5;

struct Node { int ch[2], fa, size; bool rev; } t[MAX_N];

struct Clone { int v, ls, rs, fa; } _t[MAX_N];

int root, tot;

bool get(int x) { return t[t[x].fa].ch[1] == x; }

bool nroot(int x) { return t[t[x].fa].ch[0] == x || t[t[x].fa].ch[1] == x; }

void pushup(int x) { t[x].size = t[t[x].ch[0]].size + t[t[x].ch[1]].size + 1; }

void putrev(int x) { swap(t[x].ch[0], t[x].ch[1]); t[x].rev ^= 1; }

void pushdown(int x) {

	if (!t[x].rev) return ;

	if (t[x].ch[0]) putrev(t[x].ch[0]);

	if (t[x].ch[1]) putrev(t[x].ch[1]);

	t[x].rev = 0;

}

void rotate(int x) {

	int y = t[x].fa, z = t[y].fa, k = get(x);

	if (nroot(y)) t[z].ch[get(y)] = x;

	t[x].fa = z;

	t[t[x].ch[k ^ 1]].fa = y, t[y].ch[k] = t[x].ch[k ^ 1];

	t[y].fa = x, t[x].ch[k ^ 1] = y;

	pushup(y), pushup(x);

}

void splay(int x) {

	static int stk[MAX_N], top;

	stk[top = 1] = x;

	for (int i = x; nroot(i); i = t[i].fa) stk[++top] = t[i].fa;

	for (int i = top; i; --i) pushdown(stk[i]);

	while (nroot(x)) {

		int y = t[x].fa;

		if (nroot(y)) get(x) ^ get(y) ? rotate(x) : rotate(y);

		rotate(x);

	}

}

void access(int x) { for (int y = 0; x; y = x, x = t[x].fa) splay(x), t[x].ch[1] = y, pushup(x); }

void makeroot(int x) { access(x); splay(x); putrev(x); }

void link(int x, int y) { makeroot(x); t[x].fa = y; }

void split(int x, int y) { makeroot(x); access(y); splay(y); }

void cut(int x, int y) { split(x, y); t[x].fa = t[y].ch[0] = 0; pushup(y); }

set<int> st;

map<int, int> mp;

void insert(int v) {

	int x = ++tot;

	mp[v] = x, _t[x].v = v;

	if (st.size() == 0) return st.insert(v), root = x, (void)puts("1");

	set<int> :: iterator ite = st.upper_bound(v);

	if (ite == st.end() || _t[mp[*ite]].ls) {

		--ite;

		int tmp = mp[*ite];

		link(x, tmp), _t[tmp].rs = x, _t[x].fa = tmp;

	} else {

		int tmp = mp[*ite];

		link(x, tmp), _t[tmp].ls = x, _t[x].fa = tmp;

	}

	st.insert(v);

	return split(x, root), (void)printf("%d\n", t[root].size);

}

void splay_min() {

	int x = mp[*st.begin()];

	if (x == root) return (void)puts("1");

	split(x, root); printf("%d\n", t[root].size);

	cut(x, _t[x].fa); if (_t[x].rs) cut(x, _t[x].rs);

	link(x, root); if (_t[x].rs) link(_t[x].fa, _t[x].rs);

	_t[_t[x].fa].ls = _t[x].rs; if (_t[x].rs) _t[_t[x].rs].fa = _t[x].fa;

	_t[x].fa = 0, _t[root].fa = x, _t[x].rs = root;

	root = x;

}

void splay_max() {

    int x = mp[*st.rbegin()];

    if (x == root) return (void)puts("1");

    split(x, root); printf("%d\n", t[root].size);

    cut(x, _t[x].fa); if (_t[x].ls) cut(x, _t[x].ls);

    link(x, root); if (_t[x].ls) link(_t[x].ls, _t[x].fa);

    _t[_t[x].fa].rs = _t[x].ls; if (_t[x].ls) _t[_t[x].ls].fa = _t[x].fa;

    _t[x].fa = 0, _t[root].fa = x, _t[x].ls = root;

    root = x;

}

void del_min() {

    int x = mp[*st.begin()];

    if (root == x) {

		puts("1");

		if (_t[x].rs) cut(x, _t[x].rs);

		_t[_t[x].rs].fa = 0, root = _t[x].rs;

		st.erase(st.begin());

		return ;

	}

    split(x, root); printf("%d\n", t[root].size);

    cut(x, _t[x].fa); if (_t[x].rs) cut(x, _t[x].rs);

    if (_t[x].rs) link(_t[x].fa, _t[x].rs);

    _t[_t[x].fa].ls = _t[x].rs; if (_t[x].rs) _t[_t[x].rs].fa = _t[x].fa;

    st.erase(st.begin());

}

void del_max() {

    int x = mp[*st.rbegin()];

    if (root == x) {

		puts("1");

		if (_t[x].ls) cut(x, _t[x].ls);

		_t[_t[x].ls].fa = 0, root = _t[x].ls;

		st.erase(--st.end());

		return;

	}

    split(x, root); printf("%d\n", t[root].size);

    cut(x, _t[x].fa); if (_t[x].ls) cut(x, _t[x].ls);

    if (_t[x].ls) link(_t[x].ls, _t[x].fa);

    _t[_t[x].fa].rs = _t[x].ls; if(_t[x].ls) _t[_t[x].ls].fa = _t[x].fa;

    st.erase(--st.end());

}

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

#endif

	int M = gi();

    for (int i = 1; i <= M; i++) {

        int op = gi();

        switch (op) {

            case 1: insert(gi()); break;

            case 2: splay_min(); break;

            case 3: splay_max(); break;

            case 4: del_min(); break;

            case 5: del_max(); break;

        }

    }

	return 0;

}