CodeChef ELEPHANT Elephant

問題文

https://www.codechef.com/problems/ELPHANT
IOI 2011 の問題なのでこっちでも見れます.
https://www.ioi-jp.org/ioi/2011/tasks/day2/elephants_jpn.pdf

問題概要

直線状にいる N 匹の象を幅 L まで撮れるカメラで撮る. 全匹を撮るための最小の撮影回数を求めよ. さらに, M 回象が移動するクエリが来るので毎回最小の撮影回数を求めよ.

制約：1 ≤ N,M ≤ 150,000 0 ≤ L,(象の座標) ≤ 10^9

解法

とりあえず象が移動しない場合は, 左端から順に貪欲で撮っていけばいいことはわかります.

このとき, 象たちの関係を木構造にします.

各象の親を, その象の位置+L より右にいる最初の象となるようにしていきます. （INF の位置にダミー象を置いておきます）
すると, 左端の象からスタートして何回木を登れば根（=ダミー象）にたどり着けるかが答えになります.
じゃあパスの長さを高速で求められれば良さそうですね.

あとは象が移動するクエリはいい感じに木を切ったり繋げたりが高速でできれば解けそうな気がしてきます.

つまり, Link-Cut Tree ですね.

Link-Cut Tree の詳しい解説は以下のスライドが非常にわかりやすいのでこちらを見てください.
（というかこのスライドにもこの問題の解説載ってるし, この記事の意味とは…）

プログラミングコンテストでのデータ構造 2 ～動的木編～

今回は根が右端で固定なので evert は要らないため実装が少し楽です.

あと, 象の位置が distinct とは限らないので座標圧縮した後の位置の個数だけノードを作って, ノードに象がいる位置なら 1 いないなら 0 となる値を持たせておいて, 左端から右端までのパス上のノードの値の和を求める, という感じでやるとわかりやすい気がします.

ソースコード

https://www.codechef.com/viewsolution/17457318

#include <bits/stdc++.h>
using namespace std;

class lct_node {
	lct_node *l, *r, *p;
	int val, sum;

	int pos() {
		if (p && p->l == this) return -1;
		if (p && p->r == this) return 1;
		return 0;
	}
	void update() {
		sum = (l ? l->sum : 0) + val + (r ? r->sum : 0);
	}
	void push() {
		if (pos()) p->push();
	}
	void rot() {
		lct_node *par = p;
		lct_node *mid;
		if (p->l == this) {
			mid = r;
			r = par;
			par->l = mid;
		}
		else {
			mid = l;
			l = par;
			par->r = mid;
		}
		if (mid) mid->p = par;
		p = par->p;
		par->p = this;
		if (p && p->l == par) p->l = this;
		if (p && p->r == par) p->r = this;
		par->update();
		update();
	}
	void splay() {
		push();
		while (pos()) {
			int st = pos() * p->pos();
			if (!st) rot();
			else if (st == 1) p->rot(), rot();
			else rot(), rot();
		}
	}

public:
	lct_node(int v) : l(nullptr), r(nullptr), p(nullptr), val(v), sum(v) {}
	void expose() {
		for (lct_node *x = this, *y = nullptr; x; y = x, x = x->p) x->splay(), x->r = y, x->update();
		splay();
	}
	void link(lct_node *x) {
		x->expose();
		expose();
		p = x;
	}
	void cut() {
		expose();
		l->p = nullptr;
		l = nullptr;
		update();
	}
	int find_sum() {
		expose();
		return sum;
	}
	void update_val(int v) {
		expose();
		val = v;
		update();
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int N, L, M;
	cin >> N >> L >> M;
	vector<int> p(N), x(M), y(M), ps;
	ps.push_back(INT_MAX);
	for (int i = 0; i < N; i++) {
		cin >> p[i];
		ps.push_back(p[i]);
	}
	for (int i = 0; i < M; i++) {
		cin >> x[i] >> y[i];
		ps.push_back(y[i]);
	}
	sort(ps.begin(), ps.end());
	ps.erase(unique(ps.begin(), ps.end()), ps.end());
	int V = ps.size();
	vector<lct_node> lct(V, 0);
	for (int i = 0; i < V - 1; i++) {
		lct[i].link(&lct[i + 1]);
	}
	vector<int> cnt(V);
	for (int i = 0; i < N; i++) {
		int id = lower_bound(ps.begin(), ps.end(), p[i]) - ps.begin();
		if (cnt[id]++ == 0) {
			int to = lower_bound(ps.begin(), ps.end(), p[i] + L + 1) - ps.begin();
			lct[id].cut();
			lct[id].link(&lct[to]);
			lct[id].update_val(1);
		}
	}
	for (int i = 0; i < M; i++) {
		{
			int id = lower_bound(ps.begin(), ps.end(), p[x[i]]) - ps.begin();
			if (--cnt[id] == 0) {
				lct[id].cut();
				lct[id].link(&lct[id + 1]);
				lct[id].update_val(0);
			}
		}
		{
			int id = lower_bound(ps.begin(), ps.end(), y[i]) - ps.begin();
			if (cnt[id]++ == 0) {
				int to = lower_bound(ps.begin(), ps.end(), y[i] + L + 1) - ps.begin();
				lct[id].cut();
				lct[id].link(&lct[to]);
				lct[id].update_val(1);
			}
		}
		p[x[i]] = y[i];
		printf("%d\n", lct[0].find_sum());
	}
	return 0;
}