글 읽기 - 12015 세그먼트 트리 풀이 방식

dksdmssh1212 4년 전 0

안녕하세요 요번 문제를 세그먼트 트리로 어떻게든 풀고 싶은데... 제가 어떤 부분에서 틀린건지 궁금합니다..

update()함수에 문제가 있는 것 같은데... 혹시 잘 아시는 고수분 께서는 조언좀 부탁드리겠습니다..

시간을 뺏어서 죄송합니다

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

struct segment {
	int value;
	int index;
};
vector<segment> v;
vector<int> tree;
bool operator<(const segment& a, const segment& b) {
	if (a.value == b.value) {
		return a.index > b.index; // second에 대한 내림 차순.
	}
	return a.value < b.value; // first에 대한 오름차순
}
void update(vector<int>&, int, int, int, int, int);
int findMax(vector<int>&, int, int, int, int, int);
int main() {
	int N;
	segment inputSegment;
	cin >> N;
	int h = (int)ceil(log2(N));
	int treeSIze = (1 << (h + 1));
	tree.resize(treeSIze);//세그먼트 트리 초기화
	for (int i = 0; i < N; i++) {
		cin >> inputSegment.value;
		inputSegment.index = i;
		v.push_back(inputSegment);
	}
	sort(v.begin(), v.end());
	/*이제는 v vector를 갖고 세그먼트 트리 만들기*/
	int maxLength = 1;
	int maxIndex = 0;
	bool maxIndexFlag = false;
	for (int i = 0; i < v.size(); i++) {
		inputSegment = v[i];
		if (maxIndex < inputSegment.index) {
			maxIndex = inputSegment.index;
			maxIndexFlag = true;
		}
		maxLength = findMax(tree, 1, 0, N - 1, 0, inputSegment.index);
		if (!maxIndexFlag) {
			update(tree, 1, 0, N - 1, maxLength, inputSegment.index);
		}
		else {//maxIndex가 갱신되었을 경우
			update(tree, 1, 0, N - 1, ++maxLength, inputSegment.index);
		}
		maxIndexFlag = false;
	}
	cout << tree[1] << '\n';
	return 0;
}
void update(vector<int>& tree, int node, int start, int end, int value, int index) {
	if (index < start || index > end)	return;
	tree[node] = (tree[node] > value ? tree[node] : value);
	if (start != end) {
		int mid = (start + end) / 2;
		update(tree, node * 2, start, mid, value, index);
		update(tree, node * 2 + 1, mid + 1, end, value, index);
	}
}
int findMax(vector<int>& tree, int node, int start, int end, int left, int right) {
	if (left > end || start > right)	return 0;
	if (left >= start && right <= end)	return tree[node];
	int mid = (start + end) / 2;
	int a = findMax(tree, node * 2, start, mid, left, right);
	int b = findMax(tree, node * 2 + 1, mid + 1, end, left, right);
	return a > b ? a : b;
}

sait2000 4년 전 0

뭐가 맞는지는 잘 모르겠고 반례는 드릴 수 있겠네요

in:
10
1 2 3 4 5 5 4 3 2 1

out:
5

atomzeno 4년 전 0

67줄을 잘 보세요

그 67줄이 잘못되어 있어서 틀릴 뿐입니다

저 38~52줄에 저 복잡한 것들은 뭔지 모르겠어서 간소화하고 돌려보니까 맞네요

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

문제

문제

출처

ICPC

12015 세그먼트 트리 풀이 방식

dksdmssh1212 4년 전 0

sait2000 4년 전 0

atomzeno 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말