AtCoder Regular Contest 008 D - タコヤキオイシクナール

(2021/04/30 追記) 考え方としてはイベントソートが近いのかなと思います.

座標圧縮を使わずに解いたので一応書きます.

解説

ソースコードを見た方が恐らく話が早いです(最下部にあります)

写像の合成などは既存解法と同じなので省略します.

ACL の遅延セグ木を使います. ACL の遅延セグメント木を使った区間アフィン変換 (Range Affine) はこの問題がそのままです.

モノイドの定義を次のようにします(すべてのクエリを処理した後にこうなる,という定義です).

  • seg( i) :=  i 番目の変更後に出来上がったたこ焼きの美味しさ

素数 (M + 1) 個を確保します( \because サンプル  3).このように定義することで,「各タイミングのたこ焼きの美味しさを,遅延セグメント木の上で区間アフィン変換をしながら同時に計算する」ということをやります.区間操作の順序はボックスの順序を優先すべきことに注意が必要で,それを実現するために map を使います(座標圧縮と対応するポイントです).map を使うことで,変更クエリをボックスごとに集計しつつ,その集計結果はボックスの番号の昇順になります.

集計が終わったらボックスごとに集計結果をオープンします. このうち,変更タイミングが最も遅いクエリ  i_{last} はそのクエリ適用後から最後まで, つまり  [i_{last}, M+1)区間で変更が反映されるべきです. その次に遅いクエリ  i_{last2} [i_{last2}, i_{last})区間で変更が反映されるべきです. この要領で遅い方から順に区間アフィン変換を実行していけばよいです.

すべてのクエリを処理した後, (M + 1) 個のモノイドにはそれぞれ「 i 番目の変更後に出来上がったたこ焼きの美味しさ」が入っているので,一つひとつ取り出して最小値と最大値をそれぞれ計算すれば OK です.

遅延セグメント木の上で最大値/最小値の計算も行いたい場合,モノイドを工夫して設計しないといけないことに注意が必要です *1.min/max の二項演算をナイーブに実装するだけではダメです *2

所感

試験管とはいえこれが橙 diff の時代があったんですね(90 分コンテストの D 問題ということもかなり影響してはいそうです).今なら ABC-F で出て青 diff 上位くらいでしょうか.

座標圧縮を使わずに解きましたが,それはあえてそうしたのではなく残念ながら思い付けなかったからです.座標圧縮してボックスをそのままセグメント木に載せる解法の方が直感的で分かりやすいと思います.

解答例

https://atcoder.jp/contests/arc008/submissions/22155530

#include <atcoder/lazysegtree>
using namespace atcoder;
 
// 区間アフィン・1点取得
using S = double;
struct F { double a, b; };
S op([[maybe_unused]] S a, [[maybe_unused]] S b) { return 0; }
S e() { return 1; }
S mapping(F f, S x) { return f.a * x + f.b; }
F composition(F f, F g) { return F{f.a * g.a, f.a * g.b + f.b}; }
F id() { return F{1, 0}; }
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
 
    ll N, M; cin >> N >> M;
    map<ll,vector<tuple<ll,double,double>>> mp;
    FOR(i,1,M+1) {
        ll p; double a, b; cin >> p >> a >> b;
        mp[p].push_back({i,a,b});
    }
 
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(M+1);
    for (auto& [_, T] : mp) {
        reverse(ALL(T));
        ll r = M+1;  // 右半開区間
        for (auto [l, a, b] : T) {
            seg.apply(l, r, F{a, b});
            r = l;
        }
    }
    double min_v = +INF;
    double max_v = -INF;
    REP(i,M+1) {
        double v = seg.get(i);
        chmin(min_v, v);
        chmax(max_v, v);
    }
    COUT(min_v);
    COUT(max_v);
 
    return 0;
}

*1:そもそも可能なんでしょうか…? 総和の場合は前述した問題の通り可能です

*2:供養します:https://atcoder.jp/contests/arc008/submissions/22151781