BOJ 34107 Collecting Stamps 4 (JOISC 2024-2025 Day 2 P2)

문제 링크

풀이

시작점을 고정했다고 해 보자. 시작점이 WLOG $1$이라고 할 때, 스탬프 $1$과 $2N$을 swap하지 못한다.

스탬프 제작소 $2N$개에 각각 $A_1, A_2, \cdots, A_{2N}$의 색 스탬프가 있다고 하자. 이때 모든 도장 카드에 도장을 찍을 수 있는 조건이 무엇일까? 바로 모든 $1 \le i, j \le N$에 대해 $(i, j)$가 $A$에 부분수열로 등장하는 것이다. 그런데 특정 $(i, j)$ 쌍에 대해, $j, j, i, i$ 순으로 배치된 게 아니라면 $(i, j)$는 항상 존재한다. 따라서 찍을 수 없는 스탬프의 수가 $j, j, i, i$ 순으로 배치된 스탬프 $(i, j)$ 쌍의 개수임을 알 수 있다.

여기서, 각 스탬프가 두 번 등장하는데, 첫 번째 등장을 $1$로 바꾸고 두 번째 등장을 $2$로 바꾼 뒤 inversion을 계산하면 정확히 저 케이스가 된다는 것을 알 수 있다. 그 이유는, 특정 $(i, j)$가 inversion에 기여할 조건이 한 스탬프의 두 번째 등장이 다른 스탬프의 첫 번째 등장보다 늦은 것인데, 이것이 inversion이 생길 조건과 같기 때문이다. 따라서 이 문제는 기본적으로 inversion counting으로 해석해야 한다. 여기까지 왔다면, "$X$의 비용을 이용해 교환" 등의 조건은 그냥 각 교환이 inversion을 1 줄이는 거라고 해석하는 것이 더 쉽다.

$2N$개의 시작점 각각에 대해, 초기 inversion의 개수를 구할 수 있다고 가정하고, 각각을 $v_1, v_2, \cdots, v_{2N}$이라고 하자. 각각에서 시작하는 비용은 문제에서 $c_1, c_2, \cdots, c_{2N}$으로 주어져 있다. 이때 $i$번 시작점에서 시작해 스탬프 $J$개를 찍는 최소 비용을 어떻게 구할까? 스탬프 $J$개를 찍는다는 건 $K := n^2 - J$ 이하로 inversion을 줄인다는 말과 같다. 따라서 $\min_{1 \le i \le {2N}} \left( c_i + X \min(v_i - K, 0) \right)$을 구하면 된다.

일단 먼저 $v_i$를 빠르게 구해 보자. $v_i$는 $1$과 $2$만 있는 수열에서의 inversion이다. $v_i$ 하나를 구하는 것은 간단하게 할 수 있는데, 모든 $1$에 대해 그 앞의 $2$의 개수를 세서 더하면 되고, 이는 누적합으로 간단하게 할 수 있다. 모든 $v_i$를 구하기 위해서는, $v_i$에서 $v_{i+1}$로 넘어갈 때 수열이 다음과 같이 변함을 관측하자.

• 맨 왼쪽에 있던 $1$가 오른쪽으로 넘어가고,
• 해당 $1$, 그리고 그 수와 같은 $A_i$를 가졌던 $2$가 서로 교체되어 두 수가 바뀐다.

이제 이 상황에서 inversion을 빠르게 계산하는 것은 Fenwick Tree를 이용하면 쉽다.

$cost(i, K) = (c_i + X \min(v_i - K, 0))$이라고 가정해 보자. 여기서 $i$를 고정한 뒤, $x$축을 $K$, $y$축을 함숫값으로 놓고 그래프를 그려 보면 $K$ 왼쪽은 기울기 $-X$의 선분, $K$ 오른쪽은 기울기 $0$의 반직선을 가지는 그래프가 만들어진다. 이런 그래프들이 여러 개 있을 때, 특정 $x$ 값에서의 최솟값을 쉽게 찾을 수 있어야 한다.

다양한 방법이 있을 텐데, 나는 그래프의 기울기 $-X$ 부분과 $0$ 부분을 따로 관리하기로 했다. 이렇게 하면 양쪽을 그냥 기울기가 같은 선분이나 반직선들의 집합으로 생각할 수 있고, 기울기 $-X$인 선분들은 모두 $x = 0$에서 시작하고, 기울기 $0$인 반직선들은 모두 $x = \infty$까지 이어진다는 공통점이 있다. 여기서는 정렬하고 monotone chain을 빼내는 방식으로 생각하면 $O(n \log n)$에 어렵지 않게 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick{
    int n;
    ll tree[4'000'002];

    void init(int _n){
        n = _n;
    }
    void add(int x, ll v){
        while(x<=n){
            tree[x]+=v;
            x+=x&-x;
        }
    }
    ll sum(int x){
        ll ret=0;
        while(x){
            ret += tree[x];
            x-=x&-x;
        }
        return ret;
    }
    ll sum(int l, int r){
        return sum(r)-sum(l-1);
    }
} f1, f2;

int n, q; ll X;
int A[2'000'002];
ll C[2'000'002];
ll query[2'000'002];

int pos[2'000'002];
bool chk[2'000'002];
int S[2'000'002], E[2'000'002];
ll inv[2'000'002];

struct Line{
    ll a, b; /// y = ax + b
    ll lim;
    Line(){}
    Line(ll a, ll b, ll lim): a(a), b(b), lim(lim){}

    bool operator<(const Line &r)const{
        if(lim != r.lim) return lim < r.lim;
        return b > r.b;
    }

    ll get(ll x){
        return x*a+b;
    }
};

vector<Line> vec1, vec2;
ll ans[2'000'005];

int main(){
    cin>>n>>X;
    n*=2;
    for(int i=1; i<=n; i++) cin>>A[i];
    for(int i=1; i<=n; i++) cin>>C[i];
    cin>>q;
    for(int i=1; i<=q; i++) cin>>query[i];

    f1.init(n*2);
    f2.init(n*2);

    ll sum = 0;
    for(int i=1; i<=n; i++){
        if(!chk[A[i]]){
            S[A[i]] = i, pos[i] = 1, chk[A[i]]=1;
            f1.add(i, 1);
            sum += f2.sum(1, i-1);
        }
        else{
            E[A[i]] = i, pos[i] = 2;
            f2.add(i, 1);
        }
    }

    inv[1] = sum;
    for(int i=1; i<n; i++){
        f1.add(i, -1);
        int opp = pos[i] == 1 ? E[A[i]] : S[A[i]] + n;
        f2.add(opp, -1);
        sum -= f1.sum(opp, n*2);
        f1.add(opp, 1);
        sum += f2.sum(1, opp);
        f2.add(i+n, 1);
        inv[i+1] = sum;
    }

    for(int i=1; i<=n; i++){
        vec1.push_back(Line(-X, X*inv[i] + C[i], inv[i]));
        vec2.push_back(Line(0, C[i], -inv[i]));
    }

    function<void(vector<Line>&)> monotone = [](vector<Line> &vec){
        vector<Line> new_vec = vec;
        sort(new_vec.begin(), new_vec.end());
        vec.clear();

        for(Line &p: new_vec){
            while(!vec.empty() && vec.back().b >= p.b) vec.pop_back();
            vec.push_back(p);
        }
    };

    monotone(vec1);
    monotone(vec2);

    for(int i=1; i<=q; i++){
        ans[i] = 3e18;

        ll val = ll(n)*n/4 - query[i];
        auto it = lower_bound(vec1.begin(), vec1.end(), Line(0, 0, val), [](Line A, Line B){return A.lim<B.lim;});
        if(it != vec1.end()) ans[i] = min(ans[i], it->get(val));

        it = lower_bound(vec2.begin(), vec2.end(), Line(0, 0, -val), [](Line A, Line B){return A.lim<B.lim;});
        if(it != vec2.end()) ans[i] = min(ans[i], it->get(-val));

        cout << ans[i] << '\n';
    }
}