글 읽기 - 세그먼트 트리 질문입니다.

kkw564 7년 전 0

init :: O(nlgn)

query :: O(mlgn)

각각 두개니

O(2nlgn + 2mlgn) -> O((n+m)lgn)이 맞나요??

이렇게 하면 시간초과 받나요 ?? ㄷㄷ.. 최대 200,000*lg100,000 -> 대략 200,000 * 20 = 4백만정도인데..

#include <cstdio>
#include <iostream>
#include <math.h>
#include <vector>
#include <limits.h>

#define min(a,b)(a < b ? a : b)
#define max(a,b)(a > b ? a : b)

using namespace std;

typedef pair<int, int> pii;

int initF(vector<int> &arr, vector<pair<int, int>> &tree, int node, int start, int end)
{
	if (start == end)
		return tree[node].first = arr[start];

	int mid = (start + end) / 2;

	return tree[node].first = min(initF(arr, tree, node * 2, start, mid), initF(arr, tree, node * 2 + 1, mid + 1, end));
}

int initS(vector<int> &arr, vector<pair<int, int>> &tree, int node, int start, int end)
{
	if (start == end)
		return tree[node].second = arr[start];

	int mid = (start + end) / 2;

	return tree[node].second = max(initS(arr, tree, node * 2, start, mid), initS(arr, tree, node * 2 + 1, mid + 1, end));
}

int queryMin(vector<pair<int, int>> &tree, int node, int start, int end, int left, int right)
{
	if (left > end || right < start)
		return INT_MAX;

	if (left <= start && end <= right)
		return tree[node].first;

	int mid = (start + end) / 2;

	return min(queryMin(tree, node * 2, start, mid, left, right), queryMin(tree, node * 2 + 1, mid + 1, end, left, right));
}

int queryMax(vector<pair<int, int>> &tree, int node, int start, int end, int left, int right)
{
	if (left > end || right < start)
		return -1;

	if (left <= start && end <= right)
		return tree[node].second;

	int mid = (start + end) / 2;
	
	return max(queryMax(tree, node * 2, start, mid, left, right), queryMax(tree, node * 2 + 1, mid + 1, end, left, right));
}
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	int h = (int)ceil(log2(n));
	int tree_size = (1 << (1 + h));

	vector<int> arr(n);
	vector<pair<int ,int>> tree(tree_size);


	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	initF(arr, tree, 1, 0, n - 1);
	initS(arr, tree, 1, 0, n - 1);

	
	for (int i = 0; i < m; i++)
	{
		int left, right;
		scanf("%d %d", &left, &right);

		printf("%d %d\n", queryMin(tree, 1, 0, n - 1, left-1, right-1), queryMax(tree, 1, 0, n - 1, left-1, right-1));
	}
	
	return 0;
}

kkw564 7년 전 0

찾다보니 발견한 코드가 아래 주소코드인데

https://github.com/stemp12/stu...

이 코드랑 다른게 pair뿐인데 저것때문에 시간초과가 나나요??

cki86201 7년 전 3

min과 max 매크로 안에 함수를 넣으면 함수가 여러 번 호출됩니다.

예를 들어 min (f (a), f (b))는

f (a)<f (b)?f (a):f (b)가 되어서 f 함수가 세 번 호출됩니다.

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

문제

문제

출처

ICPC

세그먼트 트리 질문입니다.

kkw564 7년 전 0

kkw564 7년 전 0

cki86201 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말