P8904 Mountains USACO22DEC G
感觉这题做法非常暴力。
对于一个楼房，我们钦定对于点 \(x\)，若 \(x<y\) 若符合题目条件，我们称作 \(x\) 看见 \(y\)，否则我们称作 \(y\) 看见 \(x\)。
首先题目判断一个楼房是否能被看见是通过斜率来判断的，具体如下图。
然后我们考虑用一个set来维护每一个楼房能看见的所有楼房。
一开始把初始状态预处理出来。然后对于每一次修改 \(x\) 楼房的操作，显然先把 \(x\) 的高度加上应该加的。首先考虑能看到 \(x\) 的点，即 \(x\) 前面的点 。
我们枚举 \(\le x\) 的每一个点 \(i\)，找到 \(i\) 能看到的位置不超过 \(x\) 且最远的楼房 \(y\)（这个点要么最高要么最矮），然后再判断连接 \((i,x)\) 的直线的斜率与连接 \((i,y)\) 的大小即可判断 \(x\) 是否能被 \(i\) 看见。
如果这个点不能被 \(i\) 看见，那这个点必然不会对 \(i\) 能看见的楼房数目产生影响。
但如果这个点能被 \(i\) 看见，那么我们需要枚举 \(x\) 后面所有能被 \(i\) 看见的点，判断斜率，直到有一个点 \(z\) 与 \(i\) 的斜率大于 \((i,x)\) 的斜率（这样 \(x\) 必定不会对后面产生任何影响，因为此时 \(h_z>h_x\)）。
最后我们再来处理 \(x\) 能看见的新的点，其实做法很暴力，我们直接每次清空 \(x\) 能看见的点，然后把仿照预处理把所有位置预处理一边即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int inf=1e9;
int h[N],n,ans;
set<int> s[N];
double getk(int i,int j){
return 1.0*(h[j]-h[i])/(j-i);
}
int main(){
// freopen("test.in","r",stdin);
cin>>n;for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=n;i++){
s[i].insert(0);s[i].insert(n+1);
double tmp=-inf;
for(int j=i+1;j<=n;j++){
if(tmp<=getk(i,j)){
// cout<<i<<" "<<j<<endl;
tmp=getk(i,j);ans++;s[i].insert(j);
}
}
}
// cout<<ans<<endl;
int T;cin>>T;
while(T--){
int x,y;cin>>x>>y;h[x]+=y;
for(int i=1;i<x;i++){
auto p=s[i].lower_bound(x);--p;int tmp=*p;
if(tmp and getk(i,tmp)>getk(i,x)) continue;
if(s[i].find(x)==s[i].end()){s[i].insert(x);ans++;}//如果以前i看不到x，现在i看得到x了
p=s[i].upper_bound(x);tmp=*p;
while(tmp<=n){
if(getk(i,tmp)>=getk(i,x) and h[tmp]>=h[x]) break;
s[i].erase(tmp);ans--;p=s[i].upper_bound(tmp);tmp=*p;
}
}
ans-=s[x].size()-2;
s[x].clear();s[x].insert(0);s[x].insert(n+1);double tmp=-inf;
for(int j=x+1;j<=n;j++){
if(tmp<=getk(x,j)){
tmp=getk(x,j);ans++;s[x].insert(j);
}
}
cout<<ans<<"\n";
}
return 0;
}