글 읽기 - 세그먼트 트리로 풀었는데 시간초과가 나네요 ㅠㅠ

dustn9401 6년 전 0

update 함수를 조금 개선해야 할 것같은데.. 방법이 떠오르지를 않네요 ㅠㅠ

힌트 한번만 주시면 감사하겠습니다..

#include <stdio.h>

int arr[100001] = { 0 };
int tree[400004] = { 0 };
int sum(int start, int end, int left, int right, int index);
int update(int start, int end, int left, int right, int index);
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (b > c)
		{
			int tmp = b;
			b = c;
			c = tmp;
		}
		if (a == 0)
			update(1, n, b, c, 1);
		else
			printf("%d\n", sum(1, n, b, c, 1));
	}
}
int sum(int start, int end, int left, int right, int index)
{
	if (start > right || end < left)
		return 0;
	else if(start >= left && end <= right)
		return tree[index];
	else
		return sum(start, (start + end) / 2, left, right, index * 2) + sum((start + end) / 2 + 1, end, left, right, index * 2 + 1);
}
int update(int start, int end, int left, int right, int index)
{
	if (start > right || end < left)    //left와 right 범위 밖일 경우 더이상 탐색하지 않습니다.
		return tree[index];
	else if(start == end)    //left와 right 범위의 리프 노드는 비트 반전
		return tree[index] = !tree[index];
	else    //반전시킨 리프 노드를 따라 올라가며 트리를 갱신합니다.
		return tree[index] = update(start, (start + end) / 2, left, right, index * 2) + update((start + end) / 2 + 1, end, left, right, index * 2 + 1);
}

lyzqm 6년 전 1

하나의 index를 update하는데는 O(logN)이 걸립니다.

최악의 경우 구간 [1,N]을 update하는데 O(N*logN)이 되겠죠..

이러면 query가 M번 들어올 수 있으니 O(M*N*logN)이 되어서 시간초과가 발생합니다.

세그먼트 트리를 유지한채 lazy propagation라는 기법을 이용하면 해결할 수 있습니다.

dustn9401 6년 전 11

감사합니다... 참 벼라별게 다 있네요

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

문제

문제

출처

ICPC

세그먼트 트리로 풀었는데 시간초과가 나네요 ㅠㅠ

dustn9401 6년 전 0

lyzqm 6년 전 1

dustn9401 6년 전 11

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말