题解 P8904 [USACO22DEC] Mountains G

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

谢谢观看！