We first present a naive solution.

Let's fix the mountain $i$ that Bessie is standing on, and consider which mountains she can see. If she can see mountain $j > i$, that means that for all $i < k < j$, $\frac{h_k-h_i}{k-i} \leq \frac{h_j-h_i}{j-i}$. Thus, for each $i$, we can calculate how many $j$ satisfy this property by sweeping from left to right. We repeat this process after every update, yielding a time complexity of $O(QN^2)$.

Joe's code:

#include <bits/stdc++.h>
using namespace std;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

typedef long long ll;

int N;
ll h[5100];

int main() {
    fastIO();
    cin >> N;
    for (int i = 1; i <= N; i++) { cin >> h[i]; }
    int Q;
    cin >> Q;
    for (int i = 1; i <= QN; i++) {
        int x, y;
        cin >> x >> y;
        h[x] += y;
        int ans = 0;
        for (int j = 1; j <= N; j++) {
            ll bh = 0, bd = -1;
            for (int k = j + 1; k <= N; k++) {
                if (bd == -1) {
                    ans++;
                    bd = 1, bh = h[k] - h[j];
                } else if ((ll)(h[k] - h[j]) * bd >= (ll)bh * (k - j)) {
                    ans++;
                    bd = k - j, bh = h[k] - h[j];
                }
            }
        }
        cout << ans << "\n";
    }
}

To speed this up, we can maintain a "monotonic set" for each index $i$. In the $i$th set, we store in sorted order all indices $j$ such that for all $i < k < j$, $\frac{h_k-h_i}{k-i} \leq \frac{h_j-h_i}{j-i}$. When we perform an update at an index $x$, we do the following:

• For $i < x$, because the updates always increase the height of a mountain, the value of $\frac{h_x-h_i}{x-i}$ increases. So we may need to insert $x$ into the monotonic set for $i$ if it is now visible from $i$, and delete any indices greater than $x$ no longer visible from $i$. For each $i$, this may be done in $O(\log N)$ amortized time, for a total of $O(N\log N)$ amortized time.
• For $i = x$, we can naively reupdate the entire monotonic set for $i$, which takes $O(N)$ or $O(N\log N)$ time.
• For $i > x$, the update does not affect the monotonic sets.

Thus, we can perform each update in $O(N\log N)$. Initially, we perform the process described in the naive solution once to initialize the monotonic sets in $O(N^2\log N)$ amortized time. Therefore, the total time complexity is $O(N^2\log N+QN\log N)$ or $O(N^2 + QN\log N)$ depending on whether the set you are using supports removing a range of $c$ consecutive elements in $O(c+\log N)$ time.

Note: to avoid using doubles to compare two fractions $\frac{a}{b}$ and $\frac{c}{d}$, we can instead compare $a\cdot d$ and $b \cdot c$.

Joe's code:

#include <bits/stdc++.h>
using namespace std;

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

typedef long long ll;
#define ff first
#define ss second
int N, Q;
ll h[5100];
set<int> rig[5100]; // monotonic sets

bool comp(int ind, int i1, int i2) {
    // does index i2 to ind have a greater slope than index i1 to ind
    int d1 = abs(ind - i1), d2 = abs(ind - i2);
    ll h1 = h[i1] - h[ind], h2 = h[i2] - h[ind];
    return h2 * d1 >= h1 * d2;
}

int main() {
    fastIO();
    cin >> N;
    for (int i = 1; i <= N; i++) { cin >> h[i]; }
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            if (rig[i].empty()) {
                rig[i].insert(j);
            } else {
                if (comp(i, *rig[i].rbegin(), j)) { rig[i].insert(j); }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) ans += (int)rig[i].size();
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int x, y;
        cin >> x >> y; // update mountain x by incrementing it by height y
        h[x] += y;
        // update the sets to the left of x
        for (int j = 1; j <= x - 1; j++) {
            auto it = rig[j].lower_bound(x);
            bool add = false;
            if ((*it) == x) {
                add = true;
                it++;
            } else {
                --it;
                if (comp(j, (*it), x)) {
                    rig[j].insert(x);
                    ans++;
                    add = true;
                    it++;
                    it++;
                }
            }
            if (add) {
                while (it != rig[j].end() && !comp(j, x, (*it))) {
                    it = rig[j].erase(it);
                    ans--;
                }
            }
        }
        // update the set for x
        ans -= (int)rig[x].size();
        rig[x].clear();
        for (int j = x + 1; j <= N; j++) {
            if (rig[x].empty()) {
                rig[x].insert(j);
                ans++;
            } else {
                if (comp(x, *rig[x].rbegin(), j)) {
                    rig[x].insert(j);
                    ans++;
                }
            }
        }
        cout << ans << "\n";
    }
}

Note: The above solution takes nearly 3s to run on some test cases. Depending on your language and implementation, you may have trouble passing all test cases even with the intended time complexity. In particular, a Java analog of the solution above using TreeSets took over 13s on some test cases (slower than the naive solution).

There are several ways to pass this problem without coming too close to the time limit:

• Use vectors instead of sets (or ArrayLists instead of TreeSets in Java). The time complexity becomes $O(N^3+QN^2)$ or $O(QN^2)$ depending on your implementation, which is worse than the set solution, but we were unable to construct a test case where this solution took more than 2s to run, presumably because erasing from a vector has a good constant factor.
• Use a segment tree instead of a set. The time complexity is the same as the set solution, but the constant factor is better. Our implementation runs in 0.8s.
• Use a bitset instead of a set. The time complexity is $O(N^2+QN^2/B)$, where we assume standard operations on $B=64$-bit integers (for such an integer, checking whether it is nonzero, finding its first set bit, and finding its last set bit) take $O(1)$ time. The implementation below runs in 0.1s.

Ben's code:

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// Source: https://nyaannyaan.github.io/library/misc/bitset-find-prev.hpp.html
template <size_t Nb> struct Bitset : bitset<Nb> {
    template <typename... Args> Bitset(Args... args) : bitset<Nb>(args...) {}

    static constexpr int N = Nb;
    static constexpr int array_size = (Nb + 63) / 64;

    union raw_cast {
        array<uint64_t, array_size> a;
        Bitset b;
    };

    int _Find_prev(size_t i) const {
        if (i == 0) return -1;
        if ((*this)[--i] == true) return i;
        size_t M = i / 64;
        const auto &a = ((raw_cast *)(this))->a;
        uint64_t buf = a[M] & ((1ull << (i & 63)) - 1);
        if (buf != 0) return M * 64 + 63 - __builtin_clzll(buf);
        while (M--) {
            if (a[M] != 0) return M * 64 + 63 - __builtin_clzll(a[M]);
        }
        return -1;
    }

    inline int _Find_last() const { return _Find_prev(N); }
};

vector<ll> h;
bool comp(int ind, int i1, int i2) {
    return (i1 - ind) * (h[i2] - h[ind]) >= (i2 - ind) * (h[i1] - h[ind]);
}

Bitset<2000> segs[2000];
int N;

void build(Bitset<2000> &b, int st) {
    int lst = st;
    b.reset();
    for (int i = st + 1; i < N; ++i) {
        if (comp(st, lst, i)) {
            lst = i;
            b[i] = 1;
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N;
    h.resize(N);
    for (auto &t : h) cin >> t;
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        build(segs[i], i);
        ans += segs[i].count();
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y;
        cin >> x >> y;
        --x;
        h[x] += y;
        for (int j = 0; j < x; ++j) {
            int it = segs[j]._Find_next(x);
            int it_minus_one = segs[j]._Find_prev(it);
            assert(it_minus_one != -1);
            if (!comp(j, it_minus_one, x)) { continue; }
            if (!segs[j][x]) {
                segs[j][x] = 1;
                ++ans;
            }
            while (it < N) {
                if (comp(j, x, it)) break;
                int next_it = segs[j]._Find_next(it);
                segs[j][it] = 0;
                --ans;
                it = next_it;
            }
        }
        ans -= segs[x].count();
        build(segs[x], x);
        ans += segs[x].count();
        cout << ans << "\n";
    }
}