20分做法

按照题意模拟即可

50分做法

如果 $j$ 到 $i$ 这一段所有点中，$j$ 和 $i$ 的斜率是最大的，就能互相看到。

复杂度 $\mathcal O(qn^2)$，但在洛谷上已经能过了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int n,q,a[N];
inline double slope(int i,int j) {return (a[i]-a[j])*1.0/(i-j);}
double mx[N];
signed main() {
	cin>>n;
	for(int i=1; i<=n; ++i) cin>>a[i];
	cin>>q;
	while(q--) {
		int x,y,ans=0;
		cin>>x>>y;
		a[x]+=y;
		for(int i=1; i<=n; ++i) mx[i]=-1e18;
		for(int i=2; i<=n; ++i) {
			for(int j=1; j<i; ++j) {
				double s=slope(i,j);
				if(mx[j]<=s) ++ans,mx[j]=s;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

满分做法

每一个人往后看，能看到的人与他连线的斜率是单调不降的。对于每一个人开一个 STL-set 存他往后能看到的人。每一次对于 $x$，直接重构 $x$ 的 set。对于 $x$ 前面的所有 $i$ 也要更新，要把 $x$ 挡住的删掉，还要看看新的 $x$ 能不能让 $i$ 看见。这些用斜率判断就行了。

对于 $i<x<j$，如果 $slope(i,x)>slope(i,j)$，$j$ 就被挡住了。

然后删的时候如果 set 本来有 $x$，先把 $x$ 删掉，最后再加进去，这个地方特判一下。如果 $x$ 的前驱没有挡住 $x$ 就行。

总共只会删除 $nq$ 个。均摊下来复杂度 $\mathcal O((n^2+nq)\log n)$。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=2005;
int n,q,a[N],ans;
set<int>s[N];
inline double slope(int i,int j) {return (double)(a[i]-a[j])/(i-j);}
signed main() {
	R(n);
	for(int i=1; i<=n; ++i)R(a[i]);
	for(int i=1; i<=n; ++i) {
		double mx=-1e18;
		for(int j=i+1; j<=n; ++j) {
			if(slope(i,j)>=mx) mx=slope(i,j),s[i].insert(j);
		}
	}
	for(int i=1; i<=n; ++i) ans+=s[i].size();
	R(q);
	while(q--) {
		int x,y;
		R(x),R(y);
		a[x]+=y,s[x].clear();
		double mx=-1e18;
		for(int j=x+1; j<=n; ++j) {
			if(slope(x,j)>=mx) mx=slope(x,j),s[x].insert(j);
		}
		for(int i=1; i<x; ++i) {
			if(s[i].empty()) {
				s[i].insert(x);
				continue;
			}
			bool fl=1;
			auto it=s[i].lower_bound(x);
			if(it!=s[i].begin()){
				--it;
				if(slope(x,i)<slope(*it,i)) fl=0;
				++it;
			}
			auto l=it,r=it;
			while(r!=s[i].end()&&(*r==x||slope(x,i)>slope(*r,i))) ++r;
			if(l!=r) s[i].erase(l,r);
			if(fl) s[i].insert(x);
		}
		ans=0;
		for(int i=1; i<=n; ++i) ans+=s[i].size();
		cout<<ans<<"\n";
	}
	return 0;
}