BOJ 13545 : 수열과 쿼리 0

알고리즘 문제 전체 링크

 

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

 

참고

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

- 머지 소트 Merge Sort

- BOJ 10866 : 덱 with Linked List

- BOJ 13546 : 수열과 쿼리 4

 

 

수열과 쿼리 4에서 구해야하는 값은 아래와 같다.

 

● l r : max{|x - y| : l ≤ x, y ≤ r and Ax = Ay} 를 출력한다.

 

즉, 구간 [left, right]에서 같은 원소가 있는 경우 그 원소의 index의 차이가 가장 큰 값이다.

 

수열과 쿼리 0에서는 [left, right]에서 부분 수열 중 합이 0인 가장 긴 부분 수열의 길이를 구해야 한다.

그런데 특정 구간 [c, d]의 합이 0이라면 [1, d]까지의 합과 [1, c - 1]까지의 합이 같다.

 

즉, 두 값이 같아야 한다.

 

이것은 수열과 쿼리 4에서 구해야하는 값이 아래와 같이 바뀌는 것을 의미한다.

 

● l r : max{|x - y| : l ≤ x, y ≤ r and Sx = Sy} 를 출력한다.

 

이때, c - 1에서 구간이 한 칸 밀리는 것은 left를 입력 받을 때 1을 빼주면 해결된다.

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

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

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

 

A를 모두 입력받은 후 누적합을 그대로 A에 추가하면 S를 구할 수 있다.

그리고 A의 모든 값에 100,000을 더한다.

왜냐하면 수열과 쿼리 4는 1 ~ 100,000의 경우를 구하는 문제지만, 

이 문제는 -100,000 ~ 100,000이므로, 0 ~ 200,000으로 값을 변경해서 이전에 사용한 방식을 그대로 사용하도록 한다.

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

 

따라서 MAX도 200,000으로 변경하고 SQRT도 448로 바꾼다.

전체 코드에서 확인해보자.

#include <stdio.h>

#define MAX (200000 + 100)
#define SQRT (448)
#define SIZE (MAX / SQRT + 1)

int N, 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", &N);

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

	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 - 1;
		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;
}