백준 17373번 녜힁

문제 요약

N개의 1이상 M이하의 정수가 주어진다.

1이상 M이하의 정수 중에서 두 숫자를 뽑아서 나열하려고 하는데 이 때, 나열할 수 없는 경우가 존재한다. N개의 주어진 수 중에서 어떤 숫자 x가 어떤 숫자 y보다 앞에 위치한다면 x y는 나열이 불가능한 경우이다.

쿼리로 숫자 K가 주어지는데 이런 식으로 나열이 가능한 경우들 중에서 사전순으로 K번째의 경우를 출력해야 한다. 만약 나열 가능한 경우의 수가 K보다 작다면 -1 -1을 출력하도록 한다.

 

제목이 녜힁이다. 녜힁~

풀이

두 글자로 이루어져 있으니 먼저 첫 글자에 집중해보자.

어떤 숫자 x를 첫 글자로 사용한다고 했을 때, x의 뒤에 올 수 있는 숫자의 가짓수는 $O(N)$에 구하는 것이 가능하다.

 

start_num[i] : i가 처음 등장하는 위치, 등장하지 않으면 -1

end_num[i] : i가 마지막으로 등장하는 위치, 등장하지 않으면 -1

back_num[i] : i가 첫 글자에 올 경우 뒤에 올 수 있는 숫자의 가짓수

 

back_num[i]는 i가 등장하지 않았다면 M이고 아니라면 start_num[i]보다 end_num[j]가 작은 j의 개수가 될 것이다.

back_num[i]를 전부 구했으면 1부터 M까지의 순서대로 back_num[i]의 누적합 배열 p를 만들어줄 수 있다.

나열할 수 있는 총 경우의 수를 구할 수 있고, K가 들어왔을 때 앞 숫자가 어떤 숫자가 되어야 하는지는 이분 탐색으로 구할 수 있다.

 

이제 뒷글자로 어떤 수가 와야할 지를 결정해야 하는데 trivial한 경우는 back_num[i]가 M이라서 모든 수가 올 수 있는 경우이다. 이 경우는 그냥 K에다가 p[i]를 빼준 값을 출력하면 된다.

 

이제 M이 아닌 경우들을 따져보자. $segtree_i$를 i를 첫 숫자로 선택했을 때, 뒤에 올 수 있는 수들의 위치에 1이 켜져있는 세그먼트 트리로 생각해보자. 그러면 이 세그트리에서 K-p[i]번째 원소를 찾으면 우리가 원하는 값이 될 것이다.

 

i를 end_num[i]가 작은 순서대로 정렬했을 때, back_num[i]들을 살펴보면 1, 1, 1, 2, 2, 2, 3, 3, ..., k, k, k+1, k+1 처럼 특정 숫자들이 반복되다가 커지고 반복되다가 커지고 하는 계단식의 형태를 가진 배열이 될 것이다.

그리고 가짓수만 같은게 아니라 올 수 있는 수들의 종류 또한 같다. 이는 $start\_num[j] \le end\_num[i]$인 j가 뒤에 올 수 있는 수들이기 때문이다.

 

그래서 end_num[i] 기준으로 i를 정렬했을 때 $segtree_i$들을 같은 상태이다가 back_num[i]가 커지는 순간 업데이트가 진행된다는 것이다.

이 점을 이용하면 모든 $segtree_i$를 PST로 관리가 가능하다.

따라서, 문제를 $O((N+Q)logN)$에 해결이 가능하다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MXN = 1e5;
const int MXM = 1e6;
ll psum[MXM+5], a[100005];
int start_num[MXM+5], end_num[MXM+5];
ll back_num[MXM+5];
vector<int> roots(MXM+5);
vector<int> v;
int N, M, Q;

struct Node {
    int l, r, val;
    Node() : val(0) {};
};

vector<Node> tree(40*MXM);

int node_cnt;

void init() {
    node_cnt = 2*M;
    for(int i=1;i<M;++i) {
        tree[i].l = i << 1;
        tree[i].r = i << 1 | 1;
    }
}

void update(int node, int s, int e, int idx, int val) {
    tree[node].val += val;
    if(s != e) {
        int mid = s+e >> 1;
        int n1 = tree[node].l, n2 = tree[node].r;
        if(idx <= mid) {
            tree[node].l = node_cnt;
            tree[node_cnt++] = tree[n1];
            update(tree[node].l, s, mid, idx, val);
        }
        else {
            tree[node].r = node_cnt;
            tree[node_cnt++] = tree[n2];
            update(tree[node].r, mid+1, e, idx, val);
        }
    }
}

int query(int node, int k) {
    int l = 1, r = M;
    while(l != r) {
        int mid = l+r >> 1;
        int lsz = tree[tree[node].l].val;
        if(lsz >= k) {
            node = tree[node].l;
            r = mid;
        }
        else {
            node = tree[node].r;
            l = mid + 1;
            k -= lsz;
        }
    }
    assert(l == r);
    return l;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    for(int i=1;i<=N;++i) cin >> a[i];
    memset(start_num, -1, sizeof(start_num));
    memset(end_num, -1, sizeof(end_num));
    for(int i=1;i<=N;++i) {
        if(start_num[a[i]] == -1) {
            start_num[a[i]] = i;
            v.push_back(a[i]);
        }
        end_num[a[i]] = i;
    }
    vector<bool> vis(MXM+5, true);
    vector<int> tmp(MXN+5, 0);
    int cnt = M;
    for(int i=N;i>0;--i) {
        tmp[i] = cnt;
        if(vis[a[i]]) {
            vis[a[i]] = false; --cnt;
        }
    }
    ll total_sum = 0;
    for(int i=1;i<=M;++i) {
        if(start_num[i] == -1) back_num[i] = M;
        else back_num[i] = tmp[start_num[i]];
        total_sum += back_num[i];
    }
    for(int i=1;i<=M;++i) psum[i] = psum[i-1] + back_num[i];
    vector<pair<int,int>> p;
    for(int i=1;i<=M;++i) p.emplace_back(i, end_num[i]);
    sort(p.begin(), p.end(), [] (pair<int,int> &a, pair<int,int> &b) { return a.second < b.second; });
    init();
    roots[0] = 1;
    int idx = 0;
    int cur_root = 1;
    for(int &i:v) {
        while(idx < p.size() && p[idx].second <= start_num[i]) {
            tree[node_cnt] = tree[cur_root];
            cur_root = node_cnt++;
            update(cur_root, 1, M, p[idx++].first, 1);
        }
        roots[i] = cur_root;
    }
    for(int i=0;i<Q;++i) {
        ll k; cin >> k;
        if(total_sum < k) cout << "-1 -1" << '\n';
        else {
            int idx = lower_bound(psum, psum+M+1, k) - psum - 1;
            k -= psum[idx]; ++idx;
            if(back_num[idx] == M) cout << idx << ' ' << k << '\n';
            else {
                cout << idx << ' ' << query(roots[idx], k) << '\n';
            }
        }
    }
    return 0;
}