这题真是十分难写啊 不管是点分治还是括号序列都有一堆细节。。
点分治：时空复杂度$O(n\log^2n)$，常数巨大
主要就是3个堆的初始状态
C堆：每个节点一个，为子树中的点到它父亲的距离的堆。
B堆：每个节点一个，存所有儿子的堆的堆顶。特别地，如果该节点关灯，那么将加入一个0；如果没有元素，堆顶应返回负数。
A堆：全局一个，存所有B堆的最大值和最小值之和。特别地，如果B堆不足两个，返回负数。
这样，我们一开始需要关闭所有的等，即对所有点调用一次turn_off。由于堆顶返回的是负数，删除时找不到的话直接忽略即可，如果返回的是0，则有可能误删有用的信息。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = + , logn = ;
struct RMQ {
int n, f[logn + ][N * ], Log[N * ];
void init(int n) {
Log[] = -;
for(int i = ; i <= n; i++) Log[i] = Log[i >> ] + ;
this->n = n;
for(int i = ; ( << i) < n; i++) {
for(int j = ; j <= n; j++) {
f[i][j] = min(f[i-][j], f[i-][j + ( << (i-))]);
}
}
}
int query(int l, int r) {
int t = Log[r - l + ];
return min(f[t][l], f[t][r - ( << t) + ]);
}
} rmq;
struct Edge {
int to; Edge *next;
} pool[N * ], *pis = pool, *fir[N];
void AddEdge(int u, int v) {
pis->to = v, pis->next = fir[u], fir[u] = pis++;
}
int dfn[N], dfs_clock, *seq = rmq.f[], dep[N], ds[N], tot;
#define v p->to
void dfs(int u, int fa) {
dfn[u] = ++dfs_clock;
seq[dfs_clock] = dep[u];
for(Edge *p = fir[u]; p; p = p->next) {
if(v != fa) {
dep[v] = dep[u] + , dfs(v, u);
seq[++dfs_clock] = dep[u];
}
}
ds[tot++] = u;
}
#undef v
int dis(int u, int v) {
if(dfn[u] > dfn[v]) swap(u, v);
return dep[u] + dep[v] - (rmq.query(dfn[u], dfn[v]) << );
}
const int INF = << ;
struct Set {
multiset<int> s;
void insert(int x) {s.insert(x);}
void erase(int x) {
multiset<int>::iterator it = s.find(x);
if(it != s.end()) s.erase(it);
}
int size() const {return s.size();}
int top() {return s.empty() ? -INF : *--s.end();}
int query() {
if(s.size() < ) return -INF;
return *--s.end() + *----s.end();
}
} A, B[N], C[N];
void print(const Set &ss) {
const multiset<int> &s = ss.s;
for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
printf("%d ", *it);
}
puts("");
}
bool centre[N];
int fa[N], maxsz[N], sz[N], root;
#define v p->to
void dfs_size(int u, int fa) {
sz[u] = , maxsz[u] = ;
for(Edge *p = fir[u]; p; p = p->next) {
if(!centre[v] && v != fa) {
dfs_size(v, u);
sz[u] += sz[v];
maxsz[u] = max(maxsz[u], sz[v]);
}
}
}
void dfs_root(int u, int fa, int r) {
maxsz[u] = max(maxsz[u], sz[r] - sz[u]);
if(maxsz[u] < maxsz[root]) root = u;
for(Edge *p = fir[u]; p; p = p->next) {
if(!centre[v] && v != fa) dfs_root(v, u, r);
}
}
void divide(int u, int _fa) {
dfs_size(u, ), dfs_root(u, , root = u);
centre[u = root] = , fa[u] = _fa;
for(Edge *p = fir[u]; p; p = p->next) {
if(!centre[v]) divide(v, u);
}
}
#undef v
void add(int u, int v, int flag) {
if(u == v) {
A.erase(B[u].query());
if(flag) B[u].insert();
else B[u].erase();
A.insert(B[u].query());
}
int f = fa[u];
if(!f) return;
A.erase(B[f].query());
B[f].erase(C[u].top());
if(flag) C[u].insert(dis(f, v));
else C[u].erase(dis(f, v));
B[f].insert(C[u].top());
A.insert(B[f].query());
add(f, v, flag);
}
int col[N];
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
#endif
int n; scanf("%d", &n);
for(int i = ; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
dfs(, );
rmq.init((n << ) - );
divide(, );
int cnt_off = n;
for(int i = ; i < n; i++)
add(ds[i], ds[i], col[ds[i]] = );
int m, u; scanf("%d", &m);
char opt[];
while(m--) {
scanf("%s", opt);
if(opt[] == 'G') {
if(cnt_off == ) puts("-1");
else if(cnt_off == ) puts("");
else printf("%d\n", A.top());
} else {
scanf("%d", &u), add(u, u, col[u] ^= );
if(col[u]) cnt_off++; else cnt_off--;
}
}
return ;
}
点分治
括号序列：时间复杂度$O(n\log n)$,空间复杂度$O(n)$
#include<bits/stdc++.h> using namespace std; const int N = + ; int col[N];
const int bracket[] = {-, -}; struct Data {
/*
0 : 从区间左起的
[ x ] x的数量 c[] 是左右括号的数量，而d[]和s[]必须保证旁边至少有一个满足条件的点
*/
int c[]; // [ )...) ] 或 [ (...( ]
int d[]; // [ )...) ] - [ (...( ] 或反过来
int s[]; // [ )...) ] + [ (...( ] 或反过来
int ans; void set(int x) {
for(int i = ; i < ; i++) {
c[i] = x == bracket[i];
d[i] = s[i] = x > && col[x] ? : -( << );
// 只有在x是满足条件的点的时候才把d[]和s[]赋为0，否则为-INF
}
}
}; void maxit(int &x, int y) {
if(x < y) x = y;
} // 实际上需要讨论lhs.c[1] 和 rhs.c[0]的大小
// 但是不合法的一定不是最优的，所以可以对两种情况直接取max
Data operator + (const Data &lhs, const Data &rhs) {
static Data res; // update ans
res.ans = max(lhs.ans, rhs.ans);
maxit(res.ans, lhs.s[] + rhs.d[]);
maxit(res.ans, lhs.d[] + rhs.s[]); // update s[]
res.s[] = max(lhs.s[], rhs.s[] - lhs.c[] + lhs.c[]); // lhs.c[1] >= rhs.c[0]
res.s[] = max(res.s[], lhs.c[] + lhs.c[] + rhs.d[]); // lhs.c[1] <= rhs.c[0]
res.s[] = max(rhs.s[], lhs.s[] - rhs.c[] + rhs.c[]); // rhs.c[1] >= lhs.c[0]
res.s[] = max(res.s[], rhs.c[] + rhs.c[] + lhs.d[]); // rhs.c[1] <= rhs.c[0] // update d[]
res.d[] = max(lhs.d[], rhs.d[] + lhs.c[] - lhs.c[]);
res.d[] = max(rhs.d[], lhs.d[] + rhs.c[] - rhs.c[]); // update c[] to update next s[] and d[]
res.c[] = lhs.c[] + max(rhs.c[] - lhs.c[], );
res.c[] = rhs.c[] + max(lhs.c[] - rhs.c[], ); return res;
} struct Edge {int to; Edge *next;} pool[N * ], *pis = pool, *fir[N];
void AddEdge(int u, int v) {pis->to = v, pis->next = fir[u], fir[u] = pis++;} int dfs_seq[N * ], dfs_clock; void dfs(int u, int fa) {
col[u] = ;
dfs_seq[++dfs_clock] = bracket[];
dfs_seq[++dfs_clock] = u;
for(Edge *p = fir[u]; p; p = p->next) {
int v = p->to;
if(v != fa) dfs(v, u);
}
dfs_seq[++dfs_clock] = bracket[];
} int pos[N]; struct SegmentTree {
Data da[N * ];
void build(int s, int l, int r, int a[]) {
if(l == r) {
if(a[l] > ) pos[a[l]] = s;
return da[s].set(a[l]);
}
int mid = (l + r) >> ;
build(s << , l, mid, a), build(s << | , mid + , r, a);
da[s] = da[s << ] + da[s << | ];
} void modify(int x) {
int s = pos[x]; da[s].set(x);
while(s >>= ) da[s] = da[s << ] + da[s << | ];
}
} seg; int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
#endif int n; scanf("%d", &n);
for(int i = ; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
AddEdge(u, v), AddEdge(v, u);
}
dfs(, );
seg.build(, , n * , dfs_seq); int m; scanf("%d", &m);
char opt[]; int ans, x, cnt = n;
while(m--) {
scanf("%s", opt);
if(opt[] == 'G') {
if(cnt >= ) ans = seg.da[].ans;
else if(cnt == ) ans = ;
else ans = -;
printf("%d\n", ans);
} else {
scanf("%d", &x);
if(col[x] ^= ) cnt++; else cnt--;
seg.modify(x);
}
} return ;
}
线段树
链分治：时间复杂度$O(n\log^2n)$,空间复杂度$O(n)$ 比点分治快多啦
notice：合并两个线段树节点的时候如果使用=赋值可能丢失儿子信息。
#include<bits/stdc++.h>
using namespace std;
const int N = + , INF = << ;
struct Set {
multiset<int> s;
void erase(int x) {assert(s.find(x) != s.end()), s.erase(s.find(x));}
void insert(int x) {s.insert(x);}
int top() const {return s.empty() ? -INF : *--s.end();}
int query() const {
if(s.size() < ) return -INF;
return *--s.end() + *----s.end();
}
} heap[N], st;
void print(const Set &ss) {
const multiset<int> &s = ss.s;
for(multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
printf("%d ", *it);
}
puts("");
}
struct Edge {
int to, w;
Edge *next;
} pool_edges[N * ], *fir[N], *pe = pool_edges;
void AddEdge(int u, int v, int w) {
pe->to = v, pe->w = w, pe->next = fir[u], fir[u] = pe++;
}
int sz[N], top[N], dis[N], son[N], fa[N], dfs_clock, seq[N], dfn[N], end[N], col[N];
#define mid ((l + r) >> 1)
struct Node {
int L, R, ans;
Node *ch[];
void set(int u) {
ans = heap[u].query();
L = R = heap[u].top();
}
void modify(int l, int r, int p);
} pool_nodes[N * ], *pn = pool_nodes, *rt[N];
void print(Node *o, int l, int r) {
printf("[%d, %d] : L = %d, R = %d, ans = %d\n", l, r, o->L, o->R, o->ans);
if(l != r) print(o->ch[], l, mid), print(o->ch[], mid + , r);
}
void merge(Node &res, const Node &lhs, const Node &rhs, int l, int r) {
res.ans = max(lhs.ans, rhs.ans);
res.ans = max(res.ans, lhs.R + dis[seq[mid + ]] - dis[seq[mid]] + rhs.L);
res.L = max(lhs.L, dis[seq[mid + ]] - dis[seq[l]] + rhs.L);
res.R = max(rhs.R, dis[seq[r]] - dis[seq[mid]] + lhs.R);
}
void Node::modify(int l, int r, int p) {
if(l == r) return set(seq[p]);
if(p <= mid) ch[]->modify(l, mid, p);
else ch[]->modify(mid + , r, p);
merge(*this, *ch[], *ch[], l, r);
}
Node *build(int l, int r) {
Node *o = pn++;
if(l == r) o->set(seq[l]);
else {
o->ch[] = build(l, mid);
o->ch[] = build(mid + , r);
merge(*o, *o->ch[], *o->ch[], l, r);
}
return o;
}
#undef mid
#define v it->to
void dfs_size(int u) {
sz[u] = , col[u] = ;
for(Edge *it = fir[u]; it; it = it->next) {
if(v != fa[u]) {
dis[v] = dis[u] + it->w;
fa[v] = u;
dfs_size(v);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
}
void dfs_build(int u, int pre) {
seq[dfn[u] = ++dfs_clock] = u;
top[u] = pre;
end[pre] = max(end[pre], dfn[u]);
if(son[u]) dfs_build(son[u], pre);
for(Edge *it = fir[u]; it; it = it->next) {
if(v != fa[u] && v != son[u]) {
dfs_build(v, v);
heap[u].insert(rt[v]->L + dis[v] - dis[u]);
}
}
heap[u].insert();
if(top[u] == u) {
rt[u] = build(dfn[u], end[u]);
st.insert(rt[u]->ans);
}
}
#undef v
void modify(int u) {
static int anc[], tot;
tot = ;
for(int t = u; t; t = fa[top[t]]) anc[tot++] = t;
for(int i = tot-; i >= ; i--) {
st.erase(rt[top[anc[i]]]->ans);
if(i) heap[anc[i]].erase(rt[top[anc[i-]]]->L + dis[top[anc[i-]]] - dis[anc[i]]);
}
if(col[u]) heap[u].insert();
else heap[u].erase();
for(int i = ; i < tot; i++) {
int x = anc[i], t = top[x];
rt[t]->modify(dfn[t], end[t], dfn[x]);
st.insert(rt[t]->ans);
if(i+ < tot) heap[anc[i+]].insert(rt[t]->L + dis[t] - dis[anc[i+]]);
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
#endif
int n; scanf("%d", &n);
for(int i = ; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
AddEdge(u, v, ), AddEdge(v, u, );
}
dfs_size();
dfs_build(, );
int m; scanf("%d", &m);
char opt[]; int u, tot = n;
while(m--) {
scanf("%s", opt);
if(opt[] == 'G') {
int ans;
if(tot == ) ans = -;
else if(tot == ) ans = ;
else ans = st.top();
printf("%d\n", ans);
} else {
scanf("%d", &u);
if(!(col[u] ^= )) tot--; else tot++;
modify(u);
}
}
}
链分治