Submission #50389847

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/lazysegtree>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

struct Node {
    Num left {0};
    Num right {0};
    Num width {0};
    bool good {true};

    Node(void) = default;

    explicit Node(Num digit) {
        left = digit;
        right = digit;
        width = 1;
        good = true;
    }

    Node flip() const {
        Node result = *this;
        result.left = 1 - left;
        result.right = 1 - right;
        return result;
    }

    Node merge(const Node& rhs) const {
        if (width == 0) {
            return rhs;
        }

        if (rhs.width == 0) {
            return *this;
        }

        Node result;
        result.left = left;
        result.right = rhs.right;
        result.width = width + rhs.width;
        result.good = good && rhs.good && (right != rhs.left);
        return result;
    }
};

Node func_operate(Node a, Node b) {
    return a.merge(b);
}

Node func_unit() {
    return Node();
}

Node func_map(Num a, Node b) {
    if (a != 0) {
        return b.flip();
    } else {
        return b;
    }
}

Num func_compose(Num a, Num b) {
    return a ^ b;
}

Num func_id() {
    return 0;
}

void solve(std::istream& is, std::ostream& os) {
    Num n, q;
    std::string s;
    is >> n >> q >> s;

    atcoder::lazy_segtree<Node, func_operate, func_unit, Num, func_map, func_compose, func_id> tree(n);
    for(Num i{0}; i<n; ++i) {
        Num d = s.at(i) - '0';
        Node nd(d);
        tree.set(i, nd);
    }

    while(q-- > 0) {
        Num cmd, l, r;
        is >> cmd >> l >> r;
        --l;

        if (cmd == 1) {
            tree.apply(l, r, 1);
        } else {
            const auto node = tree.prod(l, r);
            if (node.good) {
                os << "Yes\n";
            } else {
                os << "No\n";
            }
        }
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result