問題概要

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 <= 10¹²
・1 <= M <= 100000
・-1.0 <= a[i], b[i] <= 1.0

解法

N <= 10¹² は完全に蛇足で、(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;
}

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

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

AtCoder ARC 008 D - タコヤキオイシクナール (試験管橙色)

問題概要

解法

コード