BZOJ2816 [ZJOI2012]网络

			    <div class="post_brief"><p>
听说是水水的splay，果然是。</p>

乍一看要用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)));
}
}
}