蒟蒻 ODT 树神秘爆零求助
查看原帖
蒟蒻 ODT 树神秘爆零求助
405497
pe200012楼主2021/7/23 10:47
#include <cstdio>
#include <cstring>
#include <set>
#include <iostream>

using namespace std;
const int maxn = 100010;
const int maxm = 500010;
const int maxk = 21;
const int inf = std::numeric_limits<int>::max();

template<typename T>
inline void read(T &x) {
    T w = 1;
    char c = getchar();
    x = 0;
    while (c < '0' || c > '9') {
        if (c == '-')
            w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    x *= w;
}

template<typename T>
inline void write(T x) {
    static int sta[40];
    int cnt = -1;
    do {
        sta[++cnt] = x % 10;
        x /= 10;
    } while (x > 0);
    while (cnt >= 0)
        putchar(sta[cnt--] + '0');
}

template <typename Value>
struct Node {
    int l, r;
    mutable Value v;

    Node(const int _l, const int _r, const Value _v) : l(_l), r(_r), v(_v) {}

    inline bool operator<(const Node &o) const { return l < o.l; }
};

set<Node<int>> odt;
int n;

auto split(int x) {
    if (x > n) return odt.end();
    auto it = --odt.upper_bound({x, 0, 0});
    if (it->l == x) return it;
    int l = it->l, r = it->r;
    auto v = it->v;
    odt.erase(it);
    odt.emplace(l, x - 1, v);
    return odt.emplace(x, r, v).first;
}

inline void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    odt.erase(itl, itr);
    odt.emplace(l, r, v);
}

bool checkout(int l, int r) {
    auto itr = split(r + 1), itl = split(l);
    auto it = itl;
    auto current = itl->v;
    for (; itl != itr; ++itl) {
        if (itl->v != current) return false;
    }
    if (l == 1 || r == n) return true;
    -- it;
    return it -> v != itr -> v;
}

int main(void) {
    ios::sync_with_stdio(false);
    int k, l = 0, r = 0;
    cin >> n;
    char str[maxm];
    cin >> (str + 1);
    for (int i = 1; i <= strlen(str+1); ++i) {
        odt.emplace(i, i, str[i] - 'A');
    }
    cin >> k;
    while (k -- ) {
        char p, op;
        cin >> p >> l >> r;
        if (p == 'A') {
            cin >> op;
            assign(l, r, op);
        } else {
            if (checkout(l, r)) {
                cout << "Yes\n";
            } else cout << "No\n";
        }
    }

    return 0;
}

QAQ

2021/7/23 10:47
加载中...