提出 #50402130

---

ソースコード 拡げる

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

using MappingParam = bool;

struct Node {
    using Value = bool;
    std::optional<Value> left;
    std::optional<Value> right;
    bool good {true};

    Node(void) = default;

    explicit Node(Value val) {
        left = val;
        right = val;
        good = true;
    }

    Node flip() const {
        Node result = *this;
        if (!result.is_unit()) {
            result.left = !left.value();
            result.right = !right.value();
        }

        return result;
    }

    Node merge(const Node& rhs) const {
        if (is_unit()) {
            return rhs;
        }

        if (rhs.is_unit()) {
            return *this;
        }

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

    bool is_unit() const {
        return !left.has_value();
    }
};

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

Node func_unit() {
    return Node();
}

Node func_map(MappingParam a, Node b) {
    if (a) {
        return b.flip();
    }
    return b;
}

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

MappingParam func_id() {
    return false;
}

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

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

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

        if (cmd == 1) {
            tree.apply(l, r, true);
        } 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;
}

提出情報

ジャッジ結果