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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-12 05:07:08
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3,715 ms / 6,000 ms
• コード長: 10,852 bytes
• コンパイル時間: 2,667 ms
• コンパイル使用メモリ: 364,912 KB
• 実行使用メモリ: 61,696 KB
• 最終ジャッジ日時: 2026-09-04 22:22:56
• 合計ジャッジ時間: 25,322 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

using u32 = uint32_t;
using u64 = uint64_t;

class FastIO {
    static constexpr size_t INPUT_SIZE = 1 << 20;
    static constexpr size_t OUTPUT_SIZE = 1 << 20;

    char inputBuffer[INPUT_SIZE];
    char outputBuffer[OUTPUT_SIZE];

    size_t inputPos = 0;
    size_t inputLen = 0;
    size_t outputPos = 0;

    inline char readChar() {
        if (inputPos == inputLen) {
            inputLen = fread(
                inputBuffer,
                1,
                INPUT_SIZE,
                stdin
            );
            inputPos = 0;

            if (inputLen == 0) {
                return 0;
            }
        }

        return inputBuffer[inputPos++];
    }

public:
    ~FastIO() {
        flush();
    }

    template <class T>
    inline void readInt(T& value) {
        char c = readChar();

        while (c <= ' ') {
            c = readChar();
        }

        bool negative = false;

        if (c == '-') {
            negative = true;
            c = readChar();
        }

        T result = 0;

        while ('0' <= c && c <= '9') {
            result =
                result * 10
                + static_cast<T>(c - '0');
            c = readChar();
        }

        if constexpr (is_signed_v<T>) {
            value = negative ? -result : result;
        } else {
            value = result;
        }
    }

    inline void writeChar(char c) {
        if (outputPos == OUTPUT_SIZE) {
            flush();
        }

        outputBuffer[outputPos++] = c;
    }

    template <class T>
    inline void writeInt(T value, char end = '\n') {
        if constexpr (is_signed_v<T>) {
            if (value < 0) {
                writeChar('-');
                value = -value;
            }
        }

        char buffer[32];
        int length = 0;

        do {
            buffer[length++] =
                static_cast<char>('0' + value % 10);
            value /= 10;
        } while (value != 0);

        while (length != 0) {
            writeChar(buffer[--length]);
        }

        if (end != 0) {
            writeChar(end);
        }
    }

    inline void flush() {
        if (outputPos != 0) {
            fwrite(
                outputBuffer,
                1,
                outputPos,
                stdout
            );
            outputPos = 0;
        }
    }
};

FastIO io;

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() {
    io.readInt(N);
    io.readInt(M);

    vector<u32> A(N + 1);

    for (int i = 1; i <= N; ++i) {
        io.readInt(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) {
        io.readInt(l[i]);
    }

    for (int i = 1; i <= M; ++i) {
        io.readInt(r[i]);
    }

    for (int i = 1; i <= M; ++i) {
        io.readInt(x[i]);
    }

    for (int i = 1; i <= M; ++i) {
        io.readInt(L[i]);
    }

    for (int i = 1; i <= M; ++i) {
        io.readInt(R[i]);
    }

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

    build(1, 1, N, A);

    int Q;
    io.readInt(Q);

    history.reserve(200000);

    for (int problemIndex = 1; problemIndex <= Q; ++problemIndex) {
        int s, q;
        io.readInt(s);
        io.readInt(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
            );
        }

        io.writeInt(y);

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

    return 0;
}