けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。

セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります:

問題概要

https://beta.atcoder.jp/contests/arc008/tasks/arc008_4

N 個の一次関数 (s[i], t[i]) (x -> s[i]x + t[i]) の合成関数を考える。
最初はすべての i について s[i] = t[i] = 1 である。
今、M 個の変更 (q[i], a[i], b[i]) が加えられ、

q[i] 番目の一次関数を a[i] x + b[i] に書き換える

初期状態および、この M 回の変更後のそれぞれについて、
合成関数に 1 を入れたときの出力を求め、その M + 1 個の値の最大値と最小値を求めよ。

・1 <= N <= 1012
・1 <= M <= 100000
・-1.0 <= a[i], b[i] <= 1.0

解法

N <= 1012 は完全に蛇足で、(1, 0) のところは無視していいので、 実質最大 M 個の合成関数。座標圧縮する。

(a, b) のあとに (c, d) を合成した関数は c(ax+b)+d = acx + bc+d なので

(a, b), (c, d) -> (ac, bc+d)

となる。
この二項演算を実装したセグメントツリーを作れば良い。

コード

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <iomanip>
using namespace std;


template<class Monoid> struct SegTree {
    using Func = function<Monoid(Monoid, Monoid)>;
    const Func F;
    const Monoid UNITY;
    int SIZE_R;
    vector<Monoid> dat;
    
    SegTree(int n, const Func f, const Monoid &unity): F(f), UNITY(unity) { init(n); }
    void init(int n) {
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, UNITY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = v; }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k)
            dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* update, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = v;
        while (k >>= 1) dat[k] = F(dat[k*2], dat[k*2+1]);
    }
    
    /* get {min-value, min-index}, a and b are 0-indexed */
    Monoid get(int a, int b) {
        Monoid vleft = UNITY, vright = UNITY;
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = F(vleft, dat[left++]);
            if (right & 1) vright = F(dat[--right], vright);
        }                                                                                                              
        return F(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R]; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            cout << (*this)[i];
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};



int main() {
    long long N; int M; cin >> N >> M;
    vector<long long> p(M), pls;
    vector<double> a(M), b(M);
    for (int i = 0; i < M; ++i) {
        cin >> p[i] >> a[i] >> b[i]; --p[i];
        pls.push_back(p[i]);
    }
    sort(pls.begin(), pls.end());
    pls.erase(unique(pls.begin(), pls.end()), pls.end());
    int NN = (int)pls.size();

    SegTree<pair<double,double> > seg(NN,
                                      [](pair<double,double> a, pair<double,double> b){
                                          return make_pair(a.first * b.first, a.second * b.first + b.second);
                                      },
                                      make_pair(1, 0)
                                      );

    double Min = 1.0, Max = 1.0;
    for (int i = 0; i < M; ++i) {
        int idx = lower_bound(pls.begin(), pls.end(), p[i]) - pls.begin();
        seg.update(idx, make_pair(a[i], b[i]));
        pair<double,double> res = seg.get(0, NN);
        Min = min(Min, res.first + res.second);
        Max = max(Max, res.first + res.second);
    }
    cout << fixed << setprecision(10) << Min << endl << Max << endl;
}