题解 P4979 【矿洞：坍塌】

眠ㅤㅤㅤ · 2018-11-25 11:09:03 · 题解

对于珂朵莉树的每一个节点，我们考虑维护一个性质：该节点的与相邻的节点颜色不允许一样，也就是说连续一段颜色合并为一个节点。

拿样例来构造：AACBBABBBCCCBBB

此时对应的珂朵莉树：A_{[1,2]},C_{[3,3]},B_{[4,5]},A_{[6,6]},B_{[7,9]},C_{[10,12]},B_{[13,15]}

有了这个性质那么查询时候只需要二分找到 L,R 分别所在的位置的迭代器，那么这两个迭代器必须相等才能得到连续相同的一段，然后分类讨论一下就行了。

对于区间覆盖，也要分类讨论，需要考虑覆盖区间边界与覆盖区间边界所在的珂朵莉树节点中的区间边界位置来分类，保证我们维护的性质不变。

例如在以上的例子中，把 [ 6,6 ] 区间改为 B，修改之后的珂朵莉树应该要变成：

需要注意的细节其实挺多的，如果代码有什么问题私信我。(修改了错误的注释

完整代码：

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
    #include <bits/stdc++.h>
#endif

typedef long long LL;
using namespace std;

namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) < 'A' || o > 'Z'); return o;
    }
    inline double reod() {
        double o = read(), f = 1; char c;
        while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
        return o;
    }
}
using namespace IO;

const int SIZE = 2E5 + 7, Mod = (1E9 + 7, 998244353);

struct Chtholly {
    int L, R, w;
    Chtholly(int L, int R = 0, int w = 0) : L(L), R(R), w(w) {};
    bool operator < (const Chtholly& Tmp) const {
        return L < Tmp.L;
    }
}; set<Chtholly> Set; int N;

set<Chtholly>::iterator split(int pos) {                   
    auto Iter = prev(Set.upper_bound(Chtholly(pos)));
    if (Iter->L == pos) return Iter;
    int L = Iter->L, R = Iter->R, w = Iter->w;
    Set.erase(Iter); Set.insert(Chtholly(L, pos - 1, w));
    return Set.insert(Chtholly(pos, R, w)).first;
}

void Nota(int L, int R, int w) {
    auto LIter = prev(Set.upper_bound(Chtholly(L)));
    auto RIter = prev(Set.upper_bound(Chtholly(R)));

    /* 对右边颜色相同的点合并 */
    if (RIter != prev(Set.end()) && RIter->R == R && w == (RIter = next(RIter))->w) 
        R = RIter->R, RIter = next(RIter);
    else if (RIter->w != w)
        RIter = split(R + 1), LIter = prev(Set.upper_bound(Chtholly(L)));
    else 
        R = RIter->R, RIter = next(RIter);

    /* 对左边颜色相同的点合并 */
    if (LIter != Set.begin() && LIter->L == L && w == (prev(LIter))->w)
        LIter = prev(LIter), L = LIter->L;
    if (LIter->w != w)
        LIter = split(L);
    else
        L = LIter->L;

    /* 替换掉 */
    Set.erase(LIter, RIter);
    Set.insert(Chtholly(L, R, w));
}

bool Seniorious(int L, int R) {     
    auto now = prev(Set.upper_bound(Chtholly(L)));
    if (now != prev(Set.upper_bound(Chtholly(R)))) return false;
    if (!(L != 1 && R != N)) return true;

    /* 分类讨论即可 */
    if (L >  now->L && R <  now->R) return false;
    if (L == now->L && R != now->R) return prev(now)->w != now->w;
    if (R == now->R && L != now->L) return next(now)->w != now->w;
    return prev(now)->w != next(now)->w;
}

int main() {
    N = read(); 
    int L = 1, R = 1, pos = N; char w, prew = recd();
    while (pos-- > 1) {
        w = recd(); if (w == prew) { R++; continue; }
        Set.insert(Chtholly(L, R, prew)); L = ++R; prew = w;
    } Set.insert(Chtholly(L, R, prew));

    int que = read(); char o;
    while (que--) {
        o = recd(), L = read(), R = read();
        if (o == 'A') Nota(L, R, recd());
        else puts(Seniorious(L, R) ? "Yes" : "No");
    }
}