[USACO 2022 December Gold] Mountains (BOJ 26970)

문제 링크

 

관찰 1. 모든 기울기의 종류가 그렇게 많지 않다.

• 모든 업데이트가 하나의 원소에 대한 것이므로 모든 순간에 대해 가능한 기울기는 최대 $O(n^2 + nq)$이다.
• 따라서, 각 원소를 최대 한 번씩만 삭제하는 것이 가능하다면, 알고리즘은 시간 내에 동작할 것이다.

생각 1. $i$번째 산이 볼 수 있는 산 $j$들을 자료구조로 관리하면서, 업데이트 이후 볼 수 없게 된 산들만 잘 골라내서 지우고 싶다.

• 스택 또는 셋으로 관리하고 싶은데, 기울기가 단조 증가하도록 관리되는 것이 자연스럽다.
• 그런데, 셋의 정의가 '볼 수 있는 산들'이기 때문에, 기울기가 증가하는 순서가 곧 인덱스가 증가하는 순서이기도 하다.

관찰 2. 셋 내에서 삭제되어야 하는 원소들은 연속되어 있다.

• $[$기존 높이와 이루는 기울기, 새로운 높이와 이루는 기울기$)$가 셋에서 삭제되게 된다.
• 애초에 '볼 수 있는 산'에 대한 셋이었다면, 이 구간의 인덱스 위치도 올바른 부분만 선택하게 되므로 올바르다.

 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2003, Q = N;
ll n, q;
ll h[N];

struct angle{
    ll x, y;
    bool operator < (const angle &rhs) const {
        if (y * rhs.x == rhs.y * x) return false;
        return y * rhs.x < rhs.y * x;
    }
};
set<int> canSee[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;++i)cin>>h[i];
    
    auto build = [](int i) {
        angle mx {1,-ll(1e9)-20};
        for(int j=i+1;j<=n;++j){
            angle cur = {j-i,h[j]-h[i]};
            if(cur < mx)continue;
            mx = cur;
            canSee[i].insert(j);
        }
    };
    
    auto result = []() {
        ll res=0;
        for(int i=1;i<=n;++i)res+=size(canSee[i]);
        return res;
    };
    
    for(int i=1;i<=n;++i){
        build(i);
    }
    
    cin>>q;
    for(int _=1;_<=q;++_){
        int i, d;
        cin>>i>>d;
        
        angle mx{1,-ll(1e9)-20};
        for(int j=i-1;j>=1;--j){
            assert(!canSee[j].empty());
            
            angle pre {i-j,h[i]   -h[j]};
            angle cur {i-j,h[i]+d -h[j]};
            
            for(auto it = canSee[j].lower_bound(i);
                     it!= canSee[j].end() && angle{*it-j, h[*it]-h[j]}<cur;
                     it = canSee[j].erase(it)){
            }
            
            if(angle{i-j,h[j]-h[i]-d} < mx)continue;
            mx = angle{i-j,h[j]-h[i]-d};
            
            canSee[j].insert(i);
        }
        
        canSee[i].clear();
        h[i] += d;
        build(i);
        
        cout << result() << '\n';
    }
}