블로그 옮겼습니다

Codeforces Round #424 (Div. 2) E. Cards Sorting 본문

Algorithm/Problem Solving

Codeforces Round #424 (Div. 2) E. Cards Sorting

sgc109 2017. 7. 30. 17:00
http://codeforces.com/contest/831/problem/E


N <= 10^5

N개의 카드가 쌓여있다. 각 카드에는 숫자가 쓰여져있다. 두 장 이상의 카드에 같은 수가 적혀있을 수도 있다.

그리고 아래의 operation 을 한다.

만약 카드 덱의 맨 위에 있는 카드에 적힌 숫자가 현재 덱에 남아있는 카드들에 적힌 숫자들중 가장 작은 수이면

그 카드를 빼버리고 아니라면 덱의 맨 아래로 옮긴다. 이 과정을 반복하여 카드를 모두 빼버릴 때까지 반복한다.

이 때 카드를 모두 빼버릴 때까지 수행되는 operation 의 수를 구하는 문제이다.


우선 2장 이상의 카드에 같은 숫자가 적혀있지 않은 경우에 대해 먼저 생각해 보자.

이렇게 할 수가 있다. 어차피 작은 수부터 빼낼 수 있으니 적혀있는 숫자들을 모두 정렬하고

(숫자 중간 중간이 비어있을 수도 있으므로 깔끔하게 하기 위해 좌표압축 해도된다.

하지만 숫자의 범위가 10만이하이므로 필수는 아니다.)

작은 숫자부터 빼내보자. 

그리고 카드를 실제로 맨위에서 맨아래로 옮기는 것이 아니라 맨 처음 상태 그대로 두고

맨위에 있는 카드를 기리키는 포인터를 하나 두자. 만약 현재 카드를 아래로 보낸다면 

포인터를 아래로 한칸 옮기는 것으로 대체할 수 있고 포인터가 맨 아래에 도달했을 경우엔

다시 맨위로 옮겨주면 된다. 이렇게 했을 때 현재 포인터의 위치를 pos 라고 하겠다.

pos는 직전 숫자 카드를 제거하고 난 직후의 위치라고 보면된다.

그럼 pos 에서 다음 숫자 카드의 위치 사이에 존재하는 모든 카드를 아래로 보내야하므로

(아래로 보내는건 곧 포인터가 그냥 카드를 지나치는것과 같다)

그 사이에 존재하는 카드의 수를 답에 누적하고 pos 를 다음에 빼야할 숫자를 가진

카드의 위치로 옮겨주는 동시에 이 숫자를 가진 카드를 뺐다고 표시해준다.

이것을 가장 큰 수 까지 반복하면 되는데

아까 말했던 현재 pos와 다음으로 큰 수가 적혀있는 카드의 위치 사이에 존재하는 카드의 수를

O(N) 보다 빠르게 구할 수있다면 O(N^2) 보다 빠르게 문제를 해결할 수 있을 것이다.

그럼 어떻게 할까? 바로 펜윅 트리이다. 구간의 합을 O(lgN) 에 구할 수 있기 때문에

카드가 있으면 1 없으면 0 으로 표시해주면된다. 카드를 뺄 땐 -1만큼 업데이트 시켜주면 된다.

만약 다음 숫자 카드의 위치가 pos 보다 작다면 pos 부터 N까지 쿼리를 날리고

0부터 숫자 카드의 위치까지 쿼리를 날려서 더해주면 된다.


그럼 이제 같은 숫자가 적힌 카드가 2장이상 존재 가능할 때를 생각해 보자.

아까는 다음 숫자카드가 한장 뿐이기 때문에 다음으로 큰 숫자가 적힌 카드가

딱 한장만 존재했고, 그래서 이 위치를 next 라고 한다면 pos 부터 next 사이까지만

쿼리를 날리고 update 도 딱 하나의 인덱스에 대해서만 수행하면 되었다.

이제는 next 가 하나가 아니기 때문에 케이스를 나눠야한다. (next 들이 정렬 되어있다고 가정하자)

(숫자 k 가 적힌 카드들중 가장 앞에 있는 카드를 front[k], 끝에 있는 카드를 last[k] 라고하자)

1. last[k] < pos 인 경우

2. pos < front[k] 인 경우

3. front[k] < pos < last[k] 인 경우

(조금만 생각해 보면 last[k], front[k] 와 pos 는 같을 수 없다는 것을 알 수 있다.

pos 는 이전에 뺀 카드중 하나의 위치이기 때문이다.)


1번의 경우엔 pos 에서 N까지 쿼리를 날리고, 1에서 last[k] 까지 쿼리를 날려서 더해주면 된다.

물론 모든 nexts 들에 대해 -1 만큼 업데이트는 필수. k가 적힌 마지막으로 빠지는 카드의 위치는

last[k] 이므로 pos를 last[k] 로 갱신해준다.


2번의 경우엔 pos 에서 last[k] 까지 쿼리를 날리면된다. 업데이트는 필수. pos 는 last[k]로 갱신


3번의 경우엔 pos 에서 N 까지 쿼리를 날리고, 1에서 nexts 들의 위치들에 pos로 lower_bound 한

위치 까지 쿼리를 날리면 될 것이다. 그 이후는 이미 처음 쿼리에서 감안했기 때문.

업데이트는 역시 필수, pos 는 그 lower_bound 한 곳으로 갱신.


결국 같은 숫자가 쓰여진 카드가 한장 밖에 없을 때와 다른 점은 두가지 이다.


1. 다음 pos 위치의 후보가 하나에서 여러개로 늘어났고 후보중 하나를 정해야하고

이 위치까지 쿼리를 날려야 하므로 쿼리 날리는 부분도 살짝 달라진다.

2. BIT의 업데이트를 그 숫자가 적힌 카드가 있는 모든 인덱스에 대해 한다.


가장 중요한 실마리가 되는 아이디어는 카드를 실제로 맨 아래로 옮기는 것이 아니라 포인터를 두고

포인터만 아래로 이동시키는 것 이라고 생각한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
set<int> st;
vector<int> nums;
vector<int> idxs[100003];
int N, a;
int t[800003];
void update(int x, int v){
    while(x <= N){
        t[x] += v;
        x += x & -x;
    }
}
int query(int x){
    int ret = 0;
    while(x > 0){
        ret += t[x];
        x -= x & -x;
    }
    return ret;
}
int main() {
    fastio();
    cin >> N;
    for(int i = 1 ; i <= N; i++){
        cin >> a;
        idxs[a].push_back(i);
        st.insert(a);
        update(i, 1);
    }
    int pos = 0;
    ll ans = 0;
    nums.assign(all(st));
    for(int i = 0 ; i < sz(nums); i++){
        int cur = nums[i];
        int f = idxs[cur].front();
        int b = idxs[cur].back();
        if(f < pos && pos < b) {
            int p = lower_bound(all(idxs[cur]), pos) - idxs[cur].begin();
            ans += query(N) - query(pos) + query(idxs[cur][p - 1]);
            pos = idxs[cur][p - 1];
        }
        else if(pos <= f) {
            ans += query(b) - query(pos);
            pos = b;
        }
        else {
            ans += query(b) + query(N) - query(pos);
            pos = b;
        }
        for(int e : idxs[cur]) update(e, -1);
    }
 
    cout << ans << "\n";
    
    return 0;
}
cs


Comments