【BZOJ1095】【ZJOI2007】Hide 捉迷藏（括号序列，线段树）

Description

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

Solution

算是括号序列模板题吧。

关于括号序列，推荐看看2008年曹钦翔的论文。

对于一棵树，我们有一个序列，对树进行dfs。刚访问这个节点时在序列中加入一个(和该节点编号，离开该节点时加入一个)。

我们发现树上两点距离等于序列中两点间未被匹配的括号个数！

考虑用线段树维护这个序列：

a代表左边有多少个)

b代表右边有多少个(

dis代表最大距离

还有论文里提到的这么几个量：

right_plus：max{a+b|S’(a,b)是S的一个后缀，且S’紧接在一个黑点之后}

right_minus：max{a-b|S’(a,b)是S的一个后缀，且S’紧接在一个黑点之后}

left_plus：max{a+b|S’(a,b)是S的一个前缀，且有一个黑点紧接在S之后}

left_minus：max{b-a|S’(a,b)是S的一个前缀，且有一个黑点紧接在S之后}

那么dis(S)=max{right_plus(S1)+left_minus(S2)，right_minus(S1)+left_plus(S2)，dis(S1)，dis(S2)}

关于这几个量的维护：

right_plus(S)=max{right_plus(S1)-c+d,right_minus(S1)+c+d,right_plus(S2)}

right_minus(S)=max{right_minus(S1)+c-d,right_minus(S2)}

left_plus(S)=max{left_plus(S2)-b+a,left_minus(S2)+b+a,left_plus(S1)}

left_minus(S)=max{left_minus(S2)+b-a,left_minus(S1)}

仔细思考为什么是这样的。

感觉比较容易看懂，但是自己不太容易推出来。

放代码。

Code

/**************************************
 * Au: Hany01
 * Prob: [BZOJ1095][ZJOI2007] 捉迷藏
 * Date: Apr 6th, 2018
 * Email: [email protected]
**************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = j; i < i##_end_; ++ i)
#define For(i, j ,k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define y1 wozenmezhemecaia 
#ifdef hany01
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b,  : ; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b,  : ; }

inline int read() {
    register char c_; register int _, __;
    for (_ = , __ = , c_ = getchar(); !isdigit(c_); c_ = getchar()) if (c_ == '-')  __ = -;
    for ( ; isdigit(c_); c_ = getchar()) _ = (_ << ) + (_ << ) + (c_ ^ );
    return _ * __;
}

const int maxn = , maxm = , maxv = ;

int v[maxm], e, nex[maxm], beg[maxn], lis[maxv], pos[maxn], tot;

inline void add(int uu, int vv) { v[++ e] = vv, nex[e] = beg[uu], beg[uu] = e; }

void dfs(int u, int fa)
{
    lis[++ tot] = -;
    lis[pos[u] = ++ tot] = u;
    for (register int i = beg[u]; i; i = nex[i])
        if (v[i] != fa) dfs(v[i], u);
    lis[++ tot] = -;
}

struct SegmentTree
{
    int a[maxv << ], b[maxv << ], lp[maxv << ], rp[maxv << ], lm[maxv << ], rm[maxv << ], dis[maxv << ];

#define lc (t << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)

    inline void maintain(int t)
    {
        a[t] = a[lc] + max(a[rc] - b[lc], ), b[t] = b[rc] + max(b[lc] - a[rc], ),
        rp[t] = max(rp[rc], max(rp[lc] - a[rc] + b[rc], rm[lc] + a[rc] + b[rc])),
        lp[t] = max(lp[lc], max(lp[rc] + a[lc] - b[lc], lm[rc] + a[lc] + b[lc])),
        rm[t] = max(rm[rc], rm[lc] + a[rc] - b[rc]),
        lm[t] = max(lm[lc], lm[rc] - a[lc] + b[lc]);
        dis[t] = max(max(max(dis[lc], dis[rc]), rp[lc] + lm[rc]), rm[lc] + lp[rc]);
    }

    void build(int t, int l, int r)
    {
        if (l == r) {
            if (lis[l] > ) lp[t] = rp[t] = lm[t] = rm[t] = ;
            else {
                lp[t] = rp[t] = lm[t] = rm[t] = -INF;
                if (lis[l] == -) a[t] = ; else b[t] = ;
            }
            dis[t] = -INF;
            return ;
        }
        build(lc, l, mid), build(rc, mid + , r);
        maintain(t);
    }

    void update(int t, int l, int r, int x)
    {
        if (l == r)
        {
            if (lp[t] > -INF) lp[t] = rp[t] = lm[t] = rm[t] = -INF;
            else lp[t] = rp[t] = lm[t] = rm[t] = ;
            dis[t] = -INF;
            return ;
        }
        if (x <= mid) update(lc, l, mid, x); else update(rc, mid + , r, x);
        maintain(t);
    }
}st;

int main()
{
#ifdef hany01
    File("bzoj1095");
#endif

    static int uu, vv, n;

    n = read();
    For(i, , n)
        uu = read(), vv = read(), add(uu, vv), add(vv, uu);
    dfs(, );
    st.build(, , tot);

    for (static int m = read(); m --; )
    {
        register char c; cin >> c;
        if (c == 'C') st.update(, , tot, pos[read()]);
        else printf("%d\n", st.dis[]);
    }

    return ;
}