IOI '05 P3 - Mountain

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

vector<int> relevantID; // compressed indices

// Segment tree
class Node {
private:
    long long mx = 0;
    long long propAdd = 0; // for query that adds on range
    long long propA = -1, propB = -1; // for query that sets range to A*i + B
    Node * left, * right;
    void add(long long k) { // adds k over this node's range
        mx += k;
        propAdd += k;
    }
    void set(int l, int r, long long a, long long b) { // sets this node's range to a*relevantID[i] + b
        propAdd = 0;
        propA = a, propB = b;
        mx = max(a*relevantID[l] + b, a*relevantID[r-1] + b); // linear, so maximum is at one of the endpoints
    }

    void prop(int l, int r) { // this node covers range [l, r)
        if (!left) left = new Node();
        if (!right) right = new Node();
        if (propA == -1 && propB == -1) {
            left->add(propAdd);
            right->add(propAdd);
        } else {
            int m = (l + r) / 2;
            propB += propAdd;
            left->set(l, m, propA, propB);
            right->set(m, r, propA, propB);
        }
        propAdd = 0;
        propA = -1, propB = -1;
    }

public:
    // Updates
    void rangeAdd(int l, int r, int ql, int qr, long long k) { // adds k between indices ql and qr
        if (r <= ql || qr <= l) return;
        if (ql <= l && r <= qr) add(k);
        else {
            prop(l, r);
            int m = (l + r) / 2;
            left->rangeAdd(l, m, ql, qr, k);
            right->rangeAdd(m, r, ql, qr, k);
            mx = max(left->mx, right->mx);
        }
    }
    void rangeSet(int l, int r, int ql, int qr, long long a, long long b) { // sets range between ql and qr to a*relevantID[i] + b
        if (r <= ql || qr <= l) return;
        if (ql <= l && r <= qr) set(l, r, a, b);
        else {
            prop(l, r);
            int m = (l + r) / 2;
            left->rangeSet(l, m, ql, qr, a, b);
            right->rangeSet(m, r, ql, qr, a, b);
            mx = max(left->mx, right->mx);
        }
    }

    // Queries
    long long getValue(int l, int r, int i) {
        Node * node = this;
        while (l+1 < r) {
            node->prop(l, r);
            int m = (l + r) / 2;
            if (i < m) node = node->left, r = m;
            else node = node->right, l = m;
        }
        return node->mx;
    }
    int firstGreaterThan(int l, int r, int h) {
        if (mx <= h) return r; // no such nodes
        Node * node = this;
        while (l+1 < r) {
            node->prop(l, r);
            int m = (l + r) / 2;
            if (node->left->mx > h) node = node->left, r = m;
            else node = node->right, l = m;
        }
        return l;
    }
};

int main() {
    // Input and compress indices of points
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> queryA, queryB, queryD;
    relevantID = {0, n};
    for (char c; cin >> c && c != 'E'; ) {
        if (c == 'I') {
            int a, b, D; cin >> a >> b >> D;
            queryA.push_back(a);
            queryB.push_back(b);
            queryD.push_back(D);
            relevantID.push_back(a);
            if (a > 1) relevantID.push_back(a-1);
            relevantID.push_back(b);
            if (b < n) relevantID.push_back(b+1);
        } else {
            int h; cin >> h;
            queryA.push_back(-1);
            queryB.push_back(-1);
            queryD.push_back(h);
        }
    }
    sort(relevantID.begin(), relevantID.end());
    relevantID.resize(unique(relevantID.begin(), relevantID.end()) - relevantID.begin());
    int m = relevantID.size();

    // Build segment tree of max height in range of size m on relevant indices
    Node * root = new Node();
    for (size_t q = 0; q < queryA.size(); ++q) {
        if (queryA[q] == -1) { // Query
            int h = queryD[q];
            int pos = root->firstGreaterThan(0, m, h);

            int smallestIndex = n+1;
            if (pos < m) {
                int curID = relevantID[pos], prvID = relevantID[pos-1];
                long long curV = root->getValue(0, m, pos), prvV = root->getValue(0, m, pos-1);
                // the function must be linear between prv and cur
                assert(prvV <= h);
                assert((curV-prvV)%(curID-prvID) == 0);
                int D = (curV-prvV)/(curID-prvID);
                int steps = (h-prvV)/D + 1;
                assert(prvID + steps <= curID);

                smallestIndex = prvID + steps;
            }

            cout << smallestIndex-1 << '\n';
        } else { // Update
            int a = queryA[q], b = queryB[q], D = queryD[q];
            // find compressed positions
            int first = lower_bound(relevantID.begin(), relevantID.end(), a) - relevantID.begin();
            int last = lower_bound(relevantID.begin(), relevantID.end(), b) - relevantID.begin();

            long long lastInitial = root->getValue(0, m, last);

            // we know that first-1 is the compressed index for a-1 and last+1 is the compressed index for b+1, since we added a-1 and b+1 into relevantID
            long long v = root->getValue(0, m, first-1);
            // A*id + B = value, D * (a-1) + B = v <=> B = v - D(a-1)
            root->rangeSet(0, m, first, last+1, D, v-D*(a-1LL));

            long long lastFinal = root->getValue(0, m, last);
            long long suffixDelta = lastFinal - lastInitial;
            root->rangeAdd(0, m, last+1, m, suffixDelta);
        }
    }
    return 0;
}