Edu 80. Div2 E - 수열의 x번째 수를 꺼내서 계속 앞으로 가져다 놓기.

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

Problem - E - Codeforces

 

[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의 인덱스를 표현해야 한다.

 

 

#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+1, 0);
    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+1, 1);
        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;
}

 

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

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

3653번: 영화 수집