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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 14:44:13
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 6,434 bytes
• コンパイル時間: 3,898 ms
• コンパイル使用メモリ: 111,348 KB
• 実行使用メモリ: 18,688 KB
• 最終ジャッジ日時: 2026-09-04 22:04:21
• 合計ジャッジ時間: 39,016 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	WA * 1
other	AC * 3 WA * 14 TLE * 2

ソースコード

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

using u32 = uint32_t;
using u64 = uint64_t;

constexpr int BITS = 30;
constexpr u32 MOD_MASK = (1U << 30) - 1;

struct Update {
    int l;
    int r;
    u32 x;
};

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

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

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

    vector<int> l(M), r(M), L(M), R(M);
    vector<u32> x(M);

    for (int &v : l) cin >> v;
    for (int &v : r) cin >> v;
    for (u32 &v : x) cin >> v;
    for (int &v : L) cin >> v;
    for (int &v : R) cin >> v;

    /*
     * prefXor[i] = A[1] xor ... xor A[i]
     * prefSum[i] = A[1] + ... + A[i]
     * prefOnes[b][i] = A[1..i] のうち b bit 目が 1 である要素数
     */
    vector<u32> prefXor(N + 1, 0);
    vector<u64> prefSum(N + 1, 0);
    array<vector<int>, BITS> prefOnes;

    for (int b = 0; b < BITS; ++b) {
        prefOnes[b].assign(N + 1, 0);
    }

    for (int i = 1; i <= N; ++i) {
        prefXor[i] = prefXor[i - 1] ^ A[i];
        prefSum[i] = prefSum[i - 1] + A[i];

        for (int b = 0; b < BITS; ++b) {
            prefOnes[b][i] =
                prefOnes[b][i - 1] + static_cast<int>((A[i] >> b) & 1U);
        }
    }

    auto clampPosition = [N](u32 value) -> int {
        if (value < 1U) return 1;
        if (value > static_cast<u32>(N)) return N;
        return static_cast<int>(value);
    };

    /*
     * 元の配列 A の区間 [left, right] の各要素に mask を XOR した場合の和。
     *
     * a xor mask
     * = a + mask - 2 * (a & mask)
     */
    auto transformedSum = [&](int left, int right, u32 mask) -> u64 {
        if (left > right) return 0;

        const u64 length = static_cast<u64>(right - left + 1);
        const u64 baseSum = prefSum[right] - prefSum[left - 1];

        u64 andSum = 0;
        u32 remaining = mask;

        while (remaining != 0) {
            const int bit = __builtin_ctz(remaining);
            const u64 ones =
                static_cast<u64>(
                    prefOnes[bit][right] - prefOnes[bit][left - 1]
                );

            andSum += ones << bit;
            remaining &= remaining - 1;
        }

        return baseSum
             + length * static_cast<u64>(mask)
             - 2ULL * andSum;
    };

    /*
     * 現在までの区間 XOR 更新を考慮した区間 XOR。
     *
     * 同じ値 x を区間内の各要素に XOR すると、その区間との共通部分の
     * 長さが奇数のときだけ、区間 XOR 全体に x が現れる。
     */
    auto rangeXor = [&](int left,
                        int right,
                        const vector<Update> &updates) -> u32 {
        u32 answer = prefXor[right] ^ prefXor[left - 1];

        for (const Update &update : updates) {
            const int commonLeft = max(left, update.l);
            const int commonRight = min(right, update.r);

            if (commonLeft <= commonRight &&
                ((commonRight - commonLeft + 1) & 1)) {
                answer ^= update.x;
            }
        }

        return answer;
    };

    /*
     * 現在までの区間 XOR 更新を考慮した区間和。
     *
     * 更新区間の開始位置と終了位置 + 1 をイベントとして扱う。
     * 隣り合うイベント間では適用される XOR 値が一定になる。
     */
    auto rangeSum = [&](int left,
                        int right,
                        const vector<Update> &updates) -> u32 {
        vector<pair<int, u32>> events;
        events.reserve(2 * updates.size());

        for (const Update &update : updates) {
            const int commonLeft = max(left, update.l);
            const int commonRight = min(right, update.r);

            if (commonLeft <= commonRight) {
                events.emplace_back(commonLeft, update.x);
                events.emplace_back(commonRight + 1, update.x);
            }
        }

        sort(events.begin(), events.end());

        u64 answer = 0;
        int currentPosition = left;
        u32 currentMask = 0;

        size_t eventIndex = 0;

        while (eventIndex < events.size()) {
            const int eventPosition = events[eventIndex].first;

            if (currentPosition < eventPosition) {
                answer += transformedSum(
                    currentPosition,
                    eventPosition - 1,
                    currentMask
                );
            }

            u32 change = 0;
            while (eventIndex < events.size() &&
                   events[eventIndex].first == eventPosition) {
                change ^= events[eventIndex].second;
                ++eventIndex;
            }

            currentMask ^= change;
            currentPosition = eventPosition;
        }

        if (currentPosition <= right) {
            answer += transformedSum(currentPosition, right, currentMask);
        }

        return static_cast<u32>(answer & MOD_MASK);
    };

    int Q;
    cin >> Q;

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

        u32 y = static_cast<u32>(problemIndex);

        vector<Update> updates;
        updates.reserve(q);

        for (int j = 1; j <= q; ++j) {
            /*
             * 問題文では
             * z = ((s + j) mod M) + 1
             *
             * 配列を 0-indexed で持っているため、
             * index = (s + j) mod M とする。
             */
            const int index = (s + j) % M;
            const int z = index + 1;

            int u = clampPosition(static_cast<u32>(l[index]) ^ y);
            int v = clampPosition(static_cast<u32>(r[index]) ^ y);
            int U = clampPosition(static_cast<u32>(L[index]) ^ y);
            int V = clampPosition(static_cast<u32>(R[index]) ^ y);

            const int left = min(u, v);
            const int right = max(u, v);
            const int sumLeft = min(U, V);
            const int sumRight = max(U, V);

            if (z % 2 == 0) {
                y = rangeXor(left, right, updates);
            } else {
                updates.push_back({left, right, x[index]});
            }

            y = rangeSum(sumLeft, sumRight, updates);
        }

        cout << y << '\n';
    }

    return 0;
}