글 읽기 - 세그트리로 푸는건 알겠는데 어떤식으로 해야할지 감이안잡힙니다ㅠ!

sgc109 7년 전 1

처음엔 숫자들의 맨처음 위치를 저장하고있는 배열을 선언하고

i번째 위치에있던 숫자가 움직인 횟수(오른쪽으로움직였으면 +, 왼쪽으로움직였으면 -) 를 저장하는 세그트리를 이용하여

이동시켜야하는 숫자들을 차례대로 abs(이동해야할곳 - 현재위치) 를 출력하면서

이동해야할곳이 현재위치보다 왼쪽에 있다면 이동해야할곳~현재위치-1 에 원래 있던 원소들이 오른쪽으로 한칸씩이동하므로

lazy propogation 을 사용하여 이동해야할곳~현재위치-1을 +1 시켜줬고

반대로 이동해야할곳이 현재위치보다 오른쪽에 있다면 현재위치+1~이동해야할곳 을 -1 시켜줬고,

중요한것은 어떤 숫자를 옮겨야하는 순간에 그 숫자가 있는 위치를 알아야하고, (위치만알면 옮겨야할곳은 이미 알고있기때문에 이동거리는

계산할수가있기때문에) 또 그 숫자가 있는 위치부터 옮겨야할 위치 사이에 존재하여 위치가 변동되는 숫자들의 위치 변동을 적절히 업데이트

해주어야 한다는 것을 깨달았는데, 알고보니 제가 구현한 코드에서 가장큰 오류는 원소들이 고정적이지않고 이동한다는 사실이었습니다..

저는 특정위치에서 원소의 이동이 어느방향으로 몇번 있느냐를 계산해놓고 이값과 맨 처음원소의 위치를 더하면 변한 위치가 계산될거라고 생각했었는데 예제 출력이 잘못나오는걸보고 자세히보니 원소가 계속이동하고 원소가 이동하고나면 옆 위치에서의 이동기록?에 따라야하기때문이었습니다..

아무튼 이러한 시행착오끝에 다른 풀이를 생각해봤는데 도저히 감이 안와서 질문드립니다. 힌트라도 주시면감사하겠습니다

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <set>
#include <cmath>
// #include <unordered_set>
// #include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)

using namespace std;

typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > piii;

const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 100003;

vi rangeMove;
vi lazy;
int firstPos[MAX_N];
int n;
int size;

int query(int nodeLeft, int nodeRight, int node, int pos) {
	if(lazy[node] != 0) {
		if(nodeLeft == nodeRight) {
			rangeMove[node] += lazy[node];
		}
		else {
			lazy[2*node] = lazy[node];
			lazy[2*node+1] = lazy[node];
		}
		lazy[node] = 0;
	}

	if(nodeRight < pos || pos < nodeLeft) return INF;
	if(nodeLeft == nodeRight && nodeRight == pos) return rangeMove[node];

	int nodeMid = (nodeRight + nodeLeft) >> 1;

	int leftRange = query(nodeLeft, nodeMid, 2*node, pos);
	int rightRange = query(nodeMid+1, nodeRight, 2*node+1, pos);

	return (leftRange == INF ? rightRange : leftRange);
}

void update(int nodeLeft, int nodeRight, int left, int right, int node, int val) {
	if(lazy[node] != 0) {
		if(nodeLeft == nodeRight) {
			rangeMove[node] += lazy[node];
		}
		else {
			lazy[2*node] = lazy[node];
			lazy[2*node+1] = lazy[node];
		}
		lazy[node] = 0;
	}

	if(left <= nodeLeft && nodeRight <= right) {
		lazy[node] += val;
		return;
	}
	if(right < nodeLeft || nodeRight < left) return;

	int nodeMid = (nodeLeft + nodeRight) >> 1;

	update(nodeLeft, nodeMid, left, right, 2*node, val);
	update(nodeMid+1, nodeRight, left, right, 2*node+1, val);
}

int query(int pos) {
	return query(0,size-1,1,pos);
}

void update(int left, int right, int val) {
	update(0,size-1,left,right,1,val);
}

int main() {
	inp1(n);
	FOR(i,n) {
		int tmp;
		inp1(tmp);
		firstPos[tmp]=i+1;
	}

	size = n+1;

	rangeMove.resize(4*size);
	lazy.resize(4*size);

	int a = 1;
	FOR(i,n) {
		int curPos = firstPos[a] + query(firstPos[a]);
		if(a <= n/2) {
			printf("%d\n",curPos-a);
			if(curPos != a) update(a,curPos-1,1);
			a = n-a+1;
		}
		else {
			printf("%d\n",a-curPos);
			if(curPos != a) update(curPos+1,a,-1);
			a = n-a+2;
		}
	}
	return 0;
}

yukariko 7년 전 6

어렵게 생각하지 않아도 될것 같습니다.

현재 보고 있는 숫자를 n이라고 하죠.

n의 위치는 firstPos 배열에 담겨있기 때문에 바로 알 수 있습니다. 이 위치를 x라고 합시다.

만약 n이 가장 처음인 1이었다면, 쉽게 생각해서 왼쪽으로 x-1 만큼 움직이면 됩니다.

그런데 1이 아닌 경우는 이전의 이동에 의해 사라진 숫자가 존재하겠죠.

만약 0과 x-1 사이에 사라진 숫자가 y개 존재한다면, y개만큼은 제외하고 움직여야 합니다.

따라서 x - 1 - y만큼 움직이면 됩니다.

오른쪽인 경우도 이렇게 구할 수 있습니다.

문제는 y를 어떻게 구하는가 인데

이것은 sum 세그트리를 이용하면 쉽게 구할 수 있습니다.

왼쪽의 경우는 [0, x) 범위의 부분합을 구하면 되겠죠.

@yukariko 감사합니다! 이해가 되었습니다. 그니까 현재 보고있는 숫자를 무조건 맨끝(왼쪽or오른쪽) 으로 보낸다고 생각하면 되겠군요. 대신 이전에 미리 사라진 숫자들은 이미 끝에 붙어있어서 감안할 필요가없고 넘어갈필요가없으니 그만큼 빼주는거고.. 도대체 이런 생각이 어떻게 어렵게 생각하지않는게 될수가있나요 ㅠㅠ 하 세그트리 너무어렵네요.. 감사합니다!

joonas 3년 전 0

와 머지소트트리+이분탐색으로 비비고 있었는데 이렇게 간단하다니... 뚝배기 맞고 갑니다 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

세그트리로 푸는건 알겠는데 어떤식으로 해야할지 감이안잡힙니다ㅠ!

sgc109 7년 전 1

yukariko 7년 전 6

sgc109 7년 전 0

joonas 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말