BOJ 2568 - 전깃줄2 ( LIS, segtree )

www.acmicpc.net/problem/2568

 

<문제설명>

pair로 입력받아 정렬후 second값의 LIS를 제외한 나머지의 first값 출력

 

<풀이>

위 점화식을 구간최대 세그트리를 이용해서 구하면 된다. 세그트리의 인덱스는 second값.

 

 

<코드>

const int MAX = 1e5 + 4;
const int SMAX = (1 << 20);

int n, dp[MAX], befo[MAX];
P seg[SMAX], a[MAX];

void update(int i, int x, int y) {
	i += SMAX / 2;
	seg[i] = { x,y };
	while (i > 1) {
		i /= 2;
		seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
	}
}

P val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return { 0,0 };
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return max(val(s, e, node * 2, ns, mid), val(s, e, node * 2 + 1, mid + 1, ne));
}
P val(int s, int e) {
	return val(s, e, 1, 0, SMAX / 2 - 1);
}

int main() {
	FAST; cin >> n;
	for (int i = 1, x, y; i <= n; i++) {
		cin >> x >> y;
		a[i] = { x,y };
	}

	sort(a + 1, a + n + 1);
	for (int i = 1,x,y,idx,temp; i <= n; i++) {
		tie(x, y) = a[i];
		tie(temp, idx) = val(0, y - 1);
		dp[i] = temp+1;
		befo[i] = idx;
		update(y, dp[i], i);
	}

	set<int> s;
	for (int i = 1,x,y; i <= n; i++) {
		if (dp[i] == seg[1].first) {
			int t = i;
			while (true) {
				s.insert(t);
				t = befo[t];
				if (t == 0) break;
			}
			break;
		}
	}
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		if (s.count(i) == 0) {
			ans.push_back(a[i].first);
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << '\n';
}