IOI '15 P4 - Horses (Standard I/O)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>

using namespace std;

const int MAX_Y = 2e9;

struct Segment {
    int l, r, bestV, bestI;
    Segment() {}
    Segment(int left, int right, int v, int i): l(left), r(right), bestV(v), bestI(i) {}
    bool operator < (const Segment &s2) const {
        return pair<int, int>(l, r) < pair<int, int>(s2.l, s2.r);
    }
};

// Modular arithmetic
const int BASE = 1e9 + 7;
int add(int x, int y) {
    x += y;
    if (x >= BASE) return x-BASE;
    return x;
}
int mult(int x, int y) {
    return (long long)x*y % BASE;
}

// Segment Tree on range product over X and range max over Y
class Node {
private:
    int xProduct = 1, yMax = 0, yMaxI = -1;
    Node * left, * right;
public:
    // all ranges [)
    void update(int l, int r, int i, int x, int y) {
        if (l+1 == r) {
            xProduct = x, yMax = y, yMaxI = l;
            return;
        }
        if (!left) left = new Node();
        if (!right) right = new Node();

        int mid = (l + r) / 2;
        if (i < mid) left->update(l, mid, i, x, y);
        else right->update(mid, r, i, x, y);
        xProduct = mult(left->xProduct, right->xProduct);
        tie(yMax, yMaxI) = max(pair<int, int>{left->yMax, left->yMaxI}, pair<int, int>{right->yMax, right->yMaxI});
    }
    pair<int, pair<int, int>> rangeQuery(int l, int r, int ql, int qr) {
        if (r <= ql || qr <= l) return {1, {0, -1}};
        else if (ql <= l && r <= qr) return {xProduct, {yMax, yMaxI}};
        else {
            int mid = (l + r) / 2;
            pair<int, pair<int, int>> pr1{1, {0, -1}}, pr2{1, {0, -1}};
            if (left) pr1 = left->rangeQuery(l, mid, ql, qr);
            if (right) pr2 = right->rangeQuery(mid, r, ql, qr);
            return {mult(pr1.first, pr2.first), max(pr1.second, pr2.second)};
        }
    }
};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> X(n), Y(n);
    for (int &x : X) cin >> x;
    for (int &y : Y) cin >> y;

    Node * root = new Node(); // segment tree
    for (int i = 0; i < n; ++i) root->update(0, n, i, X[i], Y[i]);

    set<Segment> segments; // of equal multiplier
    auto createSegment = [&](int l, int r) {
        auto res = root->rangeQuery(0, n, l, r+1);
        segments.emplace(l, r, res.second.first, res.second.second);
    };
    for (int i = 0, start = 0; i < n; ++i) {
        if (i == n-1 || X[i+1] > 1) {
            createSegment(start, i);
            start = i+1;
        }
    }

    auto maxProfit = [&]() {
        int best = n, bestVal = 0, bestCoefficient = 1;
        int coefficient = 1;
        for (set<Segment>::reverse_iterator it = segments.rbegin(); it != segments.rend(); ++it) {
            int val = it->bestV, i = it->bestI;
            if (best == n || (long long)val * bestCoefficient > (long long)bestVal * coefficient) {
                best = i, bestVal = val, bestCoefficient = coefficient;
            }
            int x = X[it->l];
            if ((long long)coefficient * x > MAX_Y) break;
            coefficient *= x;
        }
        // prefix product of x[i] up to best multiplied by Y[best]
        auto res = root->rangeQuery(0, n, 0, best+1);
        return mult(res.first, Y[best]);
    };

    cout << maxProfit() << '\n';
    int m; cin >> m;
    while (m--) {
        int type, pos, val;
        cin >> type >> pos >> val;
        bool wasSegmentStart = X[pos] > 1;
        if (type == 1) X[pos] = val;
        else Y[pos] = val;
        root->update(0, n, pos, X[pos], Y[pos]);
        bool isSegmentStart = X[pos] > 1;

        auto it = segments.upper_bound({pos, n+1, 0, 0});
        --it;

        if (pos != 0 && wasSegmentStart != isSegmentStart) {
            // must update segments
            if (wasSegmentStart) {
                // merge segments it and prev(it)
                int r = it->r;
                it = prev(segments.erase(it));
                int l = it->l;
                segments.erase(it);
                createSegment(l, r);
            } else {
                // split segment it
                int l = it->l, r = it->r;
                segments.erase(it);
                createSegment(l, pos-1);
                createSegment(pos, r);
            }
        } else {
            // still need to update the segments' max Y
            int l = it->l, r = it->r;
            segments.erase(it);
            createSegment(l, r);
        }
        cout << maxProfit() << '\n';
    }
    return 0;
}