#1175002 (C++23(gcc16)) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 03:43:27
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: MLE
• 実行時間: -
• コード長: 9,058 bytes
• コンパイル時間: 2,751 ms
• コンパイル使用メモリ: 365,452 KB
• 実行使用メモリ: 1,305,320 KB
• 最終ジャッジ日時: 2026-09-04 22:02:43
• 合計ジャッジ時間: 8,547 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 8 MLE * 3 -- * 8

ソースコード

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

// Correct persistent lazy segment tree, but intentionally never reclaims
// path-copied nodes after an independent subproblem finishes.
// On the MLE-focused tests it creates about 15--17 million large nodes.

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

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

    struct Node {
        int left = -1;
        int right = -1;
        U64 sum = 0;
        array<U32, BITS> cnt{};
        U32 any = 0;
        U32 all = 0;
        U32 lazy_and = VALUE_MASK;
        U32 lazy_or = 0;
    };

    int n_;
    vector<Node> pool_;

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

    int make_node(const Node& node) {
        pool_.push_back(node);
        return static_cast<int>(pool_.size()) - 1;
    }

    int clone_node(int p) {
        return make_node(pool_[p]);
    }

    int build(int l, int r, const vector<U32>& a) {
        Node cur;
        if (l == r) {
            const U32 value = a[l];
            cur.sum = value;
            cur.any = value;
            cur.all = value;
            for (int b = 0; b < BITS; ++b) cur.cnt[b] = (value >> b) & 1U;
            return make_node(cur);
        }
        const int mid = (l + r) >> 1;
        cur.left = build(l, mid, a);
        cur.right = build(mid + 1, r, a);
        const Node& left = pool_[cur.left];
        const Node& right = pool_[cur.right];
        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];
        return make_node(cur);
    }

    void apply_or(int p, int len, U32 mask) {
        Node& cur = pool_[p];
        U32 changed = mask & ~cur.all;
        while (changed != 0) {
            const int b = __builtin_ctz(changed);
            changed &= changed - 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;
    }

    void apply_and(int p, U32 mask) {
        Node& cur = pool_[p];
        U32 changed = cur.any & ~mask;
        while (changed != 0) {
            const int b = __builtin_ctz(changed);
            changed &= changed - 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;
    }

    void push(int p, int l, int r) {
        if (l == r) return;
        const U32 lazy_and = pool_[p].lazy_and;
        const U32 lazy_or = pool_[p].lazy_or;
        if (lazy_and == VALUE_MASK && lazy_or == 0) return;

        const int mid = (l + r) >> 1;
        const int left_len = mid - l + 1;
        const int right_len = r - mid;

        const int new_left = clone_node(pool_[p].left);
        const int new_right = clone_node(pool_[p].right);
        pool_[p].left = new_left;
        pool_[p].right = new_right;

        apply_and(new_left, lazy_and);
        apply_or(new_left, left_len, lazy_or);
        apply_and(new_right, lazy_and);
        apply_or(new_right, right_len, lazy_or);

        pool_[p].lazy_and = VALUE_MASK;
        pool_[p].lazy_or = 0;
    }

    void pull(int p) {
        Node& cur = pool_[p];
        const Node& left = pool_[cur.left];
        const Node& right = pool_[cur.right];
        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];
    }

    int range_or_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql || (mask & ~pool_[p].all) == 0) return p;
        const int np = clone_node(p);
        if (ql <= l && r <= qr) {
            apply_or(np, r - l + 1, mask);
            return np;
        }
        push(np, l, r);
        const int mid = (l + r) >> 1;
        const int left = range_or_impl(pool_[np].left, l, mid, ql, qr, mask);
        const int right = range_or_impl(pool_[np].right, mid + 1, r, ql, qr, mask);
        pool_[np].left = left;
        pool_[np].right = right;
        pull(np);
        return np;
    }

    int range_and_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql || (pool_[p].any & ~mask) == 0) return p;
        const int np = clone_node(p);
        if (ql <= l && r <= qr) {
            apply_and(np, mask);
            return np;
        }
        push(np, l, r);
        const int mid = (l + r) >> 1;
        const int left = range_and_impl(pool_[np].left, l, mid, ql, qr, mask);
        const int right = range_and_impl(pool_[np].right, mid + 1, r, ql, qr, mask);
        pool_[np].left = left;
        pool_[np].right = right;
        pull(np);
        return np;
    }

    static pair<U32, U32> compose(U32 first_and, U32 first_or,
                                  U32 second_and, U32 second_or) {
        // second(first(value))
        return {first_and & second_and, (first_or & second_and) | second_or};
    }

    U64 transformed_sum(int p, int len, U32 after_and, U32 after_or) const {
        const Node& cur = pool_[p];
        U64 result = 0;
        for (int b = 0; b < BITS; ++b) {
            const U32 bit = U32(1) << b;
            U32 count;
            if (after_or & bit) count = static_cast<U32>(len);
            else if (after_and & bit) count = cur.cnt[b];
            else count = 0;
            result += contribution(count, b);
        }
        return result;
    }

    U64 range_sum_impl(int p, int l, int r, int ql, int qr,
                       U32 after_and, U32 after_or) const {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) {
            return transformed_sum(p, r - l + 1, after_and, after_or);
        }

        const Node& cur = pool_[p];
        const auto [child_and, child_or] =
            compose(cur.lazy_and, cur.lazy_or, after_and, after_or);
        const int mid = (l + r) >> 1;
        return range_sum_impl(cur.left, l, mid, ql, qr, child_and, child_or)
             + range_sum_impl(cur.right, mid + 1, r, ql, qr, child_and, child_or);
    }

public:
    explicit PersistentLazySegTree(const vector<U32>& a) : n_(static_cast<int>(a.size())) {
        // Enough for the initial tree, but nowhere near enough for all versions.
        // Growth of this vector is itself part of the eventual memory blow-up.
        pool_.reserve(300000);
        initial_root = build(0, n_ - 1, a);
    }

    int initial_root = -1;

    int range_or(int root, int l, int r, U32 mask) {
        return range_or_impl(root, 0, n_ - 1, l, r, mask);
    }

    int range_and(int root, int l, int r, U32 mask) {
        return range_and_impl(root, 0, n_ - 1, l, r, mask);
    }

    U64 range_sum(int root, int l, int r) const {
        return range_sum_impl(root, 0, n_ - 1, l, r, VALUE_MASK, 0);
    }
};

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);

    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];

    PersistentLazySegTree seg(A);

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

        int root = seg.initial_root;
        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 U = clamp_index(L[z] ^ y, N);
            const int V = clamp_index(R[z] ^ y, N);
            const int sum_l = min(U, V) - 1;
            const int sum_r = max(U, V) - 1;

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

            y = static_cast<uint32_t>(seg.range_sum(root, sum_l, sum_r)) & VALUE_MASK;
        }
        cout << y << '\n';

        // root is intentionally discarded without reclaiming any nodes.
    }
    return 0;
}