結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー iastm
提出日時 2025-10-06 18:16:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,634 bytes
コンパイル時間 1,634 ms
コンパイル使用メモリ 137,148 KB
実行使用メモリ 115,224 KB
最終ジャッジ日時 2025-10-06 18:16:59
合計ジャッジ時間 42,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <atcoder/lazysegtree>

struct S {
    int64_t sum = 0, max = 0;
    int count = 0;
};

S op(S a, S b) {
    return {a.sum + b.sum, a.max > b.max ? a.max : b.max, a.count + b.count};
}

S e() {
    return {};
}

S mapping(int64_t f, S x) {
    if (f < 0) return x;
    return {f * x.count, f, x.count};
}

int64_t composition(int64_t f, int64_t g) {
    if (f < 0) return g;
    return f;
}

int64_t id() {
    return -1;
}

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<S> A(N);
    for (S &a : A) std::cin >> a.sum, a.max = a.sum, a.count = 1;

    atcoder::lazy_segtree<S, op, e, int64_t, mapping, composition, id> seg(A);

    std::map<int, std::pair<int, int64_t>> intervals;
    int i = 0;
    while (i < N) {
        int j = i + 1;
        while (j < N && A[i].sum == A[j].sum) j++;
        intervals[i] = {j, A[i].sum};
        i = j;
    }

    std::map<std::pair<int64_t, int64_t>, int64_t> gcd_map;
    auto gcd = [&](auto gcd, int64_t a, int64_t b) -> int64_t {
        if (a < b) return gcd(gcd, b, a);
        auto iter = gcd_map.find({a, b});
        if (b == 0) return a;
        if (iter != gcd_map.end()) return iter->second;
        return gcd_map[{a, b}] = gcd(gcd, b, a % b);
    };

    while (Q--) {
        int t, l, r;
        std::cin >> t >> l >> r;
        l--;
        if (t == 1) {
            int64_t y;
            std::cin >> y;
            seg.apply(l, r, y);
            auto start = intervals.lower_bound(l);
            if (start != intervals.begin() && l < std::prev(start)->second.first) {
                if (std::prev(start)->second.first > r) {
                    start = intervals.emplace(r, std::prev(start)->second).first;
                }
                std::prev(start)->second.first = l;
            }
            auto stop = intervals.lower_bound(r);
            if (stop != intervals.begin() && r < std::prev(stop)->second.first) {
                stop = intervals.emplace(r, std::prev(stop)->second).first;
            }
            intervals.erase(start, stop);
            intervals[l] = {r, y};
        } else if (t == 2) {
            int64_t x;
            std::cin >> x;
            auto start = intervals.lower_bound(l);
            if (start != intervals.begin() && l < std::prev(start)->second.first) {
                if (std::prev(start)->second.first > r) {
                    start = intervals.emplace(r, std::prev(start)->second).first;
                }
                start = intervals.emplace(l, std::prev(start)->second).first;
                std::prev(start)->second.first = l;
            }
            auto stop = intervals.lower_bound(r);
            if (stop != intervals.begin() && r < std::prev(stop)->second.first) {
                stop = intervals.emplace(r, std::prev(stop)->second).first;
                std::prev(stop)->second.first = r;
            }
            auto iter = start;
            while (iter != stop) {
                int nl = iter->first;
                auto &[nr, val] = iter->second;
                val = gcd(gcd, val, x);
                seg.apply(nl, nr, val);
                if (iter != intervals.begin() && nl == std::prev(iter)->second.first && val == std::prev(iter)->second.second) {
                    std::prev(iter)->second.first = nr;
                    iter = intervals.erase(iter);
                } else iter++;
            }
        } else if (t == 3) {
            std::cout << seg.prod(l, r).max << std::endl;
        } else {
            std::cout << seg.prod(l, r).sum << std::endl;
        }
    }
}
0