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

kysu5095 13일 전 0

몇가지 반례도 스스로 만들어보고 확인하였는데 제출하면 틀렸다고 나와서

제 아이디어가 문제인건지 확인 부탁드립니다ㅠㅠ

m개의 쌍을 pair 형태로 입력받은 후 pair의 first기준으로 sort하였습니다.

다음으로 모든 간선을 돌면서 query와 update를 해주는데

query는 현재 pair의 second를 기준으로 더 높은곳에 몇개의 간선이 지나갔는지를 반환합니다.

다음으로 update는 1~pair.second 구간까지 +1 씩해주어 해당 구간을 지났다고 표시해주었습니다.

처음에 sort를 해주었기때문에 다음부터는 오른쪽 구간의 값들만 비교하며 답을 구하면 될 것 같아서 구현해보았는데

틀렸습니다 뜨니깐 멘붕입니다. 어느부분이 잘못된건지 아니면 아이디어 자체가 틀렸는지 모르겠습니다ㅠ

// 교차개수세기

#define ll long long
#define MAX 2000
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
ll tree[(MAX << 2) + 1];
vector<pair<int, int>> v;

// 해당구간 +1
void update(int node, int l, int r, int& idx) {
	if (idx < l || idx > r) return;
	tree[node] += 1;
	if (l == r) return;
	int next = node << 1;
	int mid = (l + r) >> 1;
	update(next, l, mid, idx);
	update(next + 1, mid + 1, r, idx);
}

// 해당구간의 값 반환
ll query(int node, int l, int r, int start, int end) {
	if (l > end || r < start) return 0;
	if (l >= start && r <= end) return tree[node];
	int next = node << 1;
	int mid = (l + r) >> 1;
	return query(next, l, mid, start, end) + query(next + 1, r, mid + 1, start, end);
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int a, b;
	ll res = 0;
	cin >> n >> m;
	v.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++) {
		res += query(1, 1, n, v[i].second + 1, n);
		update(1, 1, n, v[i].second);
	}
	cout << res << '\n';
	return 0;
}

byeongkeunahn 13일 전 0

32번째 줄에 두 번째 query 호출에서 2번째, 3번째 매개변수 순서가 반대로 되어 있습니다.

kysu5095 12일 전 0

@byeongkeunahn 헐 감사합니다ㅠ 창피하네요,,

저런 실수 찾는게 더 어려우셨을텐데 정말 감사드립니다ㅠㅠ

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

문제

문제

출처

ICPC

세그먼트트리 질문드립니다.

kysu5095 13일 전 0

byeongkeunahn 13일 전 0

kysu5095 12일 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말