【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 ;
}