4825: [Hnoi2017]单旋

题意：有趣的spaly
hnoi2017刚出来我就去做，当时这题作死用了ett，调了5节课没做出来然后发现好像直接用lct就行了然后弃掉了...
md用lct不知道好写到哪里去了1h就写完了
原树的父亲孩子可以直接维护
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

#define lc t[x].ch[0]

#define rc t[x].ch[1]

#define pa t[x].fa

#define fir first

#define sec second

const int N = 4e5+5, INF=1e9+5;

inline int read() {

	char c=getchar(); int x=0,f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

namespace lct {

	struct meow{int ch[2], fa, rev, size;} t[N];

	inline int wh(int x) {return t[pa].ch[1] == x;}

	inline int isr(int x) {return t[pa].ch[0] != x && t[pa].ch[1] != x;}

	inline void update(int x) {t[x].size = t[lc].size + t[rc].size + 1;}

	inline void rever(int x) {swap(lc, rc); t[x].rev ^= 1;}

	inline void pushdn(int x) {

		if(t[x].rev) {

			if(lc) rever(lc);

			if(rc) rever(rc);

			t[x].rev = 0;

		}

	}

	void pd(int x) {if(!isr(x)) pd(pa); pushdn(x);}

	inline void rotate(int x) {

		int f = t[x].fa, g = t[f].fa, c = wh(x);

		if(!isr(f)) t[g].ch[wh(f)] = x; t[x].fa = g;

		t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa = f;

		t[x].ch[c^1] = f; t[f].fa = x;

		update(f); update(x);

	}

	void splay(int x) {

		pd(x);

		for(; !isr(x); rotate(x))

			if(!isr(pa)) rotate(wh(x) == wh(pa) ? pa : x);

	}

	void access(int x) {

		for(int y=0; x; y=x, x=pa) splay(x), rc=y, update(x);

	}

	void maker(int x) {

		access(x); splay(x); rever(x);

	}

	void link(int x, int y) { if(!x || !y) return;

		maker(x); t[x].fa = y;

	}

	void cut(int x, int y) { if(!x || !y) return;

		maker(x); access(y); splay(y);

		t[x].fa = t[y].ch[0] = 0; update(y);

	}

	int que(int x, int y) {

		maker(x); access(y); splay(y);

		return t[y].size;

	}

} using lct::link; using lct::cut; using lct::que;

int root;

struct info {int fa, l, r;} t[N];

set< pair<int, int> > S;

set< pair<int, int> >::iterator i1, i2;

int tot;

void insert(int k) {

	++tot;

	i1 = i2 = S.insert(make_pair(k, tot)).fir;

	int a = 0, b = 0, x = tot;

	if(i1 != S.begin()) a = (--i1)->sec;

	if(++i2 != S.end()) b = i2->sec;

	if(!a && !b) root = x;

	else if(a && t[a].r == 0) t[a].r = x, t[x].fa = a, link(a, x);

	else if(b && t[b].l == 0) t[b].l = x, t[x].fa = b, link(b, x);

	printf("%d\n", que(root, x));

}

void spa_min() {

	int x = S.begin()->sec, r = t[x].r, p = t[x].fa;

	printf("%d\n", que(root, x));

	if(x == root) return;

	cut(x, p); cut(x, r); link(p, r); link(x, root);

	t[x].r = root; t[root].fa = x; t[r].fa = p; t[p].l = r;

	root = x;

}

void spa_max() {

	i1 = S.end();

	int x = (--i1)->sec, l = t[x].l, p = t[x].fa;

	printf("%d\n", que(root, x));

	if(x == root) return;

	cut(x, p); cut(x, l); link(p, l); link(x, root);

	t[x].l = root; t[root].fa = x; t[l].fa = p; t[p].r = l;

	root = x;

}

void del_min() {

	i1 = S.begin();

	int x = S.begin()->sec, r = t[x].r, p = t[x].fa; //printf("\ndel_min %d  %d  %d\n", x, r, p);

	printf("%d\n", que(root, x));

	if(x == root) {

		cut(x, r); t[r].fa = 0; root = r;

	} else {

		cut(x, p); cut(x, r); link(p, r);

		t[r].fa = p; t[p].l = r;

	}

	S.erase(i1);

}

void del_max() {

	i1 = S.end();

	int x = (--i1)->sec, l = t[x].l, p = t[x].fa;

	printf("%d\n", que(root, x));

	if(x == root) {

		cut(x, l); t[l].fa = 0; root = l;

	} else {

		cut(x, p); cut(x, l); link(p, l);

		t[l].fa = p; t[p].r = l;

	}

	S.erase(i1);

}

int m, type, k;

int main() {

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

	m = read();

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

		type=read(); //printf("hi %d  %d\n", i, type);

		if(type == 1) k = read(), insert(k);

		if(type == 2) spa_min();

		if(type == 3) spa_max();

		if(type == 4) del_min();

		if(type == 5) del_max();

	}

}
巴特西

bzoj 4825: [Hnoi2017]单旋 [lct]

4825: [Hnoi2017]单旋

最新文章

热门文章
