自动搬运

查看原文

来自洛谷，原作者为

	Lonely_NewYear 云吹开沙 火成霞

搬运于2025-08-24 22:43:36，当前版本为作者最后更新于2022-12-28 22:31:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8904 题解

模拟。

题目大意

有 $n$ 座山，每座山有高度 $h_i$，每次提高某个山的高度，同时询问有多少组山能互相看到（能互相看到指山峰连线上没有阻挡）。

题目分析

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

对于初始高度，枚举第 $i$ 个山峰，向右不断找能看见的山，同时计算视线斜率，复杂度 $O(n^2\log n)$。

每次提高第 $x$ 座山峰的高度时，枚举 $x$ 左边的山峰 $i$，先判断 $x$ 能不能被看见，能的话就向右依次删除被 $x$ 挡住的山峰，对于第 $x$ 座山，直接重构对应的 set。因为对于每个 $i<x$，每次修改最多使它能看见的山峰数加 1，所以最多删除 $n+q$ 次。对于 $x$，每次最多使它能看见的山峰数加 $n$，所有山加起来最多 $nq$ 次，复杂度 $O((n^2+nq)\log n)$。

总复杂度 $O((n^2+nq)\log n)$，常数非常大，不开 O2 过不去，开 O2 最慢的点 2.22s。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001;
int n,q;
int h[MAXN];
double cal(int i,int j){
	return 1.0*(h[j]-h[i])/(j-i);
}
set<int> st[MAXN];
int lower(int i,int x){
	auto p=st[i].lower_bound(x);
	p--;
	return *p;
}
int upper(int i,int x){
	auto p=st[i].upper_bound(x);
	return *p;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>h[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		st[i].insert(0);
		st[i].insert(n+1);
		double now=-1e9;
		for(int j=i+1;j<=n;j++)
			if(now<=cal(i,j))now=cal(i,j),st[i].insert(j),ans++;
	}
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		h[x]+=y;
		for(int i=1;i<x;i++){
			int y=lower(i,x);
			if(y&&cal(i,y)>cal(i,x))continue;
			if(st[i].find(x)==st[i].end())st[i].insert(x),ans++;
			y=upper(i,x);
			while(y<=n){
				if(cal(i,x)<=cal(i,y))break;
				st[i].erase(y),ans--;
				y=upper(i,y);
			}
		}
		ans-=st[x].size()-2;
		st[x].clear();
		st[x].insert(0);
		st[x].insert(n+1);
		double now=-1e9;
		for(int j=x+1;j<=n;j++)
			if(now<=cal(x,j))now=cal(x,j),st[x].insert(j),ans++;
		cout<<ans<<'\n';
	}
	return 0;
}

谢谢观看！