[백준] 순열복원(1777)

문제 링크 : [백준] 순열복원(1777)

문제 설명

1부터 n까지의 수로 이루어진 순열이 있을 때, i보다 오른쪽에 있는 숫자 중 i 보다 작은 원소의 갯수들이 주어집니다.
예시
원래 순열 : 2 4 5 1 7 6 3 8
주어지는 수 : 0 1 0 2 2 1 2 0
7(5번째 원소)보다 오른쪽에 있으면서 7보다 작은 수는 두 개(6, 3)이기 때문에 2가 주어집니다.
위와 같은 값들이 주어졌을 때, 원래 순열을 구하십시요.

입력

N(순열의 크기, 1<=N<=100,000)
D_i(i보다 오른쪽에 있는 수 중에서 D_i보다 작은 수의 갯 수)

8
0 1 0 2 2 1 2 0

출력

원래 순열

2 4 5 1 7 6 3 8

카테고리

#펜윅트리, #세그먼트트리, #이분탐색

시간 복잡도 상한

O(NlogN)까지 가능합니다.

해결 방법

• i보다 오른쪽에 있으면서 i보다 작은 수의 갯수는 주어진 데이터를 보면 알 수 있습니다.

시간복잡도

O(N(logN)²)

코드

#include<cstdio>
int n,i,d[100001],t[400000],l,r,m,v,a[100001];
int u(int p,int l,int r,int i){
    if(i>r||i<l)return t[p];
    if(l==r)return t[p]^=1;
    return t[p]=u(p*2,l,(l+r)/2,i)+u(p*2+1,(l+r)/2+1,r,i);
}
int q(int p,int l,int r,int x,int y){
    if(y<l||x>r)return 0;
    if(x<=l&&r<=y)return t[p];
    return q(p*2,l,(l+r)/2,x,y)+q(p*2+1,(l+r)/2+1,r,x,y);
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",d+i),u(1,1,n,i);
    for(i=n;i;i--){
        l=1;r=n;
        while(l<=r){
            m=(l+r)/2;
            v=q(1,1,n,m,n)-1;
            if(v>d[i])l=m+1;
            else r=m-1;
        }
        a[l]=i;
        u(1,1,n,r);
    }
    for(i=1;i<=n;i++)printf("%d ",a[i]);
}