题解 | 区间取反与区间数一

#include <bits/stdc++.h>
using namespace std;

template<typename S, S(*merge)(S, S), S(*element)(), typename F, S(*mapping)(F, S), F(*compose)(F, F), F(*id)()>
class LazySegTree {
    vector<S> tree;
    vector<F> lazy;
    size_t n;

    void push_up(const int node) {
        tree[node] = merge(tree[node << 1], tree[node << 1 | 1]);
    }

    void push_down(const int node, const int start, const int end) {
        if (lazy[node] == id()) return;
        const int left_child = node << 1;
        const int right_child = node << 1 | 1;
        if (start == end) {
            lazy[node] = id();
            return;
        }
        tree[left_child] = mapping(lazy[node], tree[left_child]);
        lazy[left_child] = compose(lazy[node], lazy[left_child]);

        tree[right_child] = mapping(lazy[node], tree[right_child]);
        lazy[right_child] = compose(lazy[node], lazy[right_child]);

        lazy[node] = id();
    }

    void build(const int node, const int start, const int end, vector<S> const &data) {
        if (start == end) {
            tree[node] = data[start];
            return;
        }
        const int middle = (start + end) >> 1;
        const int left_child = node << 1;
        const int right_child = node << 1 | 1;
        build(left_child, start, middle, data);
        build(right_child, middle + 1, end, data);
        push_up(node);
    }

    void update_range(const int node, const int start, const int end, const int left, const int right, const F delta) {
        if (left <= start && end <= right) {
            lazy[node] = compose(delta, lazy[node]);
            tree[node] = mapping(delta, tree[node]);
            return;
        }
        push_down(node, start, end);
        const int middle = (start + end) >> 1;
        const int left_child = node << 1;
        const int right_child = node << 1 | 1;
        if (left <= middle)
            update_range(left_child, start, middle, left, right, delta);
        if (middle < right)
            update_range(right_child, middle + 1, end, left, right, delta);
        push_up(node);
    }

    [[nodiscard]] S query_range(const int node, const int start, const int end, const int left, const int right) {
        if (left <= start && end <= right) {
            return tree[node];
        }
        push_down(node, start, end);
        const int middle = (start + end) >> 1;
        const int left_child = node << 1;
        const int right_child = node << 1 | 1;
        S result = element();
        if (right <= middle) return query_range(left_child, start, middle, left, right);
        if (left > middle) return query_range(right_child, middle + 1, end, left, right);
        S left_result = query_range(left_child, start, middle, left, right);
        S right_result = query_range(right_child, middle + 1, end, left, right);
        return merge(left_result, right_result);
    }

public:
    explicit LazySegTree(vector<S> const &data) : n(data.size()) {
        assert(n!=0);
        tree.assign(data.size() * 4, element());
        lazy.assign(data.size() * 4, id());
        const int end = n - 1;
        build(1, 0, end, data);
    }

    void update_range(const int left, const int right, F delta) {
        update_range(1, 0, n - 1, left, right, delta);
    }

    S query_range(const int left, const int right) {
        assert(0 <= left && left <= right && right < n);
        return query_range(1, 0, n - 1, left, right);
    }

    [[nodiscard]] size_t size() const {
        return n;
    }
};

struct Node {
    int num, len;

    Node() : num(0), len(0) {
    }

    Node(const int num, const int len) : num(num), len(len) {
    }

    explicit Node(const int num) : num(num), len(1) {
    }

    Node operator+(Node const &rhs) const {
        Node result{};
        result.num = num + rhs.num;
        result.len = len + rhs.len;
        return result;
    }
};

Node merge(const Node left, const Node right) {
    return left + right;
}

Node element() {
    return {};
}

Node mapping(const int f, const Node s) {
    Node result{};
    result.len = s.len;
    result.num = f % 2 == 0 ? s.num : s.len - s.num;
    return result;
}

int compose(const int f1, const int f2) {
    return (f1 + f2) % 2;
}

int id() {
    return 0;
}


void solve() {
    int n, q;
    cin >> n >> q;
    vector<Node> data(n);
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) data[i] = Node(s[i] - '0');
    LazySegTree<Node, merge, element, int, mapping, compose, id> tree(data);
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1)
            tree.update_range(l - 1, r - 1, 1);
        else
            cout << tree.query_range(l - 1, r - 1).num << '\n';
    }
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

肝了一下午的线段树模板，参考了Atcoder库的实现