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

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-15 11:52:50
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3,820 ms / 6,000 ms
• コード長: 10,540 bytes
• コンパイル時間: 3,442 ms
• コンパイル使用メモリ: 374,124 KB
• 実行使用メモリ: 44,672 KB
• 最終ジャッジ日時: 2026-09-04 22:26:24
• 合計ジャッジ時間: 30,388 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

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

class FastInput {
    static constexpr size_t BUF_SIZE = 1 << 20;

    char buf_[BUF_SIZE];
    size_t pos_ = 0;
    size_t len_ = 0;

    inline char getChar() {
        if (pos_ == len_) {
            len_ = fread(buf_, 1, BUF_SIZE, stdin);
            pos_ = 0;
            if (len_ == 0) return '\0';
        }
        return buf_[pos_++];
    }

public:
    template <class T>
    inline void readInt(T& value) {
        char c = getChar();
        while (c <= ' ') c = getChar();

        bool neg = false;
        if constexpr (is_signed_v<T>) {
            if (c == '-') {
                neg = true;
                c = getChar();
            }
        }

        using U = make_unsigned_t<T>;
        U x = 0;

        while (c >= '0' && c <= '9') {
            x = x * 10 + static_cast<U>(c - '0');
            c = getChar();
        }

        if constexpr (is_signed_v<T>) {
            value = neg ? -static_cast<T>(x) : static_cast<T>(x);
        } else {
            value = static_cast<T>(x);
        }
    }
};

static inline void append_uint32(string& out, uint32_t x) {
    char buf[10];
    int len = 0;

    do {
        buf[len++] = static_cast<char>('0' + x % 10);
        x /= 10;
    } while (x != 0);

    while (len--) out.push_back(buf[len]);
    out.push_back('\n');
}

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

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

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

    int n_ = 0;
    int size_ = 1;
    vector<Node> tree_;

    vector<int> saved_epoch_;
    int epoch_ = 0;
    vector<pair<int, Node>> history_;

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

    void save(int p) {
        if (saved_epoch_[p] == epoch_) return;
        saved_epoch_[p] = epoch_;
        history_.emplace_back(p, tree_[p]);
    }

    void build(int p, int l, int r, const vector<U32>& a) {
        tree_[p] = Node{};
        if (l == r) {
            const U32 value = (l < n_ ? a[l] : 0);
            tree_[p].sum = value;
            tree_[p].any = value;
            tree_[p].all = value;

            for (int b = 0; b < BITS; ++b) {
                tree_[p].cnt[b] = (value >> b) & 1U;
            }
            return;
        }

        const int mid = (l + r) >> 1;
        build(p << 1, l, mid, a);
        build(p << 1 | 1, mid + 1, r, a);

        Node& cur = tree_[p];
        const Node& left = tree_[p << 1];
        const Node& right = tree_[p << 1 | 1];

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

    U32 apply_or(int p, int len, U32 mask) {
        Node& cur = tree_[p];
        const U32 changed = mask & ~cur.all;
        if (changed == 0) return 0;

        save(p);

        U32 bits = changed;
        while (bits != 0) {
            const int b = __builtin_ctz(bits);
            bits &= bits - 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;

        return changed;
    }

    U32 apply_and(int p, U32 mask) {
        Node& cur = tree_[p];
        const U32 changed = cur.any & ~mask;
        if (changed == 0) return 0;

        save(p);

        U32 bits = changed;
        while (bits != 0) {
            const int b = __builtin_ctz(bits);
            bits &= bits - 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;

        return changed;
    }

    void push(int p, int l, int r) {
        Node& cur = tree_[p];

        if (l == r || (cur.lazy_and == VALUE_MASK && cur.lazy_or == 0)) {
            return;
        }

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

        const U32 lazy_and = cur.lazy_and;
        const U32 lazy_or = cur.lazy_or;

        apply_and(p << 1, lazy_and);
        apply_or(p << 1, left_len, lazy_or);

        apply_and(p << 1 | 1, lazy_and);
        apply_or(p << 1 | 1, right_len, lazy_or);

        save(p);
        cur.lazy_and = VALUE_MASK;
        cur.lazy_or = 0;
    }

    void pull_changed(int p, int len, U32 changed) {
        if (changed == 0) return;

        save(p);

        Node& cur = tree_[p];
        const Node& left = tree_[p << 1];
        const Node& right = tree_[p << 1 | 1];

        U32 bits = changed;

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

            const U32 bit_mask = U32(1) << b;
            const U32 old_count = cur.cnt[b];
            const U32 new_count = left.cnt[b] + right.cnt[b];

            if (new_count > old_count) {
                cur.sum += contribution(new_count - old_count, b);
            } else {
                cur.sum -= contribution(old_count - new_count, b);
            }

            cur.cnt[b] = new_count;

            if (new_count == 0) {
                cur.any &= ~bit_mask;
            } else {
                cur.any |= bit_mask;
            }

            if (new_count == static_cast<U32>(len)) {
                cur.all |= bit_mask;
            } else {
                cur.all &= ~bit_mask;
            }
        }
    }

    U32 range_or_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql) return 0;
        if ((mask & ~tree_[p].all) == 0) return 0;

        if (ql <= l && r <= qr) {
            return apply_or(p, r - l + 1, mask);
        }

        push(p, l, r);

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

        const U32 changed_left =
            range_or_impl(p << 1, l, mid, ql, qr, mask);

        const U32 changed_right =
            range_or_impl(p << 1 | 1, mid + 1, r, ql, qr, mask);

        const U32 changed = changed_left | changed_right;

        pull_changed(p, r - l + 1, changed);

        return changed;
    }

    U32 range_and_impl(int p, int l, int r, int ql, int qr, U32 mask) {
        if (qr < l || r < ql) return 0;
        if ((tree_[p].any & ~mask) == 0) return 0;

        if (ql <= l && r <= qr) {
            return apply_and(p, mask);
        }

        push(p, l, r);

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

        const U32 changed_left =
            range_and_impl(p << 1, l, mid, ql, qr, mask);

        const U32 changed_right =
            range_and_impl(p << 1 | 1, mid + 1, r, ql, qr, mask);

        const U32 changed = changed_left | changed_right;

        pull_changed(p, r - l + 1, changed);

        return changed;
    }

    U64 range_sum_impl(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree_[p].sum;

        push(p, l, r);

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

        return range_sum_impl(p << 1, l, mid, ql, qr)
             + range_sum_impl(p << 1 | 1, mid + 1, r, ql, qr);
    }

public:
    explicit RollbackLazySegTree(const vector<U32>& a) {
        n_ = static_cast<int>(a.size());

        while (size_ < n_) size_ <<= 1;

        tree_.resize(size_ << 1);
        saved_epoch_.assign(size_ << 1, 0);
        history_.reserve(4096);

        build(1, 0, size_ - 1, a);
    }

    void begin_subproblem() {
        ++epoch_;
        history_.clear();
    }

    void rollback() {
        for (auto it = history_.rbegin(); it != history_.rend(); ++it) {
            tree_[it->first] = it->second;
        }

        history_.clear();
    }

    void range_or(int l, int r, U32 mask) {
        range_or_impl(1, 0, size_ - 1, l, r, mask);
    }

    void range_and(int l, int r, U32 mask) {
        range_and_impl(1, 0, size_ - 1, l, r, mask);
    }

    U64 range_sum(int l, int r) {
        return range_sum_impl(1, 0, size_ - 1, l, r);
    }
};

static inline 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() {
    static constexpr uint32_t VALUE_MASK =
        (uint32_t(1) << 30) - 1;

    FastInput in;

    int N, M;
    in.readInt(N);
    in.readInt(M);

    vector<uint32_t> A(N);
    for (auto& value : A) {
        in.readInt(value);
    }

    vector<uint32_t> l(M + 1);
    vector<uint32_t> r(M + 1);
    vector<uint32_t> x(M + 1);
    vector<uint32_t> L(M + 1);
    vector<uint32_t> R(M + 1);

    for (int i = 1; i <= M; ++i) in.readInt(l[i]);
    for (int i = 1; i <= M; ++i) in.readInt(r[i]);
    for (int i = 1; i <= M; ++i) in.readInt(x[i]);
    for (int i = 1; i <= M; ++i) in.readInt(L[i]);
    for (int i = 1; i <= M; ++i) in.readInt(R[i]);

    RollbackLazySegTree seg(A);

    int Q;
    in.readInt(Q);

    string output;
    output.reserve(static_cast<size_t>(Q) * 11);

    for (int i = 1; i <= Q; ++i) {
        int s, q;
        in.readInt(s);
        in.readInt(q);

        seg.begin_subproblem();

        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 big_u = clamp_index(L[z] ^ y, N);
            const int big_v = clamp_index(R[z] ^ y, N);

            const int sum_l = min(big_u, big_v) - 1;
            const int sum_r = max(big_u, big_v) - 1;

            const uint32_t mask = x[z] ^ y;

            if ((z & 1) == 0) {
                seg.range_or(ql, qr, mask);
            } else {
                seg.range_and(ql, qr, mask);
            }

            y = static_cast<uint32_t>(
                    seg.range_sum(sum_l, sum_r)
                ) & VALUE_MASK;
        }

        append_uint32(output, y);

        seg.rollback();
    }

    fwrite(output.data(), 1, output.size(), stdout);

    return 0;
}