[BOJ] 1849. 순열

문제

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

1849번: 순열

 

풀이

세그먼트 트리를 1로 모두 채운 다음, 숫자의 입력을 쿼리라고 생각하자.

 

i번째 쿼리로 x가 들어왔을 경우, 현재 prefix sum이 x+1인 점중 가장 작은 점을 찾아서 그 칸을 채우면 된다. 

예를 들어서 $n=8$인 경우 첫번째 쿼리로 5가 들어온 경우 현재 세그먼트 트리는 다음과 같이 구성된다.

 

8
4				4
2		2		2		2
1	1	1	1	1	1	1	1
(<--------------------이 부분의 prefix sum이 5이므로---------------------->)					이 칸에 추가.

 

7
4				3
2		2		1		2
1	1	1	1	1	0	1	1

그 후 다음과 같이 segment tree를 업데이트 해준다.

 

이 때, 저 prefix sum이 5가 되는 부분을 찾아야 하는데, 이는 거꾸로 segment tree의 꼭대기 부터 내려오면서 찾을 수 있다.

만약 left child의 sum이 v보다 작거나 같다면 원하는 index는 오른쪽 자식에 있으며, left child의 sum이 v보다 크다면 원하는 index는 왼쪽 자식에 있다.

이러한 방법으로 leaf node까지 도착하면, 도착한 노드에 원하는 숫자를 추가해주면 된다.

 

이 방법으로 쿼리마다, node를 찾는데 $O(log n)$, 세그먼트 트리를 업데이트 해주는데 $O(log n)$이 걸린다.

따라서 총 시간복잡도는 $O(n+qlogn)$이다.

 

Time Complexity : $O(n+qlogn)$

 

코드

#include<iostream>
#include<vector>
#define lc(i) ((i)<<1)
#define rc(i) ((i)<<1|1)

using namespace std;

int seg[1<<18];
int n,p;
vector<int> ans;
void update(int t)
{
	t+=p;
	while(t!=1)
	{
		t>>=1;
		seg[t] = seg[lc(t)]+seg[rc(t)];
	}
}
int loc(int t)
{
	int r=1;
	while(r<p)
	{
		if(t>=seg[lc(r)])
		{
			t-=seg[lc(r)];
			r=rc(r);
		}
		else r=lc(r);
	}
	return r-p;
}
int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);
	cin>>n;

	ans.resize(n);
	for(p=n;p^(-p&p);p+=(-p&p));
	for(int i=p;i<p+n;i++) seg[i]=1;
	for(int i=p-1;i>0;i--) seg[i]= seg[i<<1]+seg[i<<1|1];

	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int l=loc(x);
		seg[p+l]=0;
		ans[l]=i;
		update(l);
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<" ";
}