Mountains (USACO Gold December 2022)

考虑暴力用 $n$ 个set维护每个山能看见的右边的山。

对于初始高度，枚举第 $i$ 个山峰，向右不断找能看见的山，同时计算视线斜率。

执行查询时，每次提高第 $x$ 座山峰的高度，这时有三种情况：

从 $x$ 左侧的山往右看：将 $x$ 与set中左边的山峰比较，如果 $x$ 的斜率低，则 $x$ 不能被看见。能的话，再向右依次删除被 $x$ 挡住的山峰，整个程序执行过程最多删除 $n^2$ 次，所以复杂度 $\mathcal{O}(n^2 \log n)$ 。
从 $x$ 山自己往右看：直接暴力重构对应的set就可以了。
从 $x$ 右侧的山往右看：没有变化。

复杂度是 $\mathcal{O}((n^2+nq)\log n)$ 。

这个题还有线段树的更快的解决，但set这个办法比较简单。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,Q;
int h[2005];
set<int> is[2005];      // is[i]: increasing set from i {idx}
const double INF = 1e18;
int ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &h[i]);
    auto grad = [](int i, int j) -> double {
        return (double)(h[i]-h[j]) / (i-j);
    };
    for (int i = 0; i < n-1; i++) {
        double mx = -INF;
        for (int j = i+1; j < n; j++) {
            double G = grad(j,i);
            if (G >= mx) {
                mx = G;
                is[i].insert(j);
            }
        }
        ans += is[i].size();
    }
 
    scanf("%d", &Q);
    for (int q = 0; q < Q; q++) {
        int x,y;
        scanf("%d %d", &x, &y);
        x--;
        h[x] += y;
        for (int i = 0; i < x; i++) {   // use is[] to update counts before x
            int orig = is[i].size();
            double G = grad(x,i);
            is[i].insert(x);
            auto it = is[i].find(x);
            if (it != is[i].begin() && grad(i, *prev(it)) > G) {   // we are too low
                is[i].erase(it);
            } else {    // remove lower nodes after x
                auto nxt = it;
                for (it++; it != is[i].end() && grad(i, *it) < G; it = nxt) {
                    nxt = next(it);
                    is[i].erase(it);
                }                
            }
            ans += is[i].size() - orig;
        }
 
        int orig = is[x].size();
        is[x].clear();
        double mx = -INF;
        for (int i = x+1; i < n; i++) { // brute force to update counts for x
            double G = grad(i,x);
            if (G >= mx) {
                mx = G;
                is[x].insert(i);
            }
        }
        ans += (is[x].size() - orig);
        printf("%d\n", ans);
    }
    return 0;
}