[백준] 22355- 말뚝 (c++)

https://www.acmicpc.net/problem/22355

 

문제 요약

N개의 말뚝이 일렬로 박혀있다. 말뚝마다 처음 높이, 높이를 높이는 비용, 높이를 낮추는 비용이 주어진다.

연속한 K개 이상의 말뚝의 높이를 똑같이 만드는 데에 드는 비용의 최솟값을 구해라.

 

풀이 (NlogHlogH)

• 세그먼트 트리
• 삼분 탐색

말뚝의 높이를 h로 만드는 데에 드는 비용을 그래프로 나타내면 아래로 볼록한 모양이다. 따라서 말뚝 구간의 높이를 h로 만드는데 드는 비용 그래프 또한 아래로 볼록하다. 삼분 탐색으로 최적의 높이를 구할 수 있다.

각 말뚝의 높이를 h로 만드는 비용은 일차함수로 표현할 수 있는데 펜윅트리 두개로 여러 일차함수의 대한 쿼리를 처리할 수 있다. (계수를 관리하는 펜윅, 상수를 관리하는 펜윅)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)
const int N=1e5+1;

struct bit {
    vector<ll> tree=vector<ll>(N);
    void up(int x,int y) {
        while(x<N)
            tree[x]+=y,x+=x&-x;
    }
    ll qu(int x) {
        ll ret=0;
        while(x)
            ret+=tree[x],x-=x&-x;
        return ret;
    }
} gbit,sbit;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n,k;cin>>n>>k;
    vector<int> h(n+1),a(n+1),b(n+1);
    for(int i=1;i<=n;i++)
        cin>>h[i];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
        
    auto add = [&](int i) {
        gbit.up(h[i],a[i]); sbit.up(h[i],-a[i]*h[i]);
        gbit.up(1,-b[i]);gbit.up(h[i],b[i]);sbit.up(1,b[i]*h[i]);sbit.up(h[i],-b[i]*h[i]);
    };
    auto pop = [&](int i) {
        gbit.up(h[i],-a[i]); sbit.up(h[i],a[i]*h[i]);
        gbit.up(1,b[i]);gbit.up(h[i],-b[i]);sbit.up(1,-b[i]*h[i]);sbit.up(h[i],b[i]*h[i]);
    };
    auto co = [&](int x) {
        return gbit.qu(x)*x+sbit.qu(x);
    };
    
    for(int i=1;i<k;i++) add(i);
    
    ll ans=1e18;
    h[0]=1;
    for(int i=1;i<=n-k+1;i++) {
        pop(i-1);add(i+k-1);
        int st=1,en=1e5;
        while(st+3<=en) {
            int l=(st*2+en)/3,r=(st+en*2)/3;
            if(co(l)>co(r))
                st=l;   
            else
                en=r;
        }
        for(int j=st;j<=en;j++)
            ans=min(ans,co(j));
    }
    cout<<ans;
}