CF1208 Red Blue Tree

问题分析

这是蒟蒻第一道3500！不过话说luogu上两个题解的程序都是假的可还行（2019.11.1）……

为了方便叙述，下面我们约定：

\([c]\) 的值为 \(1\) 当且仅当 \(c\) 为真，反之为 \(0\) 。

\(0\) 表示白色， \(1\) 表示黑色。

\(son_u\) 表示 \(u\) 的所有儿子， \(ls_u\) 表示 \(u\) 的所有轻儿子， \(hs_u\) 表示 \(u\) 的重儿子。 \(m\) 表示 \(u\) 的子节点个数。

那么实际上对于一个特定的 \(k\) ，每个点的颜色 \(C\) 都可以被这样唯一确定：

\[C_u=\left[[C_{son_u}==1]-[C_{son_u}==0]\geqslant k\right]
\]

也可以写成这样子：

\[C_u=[m-2[C_{ls_u}==0]-2[C_{hs_u}==0]-k\geqslant 0]
\]

容易发现当 \(k\) 很小时，\(C\) 一定是 \(1\) ； \(k\) 很大时， \(C\) 一定是 \(0\) 。进一步分析发现，对于每一个点 \(u\) ，总有一个 \(k'\) 满足 \(C_u=0(k\geqslant k')\) 并且 \(C_u=1(k<k')\) 。而如果我们能维护每一个节点 \(u\) 的 \(k'\) （不妨记为 \(A_u\) ），就能简单地处理询问。

考虑 \(A_u\) 的性质：

\[\begin{aligned}
C_u&=[A_u>k]\\
A_u&=\min\{k|m-2[A_{son_u}\leqslant k]-k<0\}
\end{aligned}
\]

由于每次只会改变一个叶子的颜色，那么每个 \(A\) 的值最多变化2。那么可以对每一个 \(A_u\) 的儿子，可以建一个 Binary Search Tree 来解决。每一次改变暴力往前后扫 \(k\) 变了多少。时间复杂度 \(O(n^2)\) 。当然，如果是用脚造的数据，树高很矮的话，就可以过了

（貌似变烦而且变慢了？）

其实到这里应该已经发现是动态DP了。。。

实际上这个做法花了大量的时间转移每一个父亲，那么就可以考虑用动态DP的黑科技来转移：

\[A_u=\min\{k|m-2[A_{ls_u}\leqslant k]-k-2[A_{hs_u}\leqslant k]<0\}
\]

其中前面一部分仍然是在 Binary Search Tree 上解决，后面一部分我们需要去掉这个 \([]\) 运算。（感觉思维难点就在这里。。。）

令 \(T_0\) 表示当前这条链顶为白色，且链底的重儿子为白色所需最小的 \(k\) ； \(T_1\) 表示当前这条链顶为白色，且链底的重儿子为黑色所需要最小的 \(k\) 。

这样一来，重链上的转移就满足结合律了：

现在需要从链 \(B\) 转移到链 \(A\) ，其中 \(B\) 链顶的父亲是 \(A\) 链底。那么有

\[T_0 = \min\{\max\{A_0, B_0\}, A_1\}\\
T_1 = \min\{\max\{A_0, B_1\}, A_1\}
\]

而最后的答案就是 \([T_0>k]\) 。（考虑一下，一定有 \(T_0\leqslant T_1\) 。）

参考程序

代码很短的，很好写的，也就几个钟头就写完了。拖个模板，写的丑一点，不删调试信息也就十几k而已

#include <cstdio>

#include <algorithm>

const int INF = 1e7 + 10;

struct node {

    int Value, Priority, Size, Count;

    node *LeftChild, *RightChild;

    node() {

        Value = Priority = Size = Count = 0;

        LeftChild = RightChild = NULL;

        return;

    }

    node(int _Value) {

        Value = _Value;

        Priority = rand();

        Size = Count = 1;

        LeftChild = RightChild = NULL;

        return;

    }

    inline void Update();

};

struct noneRotateTreap {

    node *Root;

    noneRotateTreap() {

        Root = NULL;

        return;

    }

    inline std::pair<node *, node *> Split(node *Rt, int x);

    inline node *Merge(node *x, node *y);

    inline node *Find(int x);

    inline void Update(int x, int State);

    inline void Insert(int x);

    inline int Delete(int x);

    inline int Rank(int x);

    inline int Query(int x);

    inline int Precursor(int x);

    inline int Successor(int x);

    void Dfs(node *Rt);

    void Debug();

};

inline void node::Update() {

    Size = Count;

    if (LeftChild != NULL)

        Size += LeftChild->Size;

    if (RightChild != NULL)

        Size += RightChild->Size;

    return;

}

inline std::pair<node *, node *> noneRotateTreap::Split(node *Rt, int x) {

    if (Rt == NULL)

        return std::pair<node *, node *>(NULL, NULL);

    if (x < Rt->Value) {

        std::pair<node *, node *> Temp = Split(Rt->LeftChild, x);

        Rt->LeftChild = Temp.second;

        Rt->Update();

        return std::pair<node *, node *>(Temp.first, Rt);

    } else {

        std::pair<node *, node *> Temp = Split(Rt->RightChild, x);

        Rt->RightChild = Temp.first;

        Rt->Update();

        return std::pair<node *, node *>(Rt, Temp.second);

    }

}

inline node *noneRotateTreap::Merge(node *l, node *r) {

    if (l == NULL) return r;

    if (r == NULL) return l;

    if (l->Priority <= r->Priority) {

        l->RightChild = Merge(l->RightChild, r);

        l->Update();

        return l;

    } else {

        r->LeftChild = Merge(l, r->LeftChild);

        r->Update();

        return r;

    }

}

inline node *noneRotateTreap::Find(int x) {

    node *Rt = Root;

    while (Rt) {

        if (Rt->Value == x)

            return Rt;

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return NULL;

}

inline void noneRotateTreap::Update(int x, int State) {

    node *Rt = Root;

    while (Rt) {

        Rt->Size += State;

        if (Rt->Value == x) {

            Rt->Count += State;

            return;

        }

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return;

}

inline void noneRotateTreap::Insert(int x) {

    node *T = Find(x);

    if (T != NULL) {

        Update(x, 1);

        return;

    }

    std::pair<node *, node *> Temp = Split(Root, x);

    Temp.first = Merge(Temp.first, new node(x));

    Root = Merge(Temp.first, Temp.second);

    return;

}

inline int noneRotateTreap::Delete(int x) {

    node *T = Find(x);

    if (T == NULL) return 1;

    if (T->Count > 1) {

        Update(x, -1);

        return 0;

    }

    std::pair<node *, node *> Temp1 = Split(Root, x - 1);

    std::pair<node *, node *> Temp2 = Split(Temp1.second, x);

    delete Temp2.first;

    Root = Merge(Temp1.first, Temp2.second);

    return 0;

}

#define LCS (Rt->LeftChild ? Rt->LeftChild->Size : 0)

inline int noneRotateTreap::Rank(int x) {

    node *Rt = Root;

    int Ans = 0;

    while (Rt) {

        if (Rt->Value == x)

            return Ans + LCS + 1;

        if (x < Rt->Value)

            Rt = Rt->LeftChild;

        else

            Ans += LCS + Rt->Count, Rt = Rt->RightChild;

    }

    return Ans + 1;

}

inline int noneRotateTreap::Query(int x) {

    node *Rt = Root;

    while (Rt) {

        if (LCS < x && x <= LCS + Rt->Count)

            return Rt->Value;

        if (x <= LCS)

            Rt = Rt->LeftChild;

        else

            x -= LCS + Rt->Count, Rt = Rt->RightChild;

    }

    return 0;

}

#undef LCS

inline int noneRotateTreap::Precursor(int x) {

    int Ans = INF;

    node *Rt = Root;

    while (Rt) {

        if (Rt->Value < x)

            Ans = Rt->Value, Rt = Rt->RightChild;

        else

            Rt = Rt->LeftChild;

    }

    return Ans;

}

inline int noneRotateTreap::Successor(int x) {

    int Ans = -INF;

    node *Rt = Root;

    while (Rt) {

        if (Rt->Value > x)

            Ans = Rt->Value, Rt = Rt->LeftChild;

        else

            Rt = Rt->RightChild;

    }

    return Ans;

}

void noneRotateTreap::Debug() {

    Dfs(Root);

    printf("\n");

    return;

}

void noneRotateTreap::Dfs(node *T) {

    if (T == NULL) return;

    Dfs(T->LeftChild);

    for (int i = 1; i <= T->Count; ++i)

        printf("%d ", T->Value);

    Dfs(T->RightChild);

    return;

}

/*========== HEAD TEMPLATE : Binaty Search Tree -> NoneRotateTreap ==========*/

//#define DEBUG

//#define DEBUG_

//#define _DEBUG_

const int Maxn = 200010;

struct edge {

    int To, Next;

    edge() {}

    edge(int _To, int _Next) : To(_To), Next(_Next) {}

};

edge Edge[Maxn << 1];

int Start[Maxn], Used;

int Num, N, Q, Type, C[Maxn], k;

noneRotateTreap NoneRotateTreap[Maxn];

int CountSon[Maxn];

int Size[Maxn], Father[Maxn], Deep[Maxn], Son[Maxn], Top[Maxn], Dfn[Maxn], Ref[Maxn], Bottom[Maxn];

std::pair<int, int> IntervalTree[Maxn << 2];

int TreeSize;

int Record[Maxn];

inline void AddEdge(int x, int y);

inline void CutDfs1(int u, int Fa);

inline void CutDfs2(int u, int Fa);

inline std::pair<int, int> Calc(int x);

inline std::pair<int, int> Merge(std::pair<int, int> x, std::pair<int, int> y);

inline void Update(int Index, int Left, int Right);

inline void BuildIntervalTree(int Index, int Left, int Right);

inline std::pair<int, int> Query(int Index, int Left, int Right, int L, int R);

inline std::pair<int, int> Query(int x);

inline void Modify(int Pos, int &k, int Delta);

inline bool Judge(int Pos, int k, int Delta);

inline void Change(int x, int y);

inline void Modify(int Index, int Left, int Right, int Pos);

int main() {

    srand((unsigned long long)"非旋treap呀");

#ifdef DEBUG

    NoneRotateTreap[0].Insert(1);

    NoneRotateTreap[0].Insert(1);

    NoneRotateTreap[0].Insert(3);

    printf("%d %d ", NoneRotateTreap[0].Rank(2), NoneRotateTreap[0].Rank(1));

    NoneRotateTreap[0].Insert(-INF);

    printf("%d\n", NoneRotateTreap[0].Rank(1));

#endif

    scanf("%d%d", &N, &k);

    for (int i = 1; i < N; ++i) {

        int x, y;

        scanf("%d%d", &x, &y);

        AddEdge(x, y);

        AddEdge(y, x);

    }

    for (int i = 1; i <= N; ++i) scanf("%d", &C[i]);

    scanf("%d", &Q);

    CutDfs1(1, 0);

    Top[1] = 1;

    Dfn[1] = ++TreeSize;

    Ref[TreeSize] = 1;

    CutDfs2(1, 0);

    for (int i = 1; i <= N; ++i) Bottom[Top[i]] = std::max(Bottom[Top[i]], Dfn[i]);

#ifdef _DEBUG_

    printf("Father : ");

    for (int i = 1; i <= N; ++i) printf("%d ", Father[i]); printf("\n");

    printf(" Top   : ");

    for (int i = 1; i <= N; ++i) printf("%d ", Top[i]); printf("\n");

    printf(" Dfn   : ");

    for (int i = 1; i <= N; ++i) printf("%d ", Dfn[i]); printf("\n");

    printf("Bottom : ");

    for (int i = 1; i <= N; ++i) printf("%d ", Bottom[i]); printf("\n");

#endif

    BuildIntervalTree(1, 1, N);

#ifdef _DEBUG_

    printf("Check Ans :\n");

    for (int i = 1; i <= N; ++i) {

        std::pair<int, int> Ans = Query(i);

        printf("%d %d %d\n", i, Ans.first, Ans.second);

    }

#endif

    for (int i = 1; i <= N; ++i)

        if (Top[i] == i)

            Record[i] = Query(i).first;

    for (int i = 1; i <= Q; ++i) {

        int Opt, x, y;

        scanf("%d", &Opt);

        if (Opt == 1) {

            scanf("%d", &x);

            int Ans = Query(x).first > k ? 1 : 0;

            printf("%d\n", Ans);

        }

        if (Opt == 2) {

            scanf("%d%d", &x, &y);

            Change(x, y);

        }

        if (Opt == 3) scanf("%d", &k);

#ifdef _DEBUG_

        printf("After Opt %d (%d-th) :\n", Opt, i);

        for (int j = 1; j <= N; ++j) {

            std::pair<int, int> Ans = Query(j);

            printf("%d %d %d\n", j, Ans.first, Ans.second);

        }

#endif

    }

    return 0;

}

inline void AddEdge(int x, int y) {

    Edge[++Used] = edge(y, Start[x]);

    Start[x] = Used;

    return;

}

inline void CutDfs1(int u, int Fa) {

    Size[u] = 1;

    Father[u] = Fa;

    Deep[u] = Deep[Fa] + 1;

    for (int t = Start[u]; t; t = Edge[t].Next) {

        int v = Edge[t].To;

        if (v == Fa) continue;

        ++CountSon[u];

        CutDfs1(v, u);

        Size[u] += Size[v];

        if (Size[v] > Size[Son[u]])

            Son[u] = v;

    }

//    if (Size[Son[u]] == 1) Son[u] = 0;

    return;

}

inline void CutDfs2(int u, int Fa) {

    if (Son[u]) {

        Top[Son[u]] = Top[u];

        Dfn[Son[u]] = ++TreeSize;

        Ref[TreeSize] = Son[u];

        CutDfs2(Son[u], u);

    }

    for (int t = Start[u]; t; t = Edge[t].Next) {

        int v = Edge[t].To;

        if (v == Fa || v == Son[u]) continue;

        Top[v] = v;

        Dfn[v] = ++TreeSize;

        Ref[TreeSize] = v;

        CutDfs2(v, u);

    }

    return;

}

inline std::pair<int, int> Merge(std::pair<int, int> x, std::pair<int, int> y) {

    std::pair<int, int> Ans;

    Ans.first = std::min(std::max(y.first, x.first), x.second);

    Ans.second = std::min(std::max(y.second, x.first), x.second);

#ifdef _DEBUG_

    printf("      Merge %d %d, %d %d, Get %d %d\n", x.first, x.second, y.first, y.second, Ans.first, Ans.second);

#endif

    return Ans;

}

inline void Update(int Index, int Left, int Right) {

    if (Left == Right) return;

    IntervalTree[Index] = Merge(IntervalTree[Index << 1], IntervalTree[Index << 1 | 1]);

    return;

}

inline void BuildIntervalTree(int Index, int Left, int Right) {

    if (Left == Right) {

//        IntervalTree[Index] = Calc(Ref[Left]);

        Modify(1, 1, N, Left);

        //Notice : 这里需要用 Modify 同时来上传。因为下面要用到 Query(Ref[Left]) 。而 Modify 至多被调用 n 次，每次 log n ，所以不会影响复杂度。

#ifdef _DEBUG_

        printf("At Pos %d, Cal %d %d\n", Ref[Left], IntervalTree[Index].first, IntervalTree[Index].second);

#endif

        if (Top[Ref[Left]] == Ref[Left]) {

//            NoneRotateTreap[Father[Ref[Left]]].Insert(IntervalTree[Index].first);

            NoneRotateTreap[Father[Ref[Left]]].Insert(Query(Ref[Left]).first);

#ifdef _DEBUG_

            printf("*** %d\n", Ref[Left]);

            printf("!!!CAL %d %d\n", Query(Ref[Left]).first, Query(Ref[Left]).second);

            printf("Add %d To %d\n", Query(Ref[Left]).first, Father[Ref[Left]]);

            NoneRotateTreap[Father[Ref[Left]]].Debug();

#endif

        }

        return;

    }

    int Mid = (Left + Right) >> 1;

    BuildIntervalTree(Index << 1 | 1, Mid + 1, Right); //Right build first

    //Notice ： 处理数据的时候要先处理深度深的链。通过线段树上先算右边再算左边就可以做到

    BuildIntervalTree(Index << 1, Left, Mid);

    Update(Index, Left, Right);

    return;

}

inline std::pair<int, int> Query(int Index, int Left, int Right, int L, int R) {

#ifdef _DEBUG_

    printf(" Query %d %d %d %d %d\n", Index, Left, Right, L, R);

#endif

    if (L <= Left && Right <= R) return IntervalTree[Index];

    int Mid = (Left + Right) >> 1;

    if (R <= Mid) return Query(Index << 1, Left, Mid, L, R);

    if (L > Mid) return Query(Index << 1 | 1, Mid + 1, Right, L, R);

    return Merge(Query(Index << 1, Left, Mid, L, R), Query(Index << 1 | 1, Mid + 1, Right, L, R));

}

inline std::pair<int, int> Calc(int x) {

    if (C[x] == 0) return std::pair<int, int>(-INF, -INF);

    if (C[x] == 1) return std::pair<int, int>(INF, INF);

//    std::pair<int, int> Temp = Query(Son[x]);

    std::pair<int, int> Ans = std::pair<int, int>(0, 0);

#ifdef DEBUG_

    printf("Son white :\n");

#endif

    Modify(x, Ans.first, 2);

#ifdef DEBUG_

    printf("Son black :\n");

#endif

    Modify(x, Ans.second, 0);

#ifdef DEBUG_

    printf("Finally get : %d %d\n", Ans.first, Ans.second);

#endif

    return Ans;

}

inline std::pair<int, int> Query(int x) {

#ifdef _DEBUG_

    printf("   Query %d -> %d %d\n", x, Dfn[x], Bottom[Top[x]]);

#endif

    return Query(1, 1, N, Dfn[x], Bottom[Top[x]]);

}

inline void Modify(int Pos, int &k, int Delta) {

    while(!Judge(Pos, k, Delta)) ++k;

    while(Judge(Pos, k - 1, Delta)) --k;

    return;

}

inline bool Judge(int Pos, int k, int Delta) {

    int m = CountSon[Pos] - k - Delta;

    int c = NoneRotateTreap[Pos].Rank(k + 1) - 1;

#ifdef DEBUG_

    printf("    Judge %d %d %d -> %d %d, %d < 0 ?\n", Pos, k, Delta, m, c, m - 2 * c);

#endif

#ifdef DEBUG

    printf("        Treap[%d], QueryRank %d, Get %d\n", Pos, k + 1, NoneRotateTreap[Pos].Rank(k + 1));

#endif

    return m - 2 * c < 0;

}

inline void Change(int x, int y) {

    C[x] = y;

    while (x) {

#ifdef _DEBUG_

        printf("Change Pos %d\n", x);

#endif

        Modify(1, 1, N, Dfn[x]);

#ifdef _DEBUG_

        printf("   Elements in Treap : ");

        NoneRotateTreap[Father[Top[x]]].Debug();

#endif

        NoneRotateTreap[Father[Top[x]]].Delete(Record[Top[x]]);

#ifdef _DEBUG_

        printf("  NoneRotateTreap %d Delete %d\n", Father[Top[x]], Record[Top[x]]);

        printf("   Elements in Treap : ");

        NoneRotateTreap[Father[Top[x]]].Debug();

#endif

        NoneRotateTreap[Father[Top[x]]].Insert(Record[Top[x]] = Query(Top[x]).first);

#ifdef _DEBUG_

        printf("  NoneRotateTreap %d Insert %d\n", Father[Top[x]], Record[Top[x]]);

        printf("   Elements in Treap : ");

        NoneRotateTreap[Father[Top[x]]].Debug();

#endif

        x = Father[Top[x]];

    }

    return;

}

inline void Modify(int Index, int Left, int Right, int Pos) {

    if (Left == Right) {

        IntervalTree[Index] = Calc(Ref[Pos]);

#ifdef _DEBUG_

        printf("   Modify %d, Get %d %d\n", Ref[Pos], IntervalTree[Index].first, IntervalTree[Index].second);

#endif

        return;

    }

    int Mid = (Left + Right) >> 1;

    if (Pos <= Mid) Modify(Index << 1, Left, Mid, Pos);

    if (Pos > Mid) Modify(Index << 1 | 1, Mid + 1, Right, Pos);

    Update(Index, Left, Right);

    return;

}

巴特西

CF1208 Red Blue Tree

问题分析

参考程序

最新文章

热门文章