BZOJ1180 [CROATIAN2009]OTOCI & BZOJ2843 极地旅行社

难得的水水的双倍题。

看上去是想考lct然后忘强制在线了么？那就直接预处理出形态然后链剖呗。当然我还没有达到mhy这种认为lct比tcd好写的水平。

中间还把修改写挂了一次，然后1180的询问数是2843的3倍又re了一次。晕。

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

using namespace std;

struct edge {
	int t;
	edge *next;
};
struct seg {
	int l, r, s[2];
	seg *ls, *rs;
};
struct query {
	char o;
	int a, b, s;
};

const int maxn = 30009;
const int maxm = 300009;

int n, m, r[maxn], d[maxn], v[maxn], u[maxn];
int fa[maxn], sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn];
int qret[2];
seg slst[maxn << 2], *sp(slst), *rt[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
query q[maxm];

inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

int getRoot(int x) {
	register int p, q;
	for (p = r[x]; r[p] ^ p; p = r[p]);
	for (; x ^ p; q = r[x], r[x] = p, x = q);
	return x;
}

void divide(int p0) {
	static int q[maxn];
	int hd(0), tl(1);
	q[0] = p0;
	d[p0] = 1;
	fa[p0] = 0;
	while (hd < tl) {
		int p(q[hd ++]);
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> t != fa[p]) {
				d[e-> t] = d[p] + 1;
				fa[e-> t] = p;
				q[tl ++] = e-> t;
			}
	}
	for (int i = tl - 1; i >= 0; -- i) {
		int p(q[i]), z(-1);
		sz[p] = 1;
		for (edge* e = head[p]; e; e = e-> next)
			if (e-> t != fa[p]) {
				sz[p] += sz[e-> t];
				if (z == -1 || sz[e-> t] > sz[z])
					z = e-> t;
			}
		if (z == -1)
			cl[fc[p] = ++ tc] = 1;
		else
			++ cl[fc[p] = fc[z]];
		ch[fc[p]] = p;
	}
}

#define cpos(_p_) (d[_p_]-d[ch[fc[_p_]]])
#define midp(p) ((p->l+p->r)>>1)

inline seg* sgtBuild(int l, int r) {
	seg* p(sp ++);
	p-> l = l;
	p-> r = r;
	p-> s[0] = r - l;
	p-> s[1] = 0;
	if (l + 1 < r) {
		p-> ls = sgtBuild(l, midp(p));
		p-> rs = sgtBuild(midp(p), r);
	}
	return p;
}
inline void sgtChg(seg* p, int p0, int i, int v) {
	if (p-> l + 1 == p-> r)
		p-> s[i] = v;
	else {
		if (p0 < midp(p))
			sgtChg(p-> ls, p0, i, v);
		else
			sgtChg(p-> rs, p0, i, v);
		p-> s[i] = p-> ls-> s[i] + p-> rs-> s[i];
	}
}
inline void sgtQry(seg* p, int l, int r) {
	if (p-> l == l && p-> r == r) {
		qret[0] += p-> s[0];
		qret[1] += p-> s[1];
	}
	else if (r <= midp(p))
		sgtQry(p-> ls, l, r);
	else if (l >= midp(p))
		sgtQry(p-> rs, l, r);
	else {
		sgtQry(p-> ls, l, midp(p));
		sgtQry(p-> rs, midp(p), r);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		r[i] = i;
		scanf("%d", v + i);
		u[i] = 1;
	}
	scanf("%d", &m);
	for (int i = 0; i < m; ++ i) {
		char opt[11];
		scanf("%s%d%d", opt, &q[i]. a, &q[i]. b);
		q[i]. o = opt[0];
		if (q[i]. o == 'b') {
			if (getRoot(q[i]. a) ^ getRoot(q[i]. b)) {
				q[i]. s = 1;
				r[getRoot(q[i]. a)] = getRoot(q[i]. b);
				addEdge(q[i]. a, q[i]. b);
				addEdge(q[i]. b, q[i]. a);
			}
			else {
				q[i]. s = 0;
			}
		}
	}
	memset(d, 0, sizeof(d));
	tc = 0;
	for (int i = 1; i <= n; ++ i)
		if (!d[i])
			divide(i);
	for (int i = 1; i <= tc; ++ i)
		rt[i] = sgtBuild(0, cl[i]);
	for (int i = 1; i <= n; ++ i)
		sgtChg(rt[fc[i]], cpos(i), 1, v[i]);
	for (int i = 0; i < m; ++ i)
		if (q[i]. o == 'b') {
			if (q[i]. s) {
				if (d[q[i]. a] > d[q[i]. b])
					swap(q[i]. a, q[i]. b);
				u[q[i]. b] = 0;
				sgtChg(rt[fc[q[i]. b]], cpos(q[i]. b), 0, 0);
				puts("yes");
			}
			else
				puts("no");
		}
		else if (q[i]. o == 'p') {
			sgtChg(rt[fc[q[i]. a]], cpos(q[i]. a), 1, q[i]. b);
		}
		else if (q[i]. o == 'e') {
			int u(q[i]. a), v(q[i]. b);
			if (getRoot(u) != getRoot(v)) {
				puts("impossible");
			}
			else {
				qret[0] = qret[1] = 0;
				while (fc[u] ^ fc[v]) {
					if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
						sgtQry(rt[fc[u]], 0, cpos(u) + 1);
						u = fa[ch[fc[u]]];
					}
					else {
						sgtQry(rt[fc[v]], 0, cpos(v) + 1);
						v = fa[ch[fc[v]]];
					}
				}
				if (d[u] > d[v])
					swap(u, v);
				sgtQry(rt[fc[u]], cpos(u), cpos(v) + 1);
				qret[0] -= :: u[u];
				if (qret[0])
					puts("impossible");
				else
					printf("%d\n",  qret[1]);
			}
		}
}