[백준]Random Generator(19646)

문제 링크 : [백준]Random Generator(19646)

19646번: Random Generator

문제 설명

1부터 N까지의 수를 순서대로 W_i개씩 나열합니다.

N번을 반복하며 P_i번째 있는 수를 출력하고, 출력한 수를 모두 지웁니다.

입력

N(출력할 수의 갯수, 1 <= N <= 200,000)

W_i(수 i를 나열할 갯수, 1 <= W_i <= 1,000)

Pi(Pi번째 수를 출력)

5
1 2 3 4 5
6 4 6 1 2

 

출력

3 4 5 1 2

 

카테고리

#세그먼트트리

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. Pi번째에 있는 수를 출력하고, 그 수를 모두 지우는 연산을 반복해야합니다.
2. 조회와 업데이트가 빈번히 일어나면서, 특정 구간에 대한 구간합을 구해야 하는 문제입니다.
3. 세그먼트 트리를 이용하여 구할 수 있을 것 같습니다.
4. 각 숫자를 인덱스로 활용하여, 갯수들의 구간합을 구해줍니다.
5. 루트에서 시작하여, 왼쪽 자식의 값이 P_i보다 크거나 같으면, P_i번째 숫자는 왼쪽 구간에 있습니다.
6. 반대로 왼쪽 자식의 값이 P_i보다 작으면, P_i번째 숫자는 오른쪽 구간에 있습니다.
7. 단, 왼쪽 자식의 값 만큼은 왼쪽 구간에 있으니, 그 숫자를 제외한 만큼을 오른쪽 구간에서 찾아야합니다.
8. 이렇게 P_i번째 숫자를 구하여 출력 한 후, 그 인덱스의 값을 0으로 업데이트하여, 그 숫자를 삭제해줍니다.

시간복잡도

O(NlogN)

코드

#include<iostream>
#define N 200001
using namespace std;
int n,d[N*4],e[N],i,x;
int in(int p,int l,int r){
    if(l==r)return d[p]=e[l];
    return d[p]=in(p*2,l,(l+r)/2)+in(p*2+1,(l+r)/2+1,r);
}
int f(int p,int l,int r,int v){
    if(l==r)return l;
    if(d[p*2]<v)return f(p*2+1,(l+r)/2+1,r,v-d[p*2]);
    return f(p*2,l,(l+r)/2,v);
}
int u(int p,int l,int r,int x){
    if(x<l||r<x)return d[p];
    if(l==r)return d[p]=0;
    return d[p]=u(p*2,l,(l+r)/2,x)+u(p*2+1,(l+r)/2+1,r,x);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>e[i];
    in(1,1,n);
    for(i=0;i<n;i++){
        cin>>x;
        x=f(1,1,n,x);
        cout<<x<<" ";
        u(1,1,n,x);
    }
}