BOJ 13546 : 수열과 쿼리 4

알고리즘 문제 전체 링크

 

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

 

참고

- BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition)

- 머지 소트 Merge Sort

- BOJ 13547 : 수열과 쿼리 5

- BOJ 10866 : 덱 with Linked List

 

 

수열과 쿼리 5에서 사용한 방법으로 문제를 푼다.

여기서는 주어진 구간 [left, right]에서 값이 같은 원소의 index의 차이를 구한다.

---

제곱근 분할법으로 원소의 길이 저장하기

 

[left, right]를 Mo's로 한 칸씩 움직이면서 각 원소마다 가장 긴 길이를 갱신하면 된다.

 

예를 들어 5번 원소가 7번 구간에 존재하고, 이 원소가 추가된다면, 5번 덱에 index = 7을 추가한다.

이때, left에서 추가하면 덱에 앞에 추가하고, right에서 추가된다면 덱의 뒤에 원소를 추가한다.

그러면 덱의 back에 저장된 값과 덱의 front에 저장된 값을 빼면 구해야 할 |x - y|를 알 수 있다.

 

하지만 모든 원소에 대해서 가장 긴 값을 구해야하므로, 모든 원소를 뒤져보아야 한다.

이때 제곱근 분할법으로 효율적으로 답을 찾을 수 있다.

 

만약 [1, 100] 구간에 5번 원소가 6와 95에 존재한다면, maxLength[95 - 6]++을 한다.

마찬가지로 구간 [a, b]에 포함되는 c와 d에 어떤 원소가 존재한다면, maxLength[d - c]++을 한다.

그러면 maxLength[100]부터 거꾸로 검사해서 0이 아닌 값이 나온다면 그 값이 최대값이다.

 

index의 차이는 100,000이 되므로 100,000번 부터 거꾸로 뒤져보는 것은 비효율적이다.

따라서 maxLengthBucket[length / SQRT]++을 해서, maxLengthBucket부터 검사하고,

Bucket에 존재하면 maxLength를 검사한다.

#define MAX (100000 + 100)
#define SQRT (316)
#define SIZE (MAX / SQRT + 1)

int maxLength[MAX + 1000];
int maxLengthBucket[SIZE];

int findMaxLength()
{
	for (int i = SIZE - 1; i >= 0; i--)
	{
		if (maxLengthBucket[i] == 0) continue;

		for (int k = SQRT - 1; k >= 0; k--)
		{
			
			if (maxLength[i * SQRT + k] > 0)
			{
				return i * SQRT + k;
			}
		}
	}

	return 0;
}

i * SQRT + k가 maxLength 배열의 크기보다 클 수 있으므로 MAX + 1000으로 적절히 넉넉하게 잡았다.

---

덱

 

덱의 경우는 동적으로 증가시켜야 하므로 링크드 리스트를 이용하여 구현한다.

코드는 BOJ 10866 : 덱 with Linked List 또는 아래 전체 코드를 참고한다.

이때, 구간의 변경이 자주 있다면 메모리의 낭비가 심해진다.

따라서 front의 prev나 back의 next가 존재한다면, 이전에 pop이 되면서 node가 남아있다는 뜻이므로

해당 노드를 재사용하도록 코드를 수정한다.

void push_front(int head, int value)
{
	dequeSize[head]++;

	DEQUE* node;
	if (front[head]->prev == NULL) node = &POOL[pcnt++];
	else node = front[head]->prev;
	
	node->value = value;

	node->next = front[head];
	front[head]->prev = node;

	front[head] = node;
}

 

pop의 경우 deque이 터지는 경우가 없으므로 성능을 위해 if문 검사는 생략하였다.

int pop_front(int head)
{
	//if (dequeSize[head] == 0) return -1;

	dequeSize[head]--;

	int ret = front[head]->value;

	front[head] = front[head]->next;

	return ret;
}

 

Mo's 알고리즘을 실행할 때,

덱의 front와 back이 역전되지 않도록 구간은 push를 먼저 실행하고, 나중에 pop을 실행해야 한다.

(수열과 쿼리 5와 달리 순서가 중요하다.)

for (int i = 0; i < M; i++)
{
	while (right < query[i].right) rightPush(++right);
	while (left > query[i].left) leftPush(--left);

	while (right > query[i].right) rightPop(right--);
	while (left < query[i].left) leftPop(left++);
	
	answer[query[i].index] = findMaxLength();
}

---

max index 갱신

 

left의 구간이 증가하여 원소를 빼는 경우를 보자.

이때 주어진 원소 head = A[left]는 빠지게 된다.

이 원소의 가장 긴 길이는 back과 front에 저장된 index의 차이므로, maxLength와 Bucket에 값을 감소한다.

그리고 pop을 한 후, 갱신된 덱에서 maxLength를 증가시킨다.

덱에 값이 없다면 할 필요 없으므로 예외처리한다.

void leftPop(int left)
{
	int length;
	int head = A[left];

	length = back[head]->prev->value - front[head]->value;
	maxLength[length]--;
	maxLengthBucket[length / SQRT]--;

	pop_front(head);

	if (dequeSize[head] != 0)
	{
		length = back[head]->prev->value - front[head]->value;
		maxLength[length]++;
		maxLengthBucket[length / SQRT]++;
	}
}

 

leftPush, rightPush, rightPop도 같은 방식으로 만든다.

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (100000 + 100)
#define SQRT (316)
#define SIZE (MAX / SQRT + 1)

int N, K, M;
int A[MAX];

int maxLength[MAX + 1000];
int maxLengthBucket[SIZE];
int answer[MAX];

typedef struct st1
{
	int index;
	int left;
	int right;
}QUERY;

QUERY query[MAX];

#pragma region merge sort
QUERY b[MAX];

int isMin(QUERY a, QUERY b)
{
	if (a.left / SQRT < b.left / SQRT) return 1;
	else if (a.left / SQRT == b.left / SQRT && a.right < b.right) return 1;

	return 0;
}

void merge(QUERY* a, int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (isMin(a[i], a[j])) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end; i++)
		a[i] = b[i - start];
}

void sort(QUERY* a, int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;
	sort(a, start, mid);
	sort(a, mid + 1, end);
	merge(a, start, end);
}
#pragma endregion

#pragma region deque
typedef struct st2
{
	int value;
	struct st2* next;
	struct st2* prev;
}DEQUE;

DEQUE deque[MAX];
DEQUE* front[MAX];
DEQUE* back[MAX];
DEQUE POOL[MAX * 10];
int pcnt;

int dequeSize[MAX];

void push_front(int head, int value)
{
	dequeSize[head]++;

	DEQUE* node;
	if (front[head]->prev == NULL) node = &POOL[pcnt++];
	else node = front[head]->prev;
	
	node->value = value;

	node->next = front[head];
	front[head]->prev = node;

	front[head] = node;
}

void push_back(int head, int value)
{
	dequeSize[head]++;

	DEQUE* node;
	if (back[head]->next == NULL) node = &POOL[pcnt++];
	else node = back[head]->next;

	back[head]->value = value;

	node->prev = back[head];
	back[head]->next = node;

	back[head] = node;
}

int pop_front(int head)
{
	//if (dequeSize[head] == 0) return -1;

	dequeSize[head]--;

	int ret = front[head]->value;

	front[head] = front[head]->next;

	return ret;
}

int pop_back(int head)
{
	//if (dequeSize[head] == 0) return -1;

	dequeSize[head]--;

	int ret = back[head]->prev->value;

	back[head] = back[head]->prev;

	return ret;
}

#pragma endregion

void leftPop(int left)
{
	int length;
	int head = A[left];

	length = back[head]->prev->value - front[head]->value;
	maxLength[length]--;
	maxLengthBucket[length / SQRT]--;

	pop_front(head);

	if (dequeSize[head] != 0)
	{
		length = back[head]->prev->value - front[head]->value;
		maxLength[length]++;
		maxLengthBucket[length / SQRT]++;
	}
}

void leftPush(int left)
{
	int length;
	int head = A[left];

	if (dequeSize[head] != 0)
	{
		length = back[head]->prev->value - front[head]->value;
		maxLength[length]--;
		maxLengthBucket[length / SQRT]--;
	}

	push_front(head, left);

	length = back[head]->prev->value - front[head]->value;
	maxLength[length]++;
	maxLengthBucket[length / SQRT]++;
}

void rightPush(int right)
{
	int length;
	int head = A[right];

	if (dequeSize[head] != 0)
	{
		length = back[head]->prev->value - front[head]->value;
		maxLength[length]--;
		maxLengthBucket[length / SQRT]--;
	}

	push_back(head, right);

	length = back[head]->prev->value - front[head]->value;
	maxLength[length]++;
	maxLengthBucket[length / SQRT]++;
}

void rightPop(int right)
{
	int length;
	int head = A[right];

	length = back[head]->prev->value - front[head]->value;
	maxLength[length]--;
	maxLengthBucket[length / SQRT]--;

	pop_back(head);

	if (dequeSize[head] != 0)
	{
		length = back[head]->prev->value - front[head]->value;
		maxLength[length]++;
		maxLengthBucket[length / SQRT]++;
	}
}

int findMaxLength()
{
	for (int i = SIZE - 1; i >= 0; i--)
	{
		if (maxLengthBucket[i] == 0) continue;

		for (int k = SQRT - 1; k >= 0; k--)
		{
			
			if (maxLength[i * SQRT + k] > 0)
			{
				return i * SQRT + k;
			}
		}
	}

	return 0;
}

int main()
{
	for(int i = 0; i < MAX; i++) front[i] = back[i] = &deque[i];

	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++) scanf("%d", &A[i]);

	scanf("%d", &M);

	for (int i = 0; i < M; i++)
	{
		int left, right;

		scanf("%d %d", &left, &right);

		query[i].index = i;
		query[i].left = left;
		query[i].right = right;
	}

	sort(query, 0, M - 1);

	int left, right;

	left = right = query[0].left;
	leftPush(left);

	for (int i = 0; i < M; i++)
	{
		while (right < query[i].right) rightPush(++right);
		while (left > query[i].left) leftPush(--left);

		while (right > query[i].right) rightPop(right--);
		while (left < query[i].left) leftPop(left++);
	
		answer[query[i].index] = findMaxLength();
	}

	for (int i = 0; i < M; i++) printf("%d\n", answer[i]);

	return 0;
}