BZOJ1095【ZJOI2007】Hide捉迷藏 <括号序列+线段树>

Posted on 2018-03-22 Symbols count in article: 1.9k Reading time ≈ 7 mins.

Problem

【ZJOI2007】Hide捉迷藏

$\mathrm{Time\;Limit:\;40\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

捉迷藏 $\mathrm{Jiajia}$ 和 $\mathrm{Wind}$ 是一对恩爱的夫妻，并且他们有很多孩子。某天， $\mathrm{Jiajia}$ 、 $\mathrm{Wind}$ 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $N$ 个屋子和 $N-1$ 条双向走廊组成，这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。
游戏是这样进行的，孩子们负责躲藏， $\mathrm{Jiajia}$ 负责找，而 $\mathrm{Wind}$ 负责操纵这 $N$ 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性， $\mathrm{Jiajia}$ 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。
我们将以如下形式定义每一种操作：

$\mathrm{C(hange)}\;i$ ：改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。
$\mathrm{G(ame)}$ ：开始一次游戏，查询最远的两个关灯房间的距离。

Input

第一行包含一个整数 $N$ ，表示房间的个数，房间将被编号为 $1,2,3\cdots N$ 的整数。接下来 $N-1$ 行每行两个整数 $a,b$ ，表示房间 $a$ 与房间 $b$ 之间有一条走廊相连。接下来一行包含一个整数 $Q$ ，表示操作次数。接着 $Q$ 行，每行一个操作，如上文所示。

Output

对于每一个操作 $\mathrm{G(ame)}$ ，输出一个非负整数，表示最远的两个关灯房间的距离。
若只有一个房间是关着灯的，输出 $0$ ；若所有房间的灯都开着，输出 $-1$ 。

Sample Input

Sample Output

Hint

对于 $100\%$ 的数据， $N\le10^5,\;M\le5\times10^5$ 。

标签：括号序列 线段树

Solution

不会写动态点分，受小岛姐的启发写了线段树，虽然有 $7$ 个标记，但推出公式还是比较好写的。

括号序列
对于一棵树，我们可以将其 $\mathrm{DFS}$ 序稍加优化，得到一个能记录每个点的子树结构的序列，即括号序列。
用左括号 $($ 表示进入某点的子树，用右括号 $)$ 表示走出某点的子树。

对于此树，括号序列为 $(A(B)(C(D)(E)))$ ，可以看出括号序列有一个有用的性质，即仍两点之间的序列可以表示从前面的点走到后面的点的走法。例如对于点 $B$ 和 $E$ ，其中间的序列为 $)(()($ ，如果去掉中间匹配的括号则变为 $)(($ ，将 $)$ 定义为向上走，将 $($ 定义为向下走，那么可以看出 $B$ 向上走两步，再向下走两步即可到 $E$ 。那么如果维护此题中的树的括号序列，那么只需要知道任意两个黑点间的括号序列消除配对后的长度的最大值后即可得到答案。

线段树维护
对于一个序列的区间，可以用二元组 $(a,b)$ 表示其消去配对后的序列，即有 $a$ 个右括号和 $b$ 个左括号。
对于区间 $S_1(a_1,b_1)$ 和 $S_2(a_2,b_2)$ ，它们合并起来的区间是 $S(a,b)$ ，那么

当 $b_1>a_2$ 时， $S_1$ 的左括号和 $S_2$ 的右括号消去后一定会剩下 $b_1-a_2$ 个左括号，因此 $a=a_1-b_1+a_2$ ， $b=b_2$
当 $b_1\le a_2$ 时， $S_1$ 的左括号和 $S_2$ 的右括号消去后一定会剩下 $a_2-b_1$ 个右括号，因此 $a=a_1$ ， $b=-a_2+b_1+b_2$

那么易得到几个推论：

$a+b=a_1+a_2+|b_1-a_2|$
$a-b=a_1+a_2-b_1-b_2$
$b-a=-a_1-a_2+b_1+b_2$

我们需要维护每个区间中两黑点间括号序列长度的最大值，那么我们还需要维护另外几个信息（有点像区间最大字段和）：

$lp=\max\lbrace a+b|S’(a,b)是S的一个前缀，且一个黑点接在S'之后\rbrace$
$lm=\max\lbrace b-a|S’(a,b)是S的一个前缀，且一个黑点接在S'之后\rbrace$
$rp=\max\lbrace a+b|S'(a,b)是S的一个后缀，且S'接在一个黑点后\rbrace$
$rm=\max\lbrace a-b|S'(a,b)是S的一个后缀，且S'接在一个黑点后\rbrace$

对于一个区间 $S$ ，其两个子区间 $S_1,S_2$ 的七个值分别为 $a_1,b_1,lp_1,lm_1,rp_1,rm_1,dis_1$ 和 $a_2,b_2,lp_2,lm_2,rp_2,rm_2,dis_2$ ，那么该区间的 $dis$ 一定是以下四个值的最大值：

$dis_1$
$dis_2$
$rp_1+lm_2$
$rm_1+lp_2$

而对于维护的 $4$ 个信息，观察发现可以这样计算：

$lp=\max\lbrace lp_1,\;a_1-b_1+lp_2,\;a_1+b_1+lm_2\rbrace$
$lm=\max\lbrace lm_1,\;-a_1+b_1+lm_2\rbrace$
$rp=\max\lbrace rp_2,\;-a_2+b_2+rp_1,\;a_2+b_2+rm_1\rbrace$
$rm=\max\lbrace rm_2,\;a_2-b_2+rm_1\rbrace$

这样以后我们就可以用线段树维护这七个标记了。
除了 $update$ 有点长以外，其他都和裸线段树一样。

以后找时间把动态点分学一学吧。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <int> G[MAX_N+5];
int n, cnt, col[MAX_N+5];    
int ind, seq[(MAX_N<<2)+5], dfn[MAX_N+5];
struct node {int a, b, lp, lm, rp, rm, dis;} tr[(MAX_N<<4)+5];
void addedge(int u, int v) {G[u].push_back(v), G[v].push_back(u);}
void DFS(int u, int f) {
    seq[++ind] = -1, seq[++ind] = u, dfn[u] = ind;
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if ((v = G[u][i]) ^ f) DFS(v, u);
    seq[++ind] = -2;
}
void init(int v, int p) {
    tr[v].a = tr[v].b = 0, tr[v].dis = -INF;
    if (seq[p] == -1) tr[v].b = 1;
    if (seq[p] == -2) tr[v].a = 1;
    if (seq[p] > 0 && col[seq[p]])
        tr[v].lp = tr[v].lm = tr[v].rp = tr[v].rm = 0;
    else tr[v].lp = tr[v].lm = tr[v].rp = tr[v].rm = -INF;
}
void update(int v, int s, int t) {
    int a = tr[v<<1].a, b = tr[v<<1].b;
    int c = tr[v<<1|1].a, d = tr[v<<1|1].b;
    tr[v].a = b < c ? a-b+c : a;
    tr[v].b = b < c ? d : b-c+d;
    tr[v].lp = tr[v<<1].lp, tr[v].rp = tr[v<<1|1].rp;
    tr[v].lm = tr[v<<1].lm, tr[v].rm = tr[v<<1|1].rm;
    tr[v].lp = max(tr[v].lp, tr[v<<1|1].lp+a-b);
    tr[v].lp = max(tr[v].lp, tr[v<<1|1].lm+a+b);
    tr[v].lm = max(tr[v].lm, tr[v<<1|1].lm-a+b);
    tr[v].rp = max(tr[v].rp, tr[v<<1].rp-c+d);
    tr[v].rp = max(tr[v].rp, tr[v<<1].rm+c+d);
    tr[v].rm = max(tr[v].rm, tr[v<<1].rm+c-d);
    tr[v].dis = max(tr[v<<1].dis, tr[v<<1|1].dis);
    tr[v].dis = max(tr[v].dis, tr[v<<1|1].lm+tr[v<<1].rp);
    tr[v].dis = max(tr[v].dis, tr[v<<1|1].lp+tr[v<<1].rm);
}
void build(int v, int s, int t) {
    if (s == t) {init(v, s);	return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t);
    update(v, s, t);
}
void modify(int v, int s, int t, int p) {
    if (s == t) {init(v, s);	return;}
    if (p <= mid) modify(v<<1, s, mid, p);
    else modify(v<<1|1, mid+1, t, p);
    update(v, s, t);
}
int main() {
    read(n), cnt = n;
    for (int i = 1; i <= n; i++) col[i] = 1;
    for (int i = 1, u, v; i < n; i++)
        read(u), read(v), addedge(u, v);
    int T;	read(T), DFS(1, 0), build(1, 1, ind);
    while (T--) {
        char opt[2];	scanf("%s", opt);
        if (opt[0] == 'C') {
            int x;	read(x);
            cnt += col[x] ? -1 : 1, col[x] ^= 1;
            modify(1, 1, ind, dfn[x]);
        }
        if (opt[0] == 'G') {
            if (!cnt) puts("-1");
            else if (cnt == 1) puts("0");
            else printf("%d\n", tr[1].dis);
        }
    }
    return 0;
}