一道不是特别难的题，但是场上不会做

首先注意到数据范围不是经典数字1e5，所以考虑 $O(n^2)$ 做法

$0$ 分做法

提交下面代码即可：

#include<iostream>
using namespace std;
int main(){
    这是0分做法 
    return 0;
}

$20$ 分做法

按照题意模拟

$50$ 分做法

对于每一个 $i$，考虑他向右看能看到多少人，注意到对于一个 $i$ 他能看到的 $j$ 的斜率是单调递增的，直接暴力修改，模拟即可

#include<iostream>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
constexpr int N=2005;
int _=1,n,q,a[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
inline double calc(int a,int b,int c,int d){return (d-b)*1.0/(c-a)*1.0;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		q=reads();
		while(q--){
			int x,y,ans=0;
			x=reads(),y=reads();a[x]+=y;
			for(int i=n;i>=1;i--){
				double maxn=-2e9;
				for(int j=i+1;j<=n;j++){
					double dududu=calc(i,a[i],j,a[j]);
					if(dududu>=maxn){
						maxn=dududu;
						ans++;
					}
				}
			}printf("%d\n",ans);
		}
	}
	return 0;
}

$100$ 分做法

我们考虑记录出来每一个 $i$ 能看到谁，然后将一个 $x$ 的高度增加可以将某些东西删除即可

我们使用set维护出来对于一个 $i$ 能看到的所有的人的编号

我们每修改一个 $a_x$，首先查看 $a_x$ 能不能被看到，如果不能被看到直接break，如果能看到，将所有编号比 $x$ 大且斜率比我的后面的人全部删掉

直接暴力删除即可，因为对于每一个 $a_x$，只会加进set中 $n^2$ 次，而每一个只会删除 $1$ 次，所以时间复杂度是 $O(n^2)$ 的

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<set>
#define N 2005
using namespace std;
bool Test_MLE_start;
int _=1,n,q,a[N];
multiset<int> st[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
inline double calc(int a,int b,int c,int d){return (d-b)*1.0/(c-a)*1.0;}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		for(int i=n;i>=1;i--){
			double maxn=-2e9;st[i].insert(0),st[i].insert(n+1);
			for(int j=i+1;j<=n;j++){
				double p=calc(i,a[i],j,a[j]);
				if(p>=maxn) maxn=p,st[i].insert(j);
			}
		}q=reads();
 		while(q--){
			int x,y,ans=0;x=reads(),y=reads();
			a[x]+=y;
			for(int i=1;i<x;i++){
				auto pit=st[i].lower_bound(x);pit--;
				int p=(*pit);
				if(p&&calc(i,a[i],p,a[p])>calc(i,a[i],x,a[x])) continue;
				auto it=st[i].find(x);
				if(it==st[i].end()) st[i].insert(x);
				p=*st[i].upper_bound(x);
				while(p<=n){
					if(calc(i,a[i],x,a[x])<=calc(i,a[i],p,a[p])) break;
					st[i].erase(p);
					p=*st[i].upper_bound(p);
				}
			}st[x].clear(),st[x].insert(0),st[x].insert(n+1);
			double maxn=-2e9;
			for(int j=x+1;j<=n;j++){
				double p=calc(x,a[x],j,a[j]);
				if(p>=maxn) maxn=p,st[x].insert(j);
			}for(int i=1;i<=n;i++) ans+=st[i].size()-2;
			printf("%d\n",ans);
		}
	}
	return 0;
}

你们咋跑得这么MAN

前人之述备矣，然则 $set$ 换成 $vector$ 可以跑$0.5s$

贴一个非常抽象的线段树做法

首先我们注意到对于$i$来说，能看见$j$，需要满足对于任意的$Slope(i,j)>=Slope(i,k),k∈(i,j)$ 所以我们直接对每一个$i$开一颗线段树来维护前缀最大值，记$pre_{max}(i,x)=max(Slope(i,s))，s∈(i,x]$，然后再开一颗来维护贡献（应该也可以合并到一颗上）。

这样的话初始贡献就很好求了，暴力建树即可。 然后考虑修改$x$，发现修改$x$对于$x$后面的山是没有影响的，所以我们只考虑，$i<x$的山和$x$本身。

考虑$i<x$的山，注意到每次$x$的高度都是增加的，也就是$Slope(i,x)$都会变大，不会变小，这个时候我们就可以直接在线段树上二分，对于每个i找到第一个小于$Slope(i,x)$的前缀，然后分两种情况讨论：

第一种，如果这个点在$x$之前，说明修改$x$不会对$i$看到$x$后面的山造成影响，我们设修改前的$i$和$x$的斜率为$Slope'(i,x)$，修改后的$x$产生贡献当且仅当

1.之前没有产生过贡献，也就是$Slope'(i,x)<pre_{max}'(i,x)$

2.现在是前缀最大值了，也就是$pre_{max}'(i,x)<=Slope(i,x)$

然后修改一下前缀最大值就可以了，这种情况就完事了。

第二种，这个点在$x$后面，说明有一坨$j$，他们的$Slope(i,j)$都是小于$Slope(i,x)$的，这个时候他们的贡献清零，然后对于这个点后面的点，是不影响他们的贡献的，因为这个点后面的点$pre_{max}$都大于等于$Slope(i,x)$，不会被影响到。然后显然$x$这个位置是有贡献的，修改一下就可以了。

接着考虑$x$，直接暴力重构就可以了。

然后就做完了，复杂度是$O(n(n+q)logn)$的，跑3s是没问题的。然后要注意下空间，实现精细一点，否则会爆（这就是为什么我赛时这个题爆蛋了），然后精度要注意一下。

代码十分构式，就不放了，大家想锻炼自己代码能力可以逝逝。

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;
}