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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 17:09:55
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3,812 ms / 6,000 ms
• コード長: 8,541 bytes
• コンパイル時間: 2,685 ms
• コンパイル使用メモリ: 363,152 KB
• 実行使用メモリ: 60,416 KB
• 最終ジャッジ日時: 2026-09-04 22:05:01
• 合計ジャッジ時間: 25,740 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

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

using u32 = uint32_t;
using u64 = uint64_t;

constexpr u32 FULL = (1u << 30) - 1;

struct Node {
    u64 sum = 0;
    u32 cnt[30]{};

    // 子に対して保留されている作用:
    // v -> (v & lazyAnd) | lazyOr
    u32 lazyAnd = FULL;
    u32 lazyOr = 0;
};

struct Backup {
    int index;
    Node node;
};

int N, M;

vector<Node> seg;
vector<int> lastModified;
vector<Backup> history;

int currentVersion = 0;

void saveNode(int p) {
    if (lastModified[p] == currentVersion) {
        return;
    }

    lastModified[p] = currentVersion;
    history.push_back({p, seg[p]});
}

void build(
    int p,
    int left,
    int right,
    const vector<u32>& A
) {
    seg[p].lazyAnd = FULL;
    seg[p].lazyOr = 0;

    if (left == right) {
        seg[p].sum = A[left];

        for (int bit = 0; bit < 30; ++bit) {
            seg[p].cnt[bit] = (A[left] >> bit) & 1u;
        }
        return;
    }

    int middle = (left + right) / 2;

    build(p * 2, left, middle, A);
    build(p * 2 + 1, middle + 1, right, A);

    seg[p].sum = seg[p * 2].sum + seg[p * 2 + 1].sum;

    for (int bit = 0; bit < 30; ++bit) {
        seg[p].cnt[bit] =
            seg[p * 2].cnt[bit]
            + seg[p * 2 + 1].cnt[bit];
    }
}

void applyOr(int p, u32 mask, int length) {
    u32 bits = mask;

    while (bits != 0) {
        int bit = __builtin_ctz(bits);
        bits &= bits - 1;

        u32 oldCount = seg[p].cnt[bit];

        if (oldCount != static_cast<u32>(length)) {
            seg[p].sum +=
                static_cast<u64>(length - oldCount) << bit;

            seg[p].cnt[bit] = length;
        }
    }

    seg[p].lazyOr |= mask;
}

void applyAnd(int p, u32 mask) {
    u32 bits = FULL ^ mask;

    while (bits != 0) {
        int bit = __builtin_ctz(bits);
        bits &= bits - 1;

        u32 oldCount = seg[p].cnt[bit];

        if (oldCount != 0) {
            seg[p].sum -= static_cast<u64>(oldCount) << bit;
            seg[p].cnt[bit] = 0;
        }
    }

    seg[p].lazyAnd &= mask;
    seg[p].lazyOr &= mask;
}

// 現在の値に
// v -> (v & andMask) | orMask
// を作用させる。
void applyTransform(
    int p,
    u32 andMask,
    u32 orMask,
    int length
) {
    // 強制的に 0 になるビット
    u32 clearBits = (FULL ^ andMask) & (FULL ^ orMask);

    while (clearBits != 0) {
        int bit = __builtin_ctz(clearBits);
        clearBits &= clearBits - 1;

        u32 oldCount = seg[p].cnt[bit];

        if (oldCount != 0) {
            seg[p].sum -= static_cast<u64>(oldCount) << bit;
            seg[p].cnt[bit] = 0;
        }
    }

    // 強制的に 1 になるビット
    u32 setBits = orMask;

    while (setBits != 0) {
        int bit = __builtin_ctz(setBits);
        setBits &= setBits - 1;

        u32 oldCount = seg[p].cnt[bit];

        if (oldCount != static_cast<u32>(length)) {
            seg[p].sum +=
                static_cast<u64>(length - oldCount) << bit;

            seg[p].cnt[bit] = length;
        }
    }

    // 新しい作用を、既存の遅延作用の後に合成する。
    seg[p].lazyAnd &= andMask;
    seg[p].lazyOr =
        (seg[p].lazyOr & andMask) | orMask;
}

void push(int p, int left, int right) {
    if (
        seg[p].lazyAnd == FULL
        && seg[p].lazyOr == 0
    ) {
        return;
    }

    saveNode(p);

    int middle = (left + right) / 2;
    int leftChild = p * 2;
    int rightChild = p * 2 + 1;

    saveNode(leftChild);
    saveNode(rightChild);

    u32 andMask = seg[p].lazyAnd;
    u32 orMask = seg[p].lazyOr;

    applyTransform(
        leftChild,
        andMask,
        orMask,
        middle - left + 1
    );

    applyTransform(
        rightChild,
        andMask,
        orMask,
        right - middle
    );

    seg[p].lazyAnd = FULL;
    seg[p].lazyOr = 0;
}

void update(
    int p,
    int left,
    int right,
    int queryLeft,
    int queryRight,
    bool isOr,
    u32 mask,
    u32 affectedBits
) {
    saveNode(p);

    if (queryLeft <= left && right <= queryRight) {
        if (isOr) {
            applyOr(p, mask, right - left + 1);
        } else {
            applyAnd(p, mask);
        }
        return;
    }

    push(p, left, right);

    int middle = (left + right) / 2;

    if (queryLeft <= middle) {
        update(
            p * 2,
            left,
            middle,
            queryLeft,
            queryRight,
            isOr,
            mask,
            affectedBits
        );
    }

    if (middle < queryRight) {
        update(
            p * 2 + 1,
            middle + 1,
            right,
            queryLeft,
            queryRight,
            isOr,
            mask,
            affectedBits
        );
    }

    seg[p].sum =
        seg[p * 2].sum
        + seg[p * 2 + 1].sum;

    // OR なら mask のビット、
    // AND なら mask が 0 のビットしか変化しない。
    u32 bits = affectedBits;

    while (bits != 0) {
        int bit = __builtin_ctz(bits);
        bits &= bits - 1;

        seg[p].cnt[bit] =
            seg[p * 2].cnt[bit]
            + seg[p * 2 + 1].cnt[bit];
    }
}

u64 rangeSum(
    int p,
    int left,
    int right,
    int queryLeft,
    int queryRight
) {
    if (queryLeft <= left && right <= queryRight) {
        return seg[p].sum;
    }

    push(p, left, right);

    int middle = (left + right) / 2;
    u64 answer = 0;

    if (queryLeft <= middle) {
        answer += rangeSum(
            p * 2,
            left,
            middle,
            queryLeft,
            queryRight
        );
    }

    if (middle < queryRight) {
        answer += rangeSum(
            p * 2 + 1,
            middle + 1,
            right,
            queryLeft,
            queryRight
        );
    }

    return answer;
}

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

    cin >> N >> M;

    vector<u32> A(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    vector<u32> l(M + 1);
    vector<u32> r(M + 1);
    vector<u32> x(M + 1);
    vector<u32> L(M + 1);
    vector<u32> 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];
    }

    seg.resize(4 * N + 5);
    lastModified.assign(4 * N + 5, 0);

    build(1, 1, N, A);

    int Q;
    cin >> Q;

    history.reserve(200000);

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

        ++currentVersion;
        history.clear();

        u32 y = problemIndex;

        auto clampIndex = [&](u32 value) -> int {
            if (value == 0) {
                return 1;
            }

            if (value > static_cast<u32>(N)) {
                return N;
            }

            return static_cast<int>(value);
        };

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

            int u = clampIndex(l[z] ^ y);
            int v = clampIndex(r[z] ^ y);

            int updateLeft = min(u, v);
            int updateRight = max(u, v);

            int upperU = clampIndex(L[z] ^ y);
            int upperV = clampIndex(R[z] ^ y);

            int sumLeft = min(upperU, upperV);
            int sumRight = max(upperU, upperV);

            u32 mask = x[z] ^ y;

            if (z % 2 == 0) {
                update(
                    1,
                    1,
                    N,
                    updateLeft,
                    updateRight,
                    true,
                    mask,
                    mask
                );
            } else {
                update(
                    1,
                    1,
                    N,
                    updateLeft,
                    updateRight,
                    false,
                    mask,
                    FULL ^ mask
                );
            }

            y = static_cast<u32>(
                rangeSum(
                    1,
                    1,
                    N,
                    sumLeft,
                    sumRight
                ) & FULL
            );
        }

        cout << y << '\n';

        // 配列を小問題開始前の状態に戻す。
        for (const Backup& backup : history) {
            seg[backup.index] = backup.node;
        }
    }

    return 0;
}