mayoko’s diary

プロコンとかいろいろ。

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

解法

large だと N の制約が 10^12 とかになっててビビりますが, よく考えると ai = 1, bi = 0 となっているところは無視しても良いので, 結局注目しなければならないところは M 個のみです。
ということで, まず最初に出てきた M 個の数字について座標圧縮をします。

こうすると, あとは M 個のクエリについて美味しさの変化を愚直に試していくことによって O(M^2) までは計算量が落ちます。ただ, これだとまだ時間が足りないのでもうちょっと工夫が必要です。

実はセグメント木を使えば計算量を O(MlogM) まで落とすことが出来ます。セグメント木をどう実装するかを考える前に,
値 x が (a0, b0) というボックス及び (a1, b1) というボックスを通った時どのような値になるのかを考えると,
a1*(a0*x+b0) + b1 = a1*a0*x + a1*b0+b1
となります。つまり, (a0, b0) と (a1, b1) というボックスを合わせると, (a1*a0, a1*b0+b1) というボックスと同じ, ということです。この考え方はセグメント木に使えそうですね(セグメント木は左側と右側をくっつける, という作業ができれば機能を持つことができるので)。ということで, 上で得られた式を使ってセグメント木を作りましょう。

const int MAXM = 100100;
ll p[MAXM];
double a[MAXM], b[MAXM];

class SegTree {
public:
    int n;
    vector<pair<double, double> > seg;
    SegTree() {}
    SegTree(int V) {init(V);}
    void init(int V) {
        n = 1;
        while (n < V) n *= 2;
        seg.resize(2*n-1);
        for (int i = 0; i < 2*n-1; i++) seg[i].first = 1, seg[i].second = 0;
    }
    void update(int k, double a, double b) {
        k += n-1;
        seg[k].first = a, seg[k].second = b;
        while (k > 0) {
            k = (k-1)/2;
            seg[k].first = seg[2*k+1].first*seg[2*k+2].first;
            seg[k].second = seg[2*k+1].second*seg[2*k+2].first + seg[2*k+2].second;
        }
    }
    pair<double, double> query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return pair<double, double>(0, 0);
        if (a <= l && r <= b) return seg[k];
        else {
            auto vl = query(a, b, 2*k+1, l, (l+r)/2);
            auto vr = query(a, b, 2*k+2, (l+r)/2, r);
            return make_pair(vl.first*vr.first, vl.second*vr.first+vr.second);
        }
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    int M;
    cin >> N >> M;
    map<ll, int> trans;
    for (int i = 0; i < M; i++) {
        cin >> p[i] >> a[i] >> b[i];
        trans[p[i]] = 1;
    }
    int k = 0;
    for (auto& p : trans) p.second = k++;
    SegTree seg(k);
    double mini = 1, maxi = 1;
    for (int i = 0; i < M; i++) {
        int j = trans[p[i]];
        seg.update(j, a[i], b[i]);
        auto tmp = seg.query(0, k, 0, 0, k);
        mini = min(mini, tmp.first+tmp.second);
        maxi = max(maxi, tmp.first+tmp.second);
    }
    printf("%.10lf\n", mini);
    printf("%.10lf\n", maxi);
    return 0;
}