#1174998 (C++17) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 03:20:41
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3,821 ms / 6,000 ms
• コード長: 8,827 bytes
• コンパイル時間: 2,054 ms
• コンパイル使用メモリ: 237,468 KB
• 実行使用メモリ: 43,648 KB
• 最終ジャッジ日時: 2026-09-04 22:02:17
• 合計ジャッジ時間: 29,433 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 19

ソースコード

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

class RollbackLazySegTree {
    using U32 = uint32_t;
    using U64 = uint64_t;

    static constexpr int BITS = 30;
    static constexpr U32 VALUE_MASK = (U32(1) << BITS) - 1;

    struct Node {
        U64 sum = 0;
        array<U32, BITS> cnt{};
        U32 any = 0;                 // bitwise OR of all values in the segment
        U32 all = 0;                 // bitwise AND of all values in the segment
        U32 lazy_and = VALUE_MASK;   // pending transform: (value & lazy_and) | lazy_or
        U32 lazy_or = 0;
    };

    int n_ = 0;
    int size_ = 1;
    vector<Node> tree_;

    // A node is copied at most once in each subproblem.
    vector<int> saved_epoch_;
    int epoch_ = 0;
    vector<pair<int, Node>> history_;

    static U64 contribution(U32 count, int bit) {
        return static_cast<U64>(count) << bit;
    }

    void save(int p) {
        if (saved_epoch_[p] == epoch_) return;
        saved_epoch_[p] = epoch_;
        history_.emplace_back(p, tree_[p]);
    }

    void build(int p, int l, int r, const vector<U32>& a) {
        tree_[p] = Node{};
        if (l == r) {
            const U32 value = (l < n_ ? a[l] : 0);
            tree_[p].sum = value;
            tree_[p].any = value;
            tree_[p].all = value;
            for (int b = 0; b < BITS; ++b) {
                tree_[p].cnt[b] = (value >> b) & 1U;
            }
            return;
        }

        const int mid = (l + r) >> 1;
        build(p << 1, l, mid, a);
        build(p << 1 | 1, mid + 1, r, a);

        Node& cur = tree_[p];
        const Node& left = tree_[p << 1];
        const Node& right = tree_[p << 1 | 1];
        cur.sum = left.sum + right.sum;
        cur.any = left.any | right.any;
        cur.all = left.all & right.all;
        for (int b = 0; b < BITS; ++b) {
            cur.cnt[b] = left.cnt[b] + right.cnt[b];
        }
    }

    U32 apply_or(int p, int len, U32 mask) {
        Node& cur = tree_[p];
        const U32 changed = mask & ~cur.all;
        if (changed == 0) return 0;

        save(p);
        U32 bits = changed;
        while (bits != 0) {
            const int b = __builtin_ctz(bits);
            bits &= bits - 1;
            const U32 old_count = cur.cnt[b];
            const U32 new_count = static_cast<U32>(len);
            cur.sum += contribution(new_count - old_count, b);
            cur.cnt[b] = new_count;
        }

        cur.any |= mask;
        cur.all |= mask;
        cur.lazy_or |= mask;
        return changed;
    }

    U32 apply_and(int p, U32 mask) {
        Node& cur = tree_[p];
        const U32 changed = cur.any & ~mask;
        if (changed == 0) return 0;

        save(p);
        U32 bits = changed;
        while (bits != 0) {
            const int b = __builtin_ctz(bits);
            bits &= bits - 1;
            const U32 old_count = cur.cnt[b];
            cur.sum -= contribution(old_count, b);
            cur.cnt[b] = 0;
        }

        cur.any &= mask;
        cur.all &= mask;
        cur.lazy_and &= mask;
        cur.lazy_or &= mask;
        return changed;
    }

    void push(int p, int l, int r) {
        Node& cur = tree_[p];
        if (l == r || (cur.lazy_and == VALUE_MASK && cur.lazy_or == 0)) return;

        const int mid = (l + r) >> 1;
        const int left_len = mid - l + 1;
        const int right_len = r - mid;
        const U32 lazy_and = cur.lazy_and;
        const U32 lazy_or = cur.lazy_or;

        apply_and(p << 1, lazy_and);
        apply_or(p << 1, left_len, lazy_or);
        apply_and(p << 1 | 1, lazy_and);
        apply_or(p << 1 | 1, right_len, lazy_or);

        save(p);
        cur.lazy_and = VALUE_MASK;
        cur.lazy_or = 0;
    }

    void pull_changed(int p, int len, U32 changed) {
        if (changed == 0) return;
        save(p);

        Node& cur = tree_[p];
        const Node& left = tree_[p << 1];
        const Node& right = tree_[p << 1 | 1];

        U32 bits = changed;
        while (bits != 0) {
            const int b = __builtin_ctz(bits);
            bits &= bits - 1;
            const U32 bit_mask = U32(1) << b;

            const U32 old_count = cur.cnt[b];
            const U32 new_count = left.cnt[b] + right.cnt[b];
            if (new_count > old_count) {
                cur.sum += contribution(new_count - old_count, b);
            } else {
                cur.sum -= contribution(old_count - new_count, b);
            }
            cur.cnt[b] = new_count;

            if (new_count == 0) cur.any &= ~bit_mask;
            else cur.any |= bit_mask;

            if (new_count == static_cast<U32>(len)) cur.all |= bit_mask;
            else cur.all &= ~bit_mask;
        }
    }

    U32 range_or_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql) return 0;
        if ((mask & ~tree_[p].all) == 0) return 0;
        if (ql <= l && r <= qr) return apply_or(p, r - l + 1, mask);

        push(p, l, r);
        const int mid = (l + r) >> 1;
        const U32 changed_left = range_or_impl(p << 1, l, mid, ql, qr, mask);
        const U32 changed_right = range_or_impl(p << 1 | 1, mid + 1, r, ql, qr, mask);
        const U32 changed = changed_left | changed_right;
        pull_changed(p, r - l + 1, changed);
        return changed;
    }

    U32 range_and_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql) return 0;
        if ((tree_[p].any & ~mask) == 0) return 0;
        if (ql <= l && r <= qr) return apply_and(p, mask);

        push(p, l, r);
        const int mid = (l + r) >> 1;
        const U32 changed_left = range_and_impl(p << 1, l, mid, ql, qr, mask);
        const U32 changed_right = range_and_impl(p << 1 | 1, mid + 1, r, ql, qr, mask);
        const U32 changed = changed_left | changed_right;
        pull_changed(p, r - l + 1, changed);
        return changed;
    }

    U64 range_sum_impl(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree_[p].sum;

        push(p, l, r);
        const int mid = (l + r) >> 1;
        return range_sum_impl(p << 1, l, mid, ql, qr)
             + range_sum_impl(p << 1 | 1, mid + 1, r, ql, qr);
    }

public:
    explicit RollbackLazySegTree(const vector<U32>& a) {
        n_ = static_cast<int>(a.size());
        while (size_ < n_) size_ <<= 1;
        tree_.resize(size_ << 1);
        saved_epoch_.assign(size_ << 1, 0);
        history_.reserve(4096);
        build(1, 0, size_ - 1, a);
    }

    void begin_subproblem() {
        ++epoch_;
        history_.clear();
    }

    void rollback() {
        for (auto it = history_.rbegin(); it != history_.rend(); ++it) {
            tree_[it->first] = it->second;
        }
        history_.clear();
    }

    void range_or(int l, int r, U32 mask) {
        range_or_impl(1, 0, size_ - 1, l, r, mask);
    }

    void range_and(int l, int r, U32 mask) {
        range_and_impl(1, 0, size_ - 1, l, r, mask);
    }

    U64 range_sum(int l, int r) {
        return range_sum_impl(1, 0, size_ - 1, l, r);
    }
};

static int clamp_index(uint32_t value, int n) {
    if (value < 1) return 1;
    if (value > static_cast<uint32_t>(n)) return n;
    return static_cast<int>(value);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    static constexpr uint32_t VALUE_MASK = (uint32_t(1) << 30) - 1;

    int N, M;
    cin >> N >> M;

    vector<uint32_t> A(N);
    for (auto& value : A) cin >> value;

    vector<uint32_t> l(M + 1), r(M + 1), x(M + 1), L(M + 1), R(M + 1);
    for (int i = 1; i <= M; ++i) cin >> l[i];
    for (int i = 1; i <= M; ++i) cin >> r[i];
    for (int i = 1; i <= M; ++i) cin >> x[i];
    for (int i = 1; i <= M; ++i) cin >> L[i];
    for (int i = 1; i <= M; ++i) cin >> R[i];

    RollbackLazySegTree seg(A);

    int Q;
    cin >> Q;
    for (int i = 1; i <= Q; ++i) {
        int s, q;
        cin >> s >> q;

        seg.begin_subproblem();
        uint32_t y = static_cast<uint32_t>(i);

        for (int j = 1; j <= q; ++j) {
            const int z = ((s + j) % M) + 1;

            const int u = clamp_index(l[z] ^ y, N);
            const int v = clamp_index(r[z] ^ y, N);
            const int ql = min(u, v) - 1;
            const int qr = max(u, v) - 1;

            const int big_u = clamp_index(L[z] ^ y, N);
            const int big_v = clamp_index(R[z] ^ y, N);
            const int sum_l = min(big_u, big_v) - 1;
            const int sum_r = max(big_u, big_v) - 1;

            const uint32_t mask = x[z] ^ y;
            if ((z & 1) == 0) seg.range_or(ql, qr, mask);
            else seg.range_and(ql, qr, mask);

            y = static_cast<uint32_t>(seg.range_sum(sum_l, sum_r)) & VALUE_MASK;
        }

        cout << y << '\n';
        seg.rollback();
    }

    return 0;
}