글 읽기 - 이 문제 세그트리로는 못 푸나요?

smu201111192 7년 전 0

세그트리로 접근해서 풀고 있는데 .

자꾸 wa받네요. 애초에 세그트리로는 풀기 불가능한문젠가요

제 로직을 간단하게 설명하자면.

선분을 아래좌표가 작은순으로 정렬한후

차례대로 세그트리에 넣어가면서 비교해줍니다.

아래좌표가 정렬되어있으니. 위좌표만을 통해서 Lis를 구해주는거랑 비슷하게 생각하고 접근했는데

어떤게 문제일까요 .

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
	int st, ed;
	bool operator <(const node n)const{
		if (st != n.st)return st < n.st;
		return ed > n.ed; //이따 생각
	}
};
node nd[100001];
vector<int> tree;
int dp[100001] = {0,};
void update(int node,int s,int e,int pos,int newValue){
	if (pos<s || pos>e)return;
	if (s == e){
		dp[s] = newValue;
		return;
	};
	int mid = (s + e) / 2;
	update(node * 2, s, mid, pos, newValue);
	update(node * 2 + 1, mid + 1, e, pos, newValue);
	if (dp[tree[node * 2]]>dp[tree[node * 2 + 1]]){
		tree[node] = tree[node * 2];
	}
	else
		tree[node] = tree[node * 2] + 1;
}
void build(int node,int s,int e){
	if (s == e){
		tree[node] = s;
		return;
	}
	int mid = (s + e) / 2;
	build(node * 2, s, mid);
	build(node * 2 + 1, mid + 1, e);
}
int query(int node,int s,int e,int st,int ed){
	if (s>ed || e < st)return 0;
	if (s >= st && e <= ed)return tree[node];
	int mid=(s + e) / 2;
	int a = query(node * 2, s, mid, st, ed);
	int b = query(node * 2 + 1, mid + 1, e, st, ed);
	if (dp[a] > dp[b])
		return tree[node * 2];
	else
		return tree[node * 2 + 1];
}
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	tree.resize(4 * n);
	for (int i = 0; i < n; i++){
		cin >> nd[i].ed >> nd[i].st;
	}
	sort(nd, nd + n);
	int ans = 0;
	build(1, 1, n);
	for (int i = 0; i < n; i++){
		int st = nd[i].st, ed = nd[i].ed;
		int index = query(1, 1, n, ed + 1, n);
		int a;
		if (dp[index] == 0){
			a = 0;
			update(1, 1, n,ed, a + 1);
		}
		else{
			a = dp[index];
			update(1, 1, n, index, a + 1);
		}
		ans = max(a + 1, ans);
	}
	cout << ans;
	return 0;
}

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

문제

문제

출처

ICPC

이 문제 세그트리로는 못 푸나요?

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말