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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-05 14:45:42
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 7,201 bytes
• コンパイル時間: 1,322 ms
• コンパイル使用メモリ: 220,840 KB
• 実行使用メモリ: 34,432 KB
• 最終ジャッジ日時: 2026-09-04 22:04:22
• 合計ジャッジ時間: 13,079 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 13 TLE * 1 -- * 5

ソースコード

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

using u32 = uint32_t;
using u64 = uint64_t;

static constexpr int B = 4;
static constexpr int CHUNKS = 8;
static constexpr int CHUNK_VALUES = 1 << B;
static constexpr int NONZERO_MASKS = CHUNK_VALUES - 1;
static constexpr u32 FULL = (1u << 30) - 1;

class MaskedPrefixSum {
private:
    int n;
    size_t width;
    vector<u32> pref;

    size_t offset(int chunk, int mask) const {
        // mask は 1 以上 15 以下
        return (
            static_cast<size_t>(chunk) * NONZERO_MASKS
            + (mask - 1)
        ) * width;
    }

public:
    explicit MaskedPrefixSum(const vector<u32>& a)
        : n(static_cast<int>(a.size()) - 1),
          width(static_cast<size_t>(n) + 1),
          pref(
              static_cast<size_t>(CHUNKS)
              * NONZERO_MASKS
              * width,
              0
          ) {

        for (int chunk = 0; chunk < CHUNKS; ++chunk) {
            const int shift = B * chunk;

            for (int mask = 1; mask < CHUNK_VALUES; ++mask) {
                const size_t base = offset(chunk, mask);

                for (int i = 1; i <= n; ++i) {
                    const u32 part =
                        (a[i] >> shift) & (CHUNK_VALUES - 1);

                    pref[base + i] =
                        pref[base + i - 1]
                        + (part & static_cast<u32>(mask));
                }
            }
        }
    }

    u64 rangeMaskedSum(int l, int r, u32 mask) const {
        u64 result = 0;

        for (int chunk = 0; chunk < CHUNKS; ++chunk) {
            const int shift = B * chunk;
            const int chunkMask =
                static_cast<int>(
                    (mask >> shift) & (CHUNK_VALUES - 1)
                );

            if (chunkMask == 0) {
                continue;
            }

            const size_t base = offset(chunk, chunkMask);

            const u32 partSum =
                pref[base + r] - pref[base + l - 1];

            result += static_cast<u64>(partSum) << shift;
        }

        return result;
    }
};

struct Segment {
    int l;
    int r;
    u32 keepMask;
    u32 oneMask;
};

static inline void appendMerged(
    vector<Segment>& segments,
    const Segment& segment
) {
    if (segment.l > segment.r) {
        return;
    }

    if (
        !segments.empty()
        && segments.back().r + 1 == segment.l
        && segments.back().keepMask == segment.keepMask
        && segments.back().oneMask == segment.oneMask
    ) {
        segments.back().r = segment.r;
    } else {
        segments.push_back(segment);
    }
}

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& value : l) {
        cin >> value;
    }
    for (int& value : r) {
        cin >> value;
    }
    for (u32& value : x) {
        cin >> value;
    }
    for (int& value : L) {
        cin >> value;
    }
    for (int& value : R) {
        cin >> value;
    }

    MaskedPrefixSum prefix(A);

    int Q;
    cin >> Q;

    vector<Segment> segments;
    vector<Segment> nextSegments;

    segments.reserve(32);
    nextSegments.reserve(32);

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

        u32 y = static_cast<u32>(problemIndex);

        segments.clear();
        nextSegments.clear();

        segments.push_back({
            1,
            N,
            FULL,
            0
        });

        for (int j = 1; j <= q; ++j) {
            // 問題文の z は 1-indexed
            const int z = ((s + j) % M) + 1;
            const int index = z - 1;

            auto transformedPosition = [&](int p) -> int {
                return clamp(
                    p ^ static_cast<int>(y),
                    1,
                    N
                );
            };

            const int u = transformedPosition(l[index]);
            const int v = transformedPosition(r[index]);
            const int U = transformedPosition(L[index]);
            const int V = transformedPosition(R[index]);

            const int updateL = min(u, v);
            const int updateR = max(u, v);

            const int sumL = min(U, V);
            const int sumR = max(U, V);

            const u32 operationMask = x[index] ^ y;

            nextSegments.clear();

            for (const Segment& segment : segments) {
                if (
                    segment.r < updateL
                    || updateR < segment.l
                ) {
                    appendMerged(nextSegments, segment);
                    continue;
                }

                // 更新区間より左側
                if (segment.l < updateL) {
                    appendMerged(
                        nextSegments,
                        {
                            segment.l,
                            updateL - 1,
                            segment.keepMask,
                            segment.oneMask
                        }
                    );
                }

                // 更新区間との共通部分
                Segment middle{
                    max(segment.l, updateL),
                    min(segment.r, updateR),
                    segment.keepMask,
                    segment.oneMask
                };

                if (z % 2 == 0) {
                    // value := value | operationMask
                    middle.keepMask &=
                        (FULL ^ operationMask);
                    middle.oneMask |= operationMask;
                } else {
                    // value := value & operationMask
                    middle.keepMask &= operationMask;
                    middle.oneMask &= operationMask;
                }

                appendMerged(nextSegments, middle);

                // 更新区間より右側
                if (updateR < segment.r) {
                    appendMerged(
                        nextSegments,
                        {
                            updateR + 1,
                            segment.r,
                            segment.keepMask,
                            segment.oneMask
                        }
                    );
                }
            }

            segments.swap(nextSegments);

            u64 sum = 0;

            for (const Segment& segment : segments) {
                const int left = max(segment.l, sumL);
                const int right = min(segment.r, sumR);

                if (left > right) {
                    continue;
                }

                const u64 length =
                    static_cast<u64>(right - left + 1);

                sum += length * segment.oneMask;

                sum += prefix.rangeMaskedSum(
                    left,
                    right,
                    segment.keepMask
                );
            }

            // 2^30 で割った余り
            y = static_cast<u32>(sum & FULL);
        }

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

    return 0;
}