BOJ 14181 - 함수와 쿼리 (D3)

CHT 처음 배울때 봤다가 이게 왜 CHT지 하고 탈주했다.

http://boj.kr/14181

14181번: 함수와 쿼리

풀이) Li-chao + Segment Tree

 

점화식을 세우기 영 쉽지 않아 보인다.

그러므로 정의에 따라 점화식을 관찰하자.

$$f(1,j)=a[j]$$

$$f(2,j)=min(f(1,j),f(1,j-1))+a[j]$$

$$=min(2\ast a[j],a[j-1]+a[j])$$

a[j]를 안으로 넣은 것이다.

$$f(3,j)=min(f(2,j),f(2,j-1))+a[j]$$

$$=min(3\ast a[j],a[j-1]+2\ast a[j],2\ast a[j-1]+a[j],a[j]+a[j-1]+a[j-2])$$

 

직접 해보면서 얻을 수 있는 f(i,j)에 대한 결론은 다음과 같다.

 

f(i, j) := 아래와 같은 규칙을 이용해서 배열에서 i개의 수를 고를 때, 그 합의 최솟값

규칙 

(1)a[j]는 골라져 있다.

(2)임의의 k에 대하여, a[k]를 고르려면 a[k+1]이 적어도 하나 이상 골라져 있어야 한다.

(3)a[k]는 여러번 고를 수 있다.

 

위 규칙을 해석해보자.

예제 1

위 그림처럼 만약 j=4라면, 

이런식으로 고를 수 있다는 의미이다.

위에서 파란색으로 표시된 부분이며, 여기서 3, 4를 원하는 만큼 더할 수 있다.(최소 1개 이상)

 

예를 들어 위 상태에서 i=3이라면 4를 1번 더하고, 3을 2번 더할 수 있다.

또 4를 2번 더하고, 3을 1번 더할 수도 있다.

 

여기까지 됐다 치자. 그렇다면 이걸 어디에 활용할까?

위 규칙에 따를 때, 어떻게 더하면 최솟값이 나오는 지를 생각해볼수 있다.

 

예를 들어 위 상황을 그대로 생각해보자. i=3, j=4이다.

그럼 이렇게 3가지 경우로 고를 수 있다. (a[4]만 이용 / a[3], a[4] 이용 / a[2], a[3], a[4] 이용)

그럼 여기서 최솟값은 무엇일까? 당연히 a[2]+a[3]+a[4]이다.

즉 어떤 구간이 있다면 작은 값을 당연히 많이 더하는 것이 이득이다. 4+4+4>2+3+4임은 당연하다.

 

쨌든 결론은, 어떤 구간에서 최소인 하나의 값 빼고는 다 한번씩 더한다고 해도 무방하다는 것이다!

간단히 알아보자.

 

위 상황에서 5개의 수를 더해야 하고 각각 1번 이상씩 더할 때, a를 2번, b를 1번, c를 2번 더하면 값이 최소라고 가정하자.

(즉, 2번 이상 더한 수가 2개 이상 존재한다는 것이다.)

 

그럼 자명하게 b>a, b>c이므로 b는 고려할 필요가 없다.

만약 a<c라면, 최적해는 a를 3번, b,c를 각각 1번씩 이용하는 것이 더 작으므로 a<c는 아니다.

만약 a>c라면, 최적해는 a,b를 각각 1번씩, c를 3번 이용하는 것이 더 작으므로 a>c는 아니다.

a<c도 아니고, a>c도 아니므로 a=c이다.

 

a=c이므로 a를 2번, b를 1번, c를 2번 사용하는 것은 a를 3번, b를 1번, c를 1번 사용하는 것과 같다.

따라서 하나의 값만 빼고 다 한번씩 더한다고 해도 최적해를 구할 수 있다!

 

휴... 힘들다. 글로 쓰니까 힘든데, 직접 써보면서 생각해보면 그렇게 어려운 내용은 아닐 것이다.

쨌든 위 결론을 이용하면 dp 식을 세울 수 있다.

$$f(i,j)=min(P[j]-P[k]+a[k]\ast (i-(j-k)))$$

a[i]는 주어진 배열, P[i]는 a의 prefix sum이다. k는 j-i<=k<=j를 만족하는 정수이다.

P[j]-P[k]는 j->k로 이동하는데 더하는 값, a[k]*(i - (j-k))는 a[k]를 최대한 더하는 것이다.

즉 i개를 더할 때 a[k]를 최대한 많이 더하기 위해, j-k개는 이동하는데 쓰고 나머지는 다 a[k]를 더하는 것이다.

위 식을 변형하자.

$$=min(P[j]-P[k]+a[k]\ast i-a[k]\ast j+a[k]\ast k)$$

$$=min(a[k]\ast (i-j)-P[k]-a[k]\ast k)+P[j]$$

y = a[k] * x + (-P[k]-a[k]*k] 꼴로 생각하고 x = (i-j)를 대입한다고 생각하면, CHT로 구할 수 있게 된다.

근데 문제는 k의 조건이 j-i<=k<=j인 것이다. 즉 모든 직선을 다 사용할 수 없다.

이는 세그먼트 트리에 리차오 트리를 넣어서 해결할 수 있다. (코드 참조)

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
const ll inf = 2e18;
ll n, q;
ll a[101010];
ll p[101010];
struct Line{
    ll a, b;
    ll f(ll x){return a*x+b; }
};
Line max(Line a, Line b, ll x){ return a.f(x) >= b.f(x) ? a : b; }
Line min(Line a, Line b, ll x){ return a.f(x) < b.f(x) ? a : b; }
struct Node{
    ll l,r,s,e;
    Line line;
};
struct li_chao{
    vector<Node> tree;
    void init(ll s, ll e){ tree.push_back({-1,-1,s,e,{0,inf}}); }
    void upd(ll node, Line k){
        if(tree.empty())tree.push_back({-1,-1,(ll)-1e9, (ll)1e9, {0, inf}});
        ll s = tree[node].s, e = tree[node].e;
        Line low = min(tree[node].line, k, s), high = max(tree[node].line, k, s);
        if(low.f(e) <= high.f(e)){
            tree[node].line = low;
            return;
        }
        ll mid = s+e>>1;
        if(low.f(mid) <= high.f(mid)){   //mid 오른쪽에 교점
            tree[node].line = low;
            if(tree[node].r == -1){
                tree[node].r = tree.size();
                tree.push_back({-1,-1,mid+1,e,{0,inf}});
            }
            upd(tree[node].r, high);
        }
        else{
            tree[node].line = high;
            if(tree[node].l == -1){
                tree[node].l = tree.size();
                tree.push_back({-1,-1,s,mid,{0,inf}});
            }
            upd(tree[node].l, low);
        }
    }
    ll query(ll node, ll x){
        if(node==-1)return inf;
        ll s = tree[node].s, e = tree[node].e;
        ll mid = s+e>>1;
        if(x<=mid)return min(query(tree[node].l, x), tree[node].line.f(x));
        return min(query(tree[node].r, x), tree[node].line.f(x));
    }
};
struct segtree{
    vector<li_chao> T;
    segtree(): T(404040){}
    void upd(ll node, ll s, ll e, ll idx, Line diff){
        if(idx<s or e<idx)return;
        T[node].upd(0, diff);
        if(s==e)return;
        ll mid = s+e>>1;
        upd(node*2, s, mid, idx, diff); upd(node*2+1, mid+1, e, idx, diff);
    }
    ll query(ll node, ll s, ll e, ll l, ll r, ll x){
        if(e<l or r<s)return inf;
        if(l <= s and e <= r)return T[node].query(0, x);
        ll mid = s+e>>1;
        return min(query(node*2, s, mid, l, r, x), query(node*2+1, mid+1, e, l, r, x));
    }
};
int main(){
    fast;
    cin>>n;
    segtree seg;
    seg.T.resize(n+1);
    for(int i = 1 ; i <= n ; i++){
        cin>>a[i];
        p[i] = p[i-1]+a[i];
        seg.upd(1,1,n,i,{a[i], -p[i]+a[i]*i});
    }
    seg.upd(1,0,n,0,{0,0});
    cin>>q;
    while(q--){
        ll i, j; cin>>i>>j;
        cout<<seg.query(1, 1, n, j-i, j, i-j)+p[j]<<"\n";
    }
}

세그먼트 트리의 각 노드에 리차오 트리를 넣고, 구간마다 리차오 트리의 최솟값을 관리하면 된다.

개빨리품