본문으로 바로가기

https://codeforces.com/contest/1288/problem/E

 

Problem - E - Codeforces

 

codeforces.com

 

[1 2 3 4 5] 라는 수열이 있을 때

3이라고 입력하면

[3 1 2 4 5]를 만들고

여기서 4라고 입력하면

[4 3 1 2 5]를 만들려고 한다.

 

이 때 각 숫자마다 숫자가 존재했던 위치의 max값을 구하는 문제다.

 

 

segtree나 fenwick을 이용하는 전형적인 문제.

 

x의 suffix sum이 현재 x보다 앞에 있는 숫자들의 개수를 알려준다고 하면

suffix sum은 fenwick이나 segtree등으로 쉽게 구할 수 있다.

다만 x의 suffix sum을 구하고 난 다음 이 x라는 숫자를 맨 앞으로 가져가야 하는데,

이를 위해 x를 제외한 나머지 숫자들을 오른쪽으로 한칸씩 움직이면 답이 없다.

그래서 애초에 suffix sum을 구하는 방을 n+m+1개만큼 만들고

[m+1, n+m] 구간부터 사용한다.

처음 x라는 숫자가 맨 앞으로 이동한다면,

1. query(m+x)로 max를 업데이트

2. update(m+x, -1)로 x위치를 없애주고

3. update(m+1 -1, 1)로 맨 앞에 위치하게될 x를 표현해준다.

물론 x의 위치가 계속 변하기 때문에 lastPos같은 배열을 만들어서 마지막으로 x가 저장된 fenwick tree의 인덱스를 표현해야 한다.

 

 

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
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int,int> pii;
int n,m;
vector<int> fen,a;
pii ans[300001];
int lastPos[300001];
void update(int at, int by) {
    for(; at<=n+m; at+=at&-at) fen[at] += by;
}
int query(int at) {
    int ret = 0;
    for(; at>0; at-=at&-at) ret += fen[at];
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    fen.clear(); fen.resize(n+m+10);
    for(int i=1; i<=n; i++) {
        update(m+i,1);
        lastPos[i] = m+i;
        ans[i].first = i;
    }
    for(int i=1; i<=m; i++) {
        int x; cin >> x;
        a.push_back(x);
 
        ans[x].first = 1;
        ans[x].second = max(ans[x].second, query(lastPos[x]));
        update(lastPos[x],-1);
        update(m-i+11);
        lastPos[x] = m-i+1;
    }
    for(int i=1; i<=n; i++) {
        ans[i].second = max(ans[i].second, query(lastPos[i]));
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
 
    return 0;
}
cs

 

이와 유사한 문제로는 BOJ 3653이 있다.

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

 

3653번: 영화 수집

문제 상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다. 보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다. 상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫

www.acmicpc.net