結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <utility>
#include <atcoder/lazysegtree>
// #include <kotone/container_hash>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_CONTAINER_HASH_HPP
#define KOTONE_CONTAINER_HASH_HPP 1

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

namespace kotone {

// A hash for pairs of integral values.
// If possible, consider hashing plain integers as a computationally-cheaper alternative.
template <typename S, typename T> struct pair_hash {
    std::size_t operator()(const std::pair<S, T> &p) const {
        uint64_t x = static_cast<uint64_t>(p.first);
        uint64_t y = static_cast<uint64_t>(p.second);
        return std::hash<uint64_t>()((x >> 32 ^ x) << 32 | (y >> 32 ^ y));
    }
};

}  // namespace kotone

#endif  // KOTONE_CONTAINER_HASH_HPP

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;
        if (A[i].sum > 1) {
            while (j < N && A[i].sum == A[j].sum) j++;
            intervals[i] = {j, A[i].sum};
        }
        i = j;
    }

    std::unordered_map<std::pair<int64_t, int64_t>, int64_t, kotone::pair_hash<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 (val > 1) {
                    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 iter = intervals.erase(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