BZOJ2816 [ZJOI2012]网络

听说是水水的splay，果然是。

乍一看要用lct，然后因为度数只有2，所以肯定是一条链。然后就直接用splay来维护。然后因为少写了句splay(v)导致多调了至少一节课的时间。我没救了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

#define upmax(_a_,_b_) { \
	if (_a_ < _b_) \
		_a_ = _b_; \
}

struct splay_node {
	int vl, vm, rv;
	splay_node *pt, *ls, *rs;
	inline void update() {
		vm = vl;
		if (ls)
			upmax(vm, ls-> vm);
		if (rs)
			upmax(vm, rs-> vm);
	}
	inline void fix() {
		if (rv) {
			swap(ls, rs);
			if (ls)
				ls-> rv ^= 1;
			if (rs)
				rs-> rv ^= 1;
			rv = 0;
		}
	}
};

typedef pair <int, int> edge;
typedef pair <edge, int> mpr;
typedef map <edge, int> emap;

const int maxn = 200009;
const int maxc = 13;

#define nid(_p_,_c_) ((_p_)+(_c_)*n)
#define eid(_e_) ((_e_)+eb)

splay_node slst[maxn], *sr[maxn];
int v[maxn], n, m, c, q, eb, nc[maxn][maxc], ce[maxn];
emap el;

inline void rot(splay_node* q) {
	splay_node *p(q-> pt), *a(p-> pt);
	if (a) {
		if (p == a-> ls) 
			a-> ls = q; 
		else 
			a-> rs = q; 
	}
	p-> pt = q;
	q-> pt = a;
	if (q == p-> ls) {
		if (q-> rs)
			q-> rs-> pt = p;
		p-> ls = q-> rs;
		q-> rs = p;
	}
	else {
		if (q-> ls)
			q-> ls-> pt = p;
		p-> rs = q-> ls;
		q-> ls = p;
	}
	p-> update();
	q-> update();
}

void splay(splay_node* q) {
	static splay_node* stc[maxn];
	int tst(1);
	stc[tst] = q;
	for (splay_node* p = q; p-> pt; p = p-> pt)
		stc[++ tst] = p-> pt;
	for (; tst; -- tst)
		stc[tst]-> fix();
	while (q-> pt) {
		splay_node *p(q-> pt);
		if (!p-> pt || !p-> pt-> pt)
			rot(q);
		else {
			if ((q == p-> ls) == (p == p-> pt-> ls)) {
				rot(p);
				rot(q);
			}
			else {
				rot(q);
				rot(q);
			}
		}
	}
}

splay_node* expose(splay_node* p) {
	splay(p);
	while (p) {
		p-> fix();
		if (p-> ls)
			p = p-> ls;
		else
			break;
	}
	return p;
}

void link(int e0, int u0, int v0) {
	splay_node *e(sr[e0]), *u(sr[u0]), *v(sr[v0]);
	splay(u);
	if (u-> fix(), u-> rs)
		u-> rv ^= 1;
	splay(v);
	if (v-> fix(), v-> ls)
		v-> rv ^= 1;
	e-> rv = 0;
	e-> ls = u;
	u-> pt = e;
	e-> rs = v;
	v-> pt = e;
	e-> update();
}

void cut(int e0) {
	splay_node* e(sr[e0]);
	splay(e);
	e-> fix();
	if (e-> ls) {
		e-> ls-> pt = 0;
		e-> ls = 0;
	}
	if (e-> rs) {
		e-> rs-> pt = 0;
		e-> rs = 0;
	}
	e-> update();
}

int query(int u0, int v0) {
	splay_node *u(sr[u0]), *v(sr[v0]);
	if (expose(u) != expose(v))
		return -1;
	if (u == v)
		return u-> vl;
	int ans(max(u-> vl, v-> vl));
	splay(u);
	splay(v);
	if (u == v-> ls) {
		if (u-> rs)
			upmax(ans, u-> rs-> vm);
	}
	else if (u == v-> rs) {
		if (u-> ls)
			upmax(ans, u-> ls-> vm);
	}
	return ans;
}

int main() {
	scanf("%d%d%d%d", &n, &m, &c, &q);
	eb = n * c;
	for (int i = 1; i <= eb + m; ++ i)
		sr[i] = slst + i;
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", v + i);
		for (int j = 0; j < c; ++ j) {
			splay_node* p(sr[nid(i, j)]);
			p-> vl = p-> vm = v[i];
		}
	}
	for (int i = 1; i <= m; ++ i) {
		splay_node* p(sr[eid(i)]);
		p-> vl = p-> vm = 0;
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		link(eid(i), nid(u, w), nid(v, w));
		ce[i] = w;
		++ nc[u][w];
		++ nc[v][w];
		if (u > v)
			swap(u, v);
		el. insert(mpr(edge(u, v), i));
	}
	while (q --) {
		int opt, u, v, w;
		scanf("%d", &opt);
		if (opt == 0) {
			scanf("%d%d", &u, &v);
			for (int i = 0; i < c; ++ i) {
				splay_node* p(sr[nid(u, i)]);
				p-> vl = v;
				p-> update();
				splay(p);
			}
		}
		else if (opt == 1) {
			scanf("%d%d%d", &u, &v, &w);
			if (u > v)
				swap(u, v);
			emap :: iterator it = el. find(edge(u, v));
			if (it == el. end())
				puts("No such edge.");
			else if (w == ce[it-> second])
				puts("Success.");
			else if (nc[u][w] > 1 || nc[v][w] > 1)
				puts("Error 1.");
			else if (expose(sr[nid(u, w)]) == expose(sr[nid(v, w)]))
				puts("Error 2.");
			else {
				int e(it-> second);
				-- nc[u][ce[e]];
				-- nc[v][ce[e]];
				cut(eid(e));
				ce[e] = w;
				++ nc[u][ce[e]];
				++ nc[v][ce[e]];
				link(eid(e), nid(u, w), nid(v, w));
				puts("Success.");
			}
		}
		else {
			scanf("%d%d%d", &w, &u, &v);
			printf("%d\n", query(nid(u, w), nid(v, w)));
		}
	}
}