BZOJ2157 旅游

			    <div class="post_brief"><p>
去找水题于是找到这么一道恶心的代码题。其实应该可以用函数指针来优化一下代码量，不过懒得了。虽然复制粘贴导致调试了老半天。</p>

水水的链剖+线段树。然后tag打一打就好了。

最近是装备了高超的开坑技巧啊。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct seg {
int l, r, s, a, b, rv;
seg *ls, *rs;
inline void update() {
if (l + 1 < r) {
s = ls-> s + rs-> s;
a = min(ls-> a, rs-> a);
b = max(ls-> b, rs-> b);
if (rv) {
s = -s;
swap(a, b);
a = -a;
b = -b;
}
}
else
a = b = s;
}
inline void chgTag() {
s = -s;
swap(a, b);
a = -a;
b = -b;
rv ^= 1;
}
inline void downTag() {
if (rv) {
rv = 0;
if (l + 1 < r) {
ls-> chgTag();
rs-> chgTag();
}
}
}
};
struct edge {
int t, v;
edge *next;
};
const int maxn = 20009;
int n, m, fa[maxn], d[maxn], vl[maxn], ea[maxn], eb[maxn];
int sz[maxn], tc, fc[maxn], ch[maxn], cl[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
seg slst[maxn << 2], *sp(slst), *rt[maxn];
inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}
#define midp(p) ((p->l+p->r)>>1)
inline seg* sgtBuild(int l, int r) {
seg* p(sp ++);
p-> l = l;
p-> r = r;
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 v0) {
if (p-> l + 1 == p-> r) {
p-> rv = 0;
p-> s = v0;
}
else {
p-> downTag();
if (p0 < midp(p))
sgtChg(p-> ls, p0, v0);
else
sgtChg(p-> rs, p0, v0);
}
p-> update();
}
inline int sgtSum(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> s;
else {
p-> downTag();
if (r <= midp(p))
return sgtSum(p-> ls, l, r);
else if (l >= midp(p))
return sgtSum(p-> rs, l, r);
else
return sgtSum(p-> ls, l, midp(p)) + sgtSum(p-> rs, midp(p), r);
}
}
inline int sgtMin(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> a;
else {
p-> downTag();
if (r <= midp(p))
return sgtMin(p-> ls, l, r);
else if (l >= midp(p))
return sgtMin(p-> rs, l, r);
else
return min(sgtMin(p-> ls, l, midp(p)), sgtMin(p-> rs, midp(p), r));
}
}
inline int sgtMax(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
return p-> b;
else {
p-> downTag();
if (r <= midp(p))
return sgtMax(p-> ls, l, r);
else if (l >= midp(p))
return sgtMax(p-> rs, l, r);
else
return max(sgtMax(p-> ls, l, midp(p)), sgtMax(p-> rs, midp(p), r));
}
}
inline void sgtRev(seg* p, int l, int r) {
if (p-> l == l && p-> r == r)
p-> chgTag();
else {
p-> downTag();
if (r <= midp(p))
sgtRev(p-> ls, l, r);
else if (l >= midp(p))
sgtRev(p-> rs, l, r);
else
sgtRev(p-> ls, l, midp(p)), sgtRev(p-> rs, midp(p), r);
}
p-> update();
}
#define cpos(p) (d[p]-d[ch[fc[p]]])
void divide() {
static int q[maxn];
int hd(0), tl(1);
q[0] = 0;
memset(d, 0, sizeof(d));
d[0] = 1;
fa[0] = 0;
vl[0] = 0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (!d[e-> t]) {
fa[e-> t] = p;
d[e-> t] = d[p] + 1;
q[tl ++] = e-> t;
vl[e-> t] = e-> v;
}
}
tc = 0;
for (int ti = tl - 1; ti >= 0; – ti) {
int p(q[ti]), 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;
}
for (int i = 1; i <= tc; ++ i)
rt[i] = sgtBuild(0, cl[i]);
for (int i = 0; i < n; ++ i)
sgtChg(rt[fc[i]], cpos(i), vl[i]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif
scanf("%d", &amp;n);
memset(head, 0, sizeof(d));
for (int i = 1; i &lt; n; ++ i) {
	int w;
	scanf("%d%d%d", ea + i, eb + i, &amp;w);
	addEdge(ea[i], eb[i], w);
	addEdge(eb[i], ea[i], w);
}
divide();
scanf("%d", &amp;m);
while (m --) {
	char opt[7];
	int u, v, w;
	scanf("%s", opt);
	if (opt[0] == 'C') {
		scanf("%d%d", &amp;u, &amp;w);
		if (d[ea[u]] &gt; d[eb[u]])
			swap(ea[u], eb[u]);
		v = eb[u];
		sgtChg(rt[fc[v]], cpos(v), w);
	}
	else if (opt[0] == 'N') {
		scanf("%d%d", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; d[ch[fc[v]]]) {
				sgtRev(rt[fc[u]], 0, cpos(u) + 1);
				u = fa[ch[fc[u]]];
			}
			else {
				sgtRev(rt[fc[v]], 0, cpos(v) + 1);
				v = fa[ch[fc[v]]];
			}
		if (d[u] &gt; d[v])
			swap(u, v);
		if (u ^ v)
			sgtRev(rt[fc[u]], cpos(u) + 1, cpos(v) + 1);
	}
	else if (opt[0] == 'S') {
		int s(0);
		scanf("%d%d", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; d[ch[fc[v]]]) {
				s += sgtSum(rt[fc[u]], 0, cpos(u) + 1);
				u = fa[ch[fc[u]]];
			}
			else {
				s += sgtSum(rt[fc[v]], 0, cpos(v) + 1);
				v = fa[ch[fc[v]]];
			}
		if (d[u] &gt; d[v])
			swap(u, v);
		if (u ^ v)
			s += sgtSum(rt[fc[u]], cpos(u) + 1, cpos(v) + 1);
		printf("%d\n", s);
	}
	else if (opt[1] == 'I') {
		int s(0x3f3f3f3f);
		scanf("%d%d", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; d[ch[fc[v]]]) {
				s = min(s, sgtMin(rt[fc[u]], 0, cpos(u) + 1));
				u = fa[ch[fc[u]]];
			}
			else {
				s = min(s, sgtMin(rt[fc[v]], 0, cpos(v) + 1));
				v = fa[ch[fc[v]]];
			}
		if (d[u] &gt; d[v])
			swap(u, v);
		if (u ^ v)
			s = min(s, sgtMin(rt[fc[u]], cpos(u) + 1, cpos(v) + 1));
		printf("%d\n", s);
	}
	else if (opt[1] == 'A') {
		int s(-0x3f3f3f3f);
		scanf("%d%d", &amp;u, &amp;v);
		while (fc[u] ^ fc[v])
			if (d[ch[fc[u]]] &gt; d[ch[fc[v]]]) {
				s = max(s, sgtMax(rt[fc[u]], 0, cpos(u) + 1));
				u = fa[ch[fc[u]]];
			}
			else {
				s = max(s, sgtMax(rt[fc[v]], 0, cpos(v) + 1));
				v = fa[ch[fc[v]]];
			}
		if (d[u] &gt; d[v])
			swap(u, v);
		if (u ^ v)
			s = max(s, sgtMax(rt[fc[u]], cpos(u) + 1, cpos(v) + 1));
		printf("%d\n", s);
	}
}

}

Comments