split game [yukicoder No.844] - はまやんはまやんはまやん

前提知識

動的計画法更新最適化（SegTree）

解説

何から始めようかという問題である。
フローっぽい雰囲気もあるが、レベルが2.5だし、制約も10^5なので違うだろう。
天才最適貪欲かもと一瞬思ったが、そこから考えると沼になりそうだったので、後回し。
他に適用できそうな典型といえば、DPかという感じで、とりあえずDPで考える。
　
DPで重要なのは、状態をまとめるという部分であるが、「この部分はどうなっていてもいい」みたいな
まとめられるところがないか探す。
ある区間[Lj, Rj]が存在するときに点をえることができるが、

[0,Lj)はどうなっていてもいい→状態をまとめることができる
[Lj,Rj]は線があってはいけない→最後に線がある位置だけが重要なのではないか？

というところから、
dp[i] := 最後にマスiの後ろに黒線を引いたときの点数の最大値
というDPを考える。
　
dp[i]を順番に埋めていくが、dp[i]が更新される遷移としては2種類ある。

もう既に区間の左側に黒線がある場合はdp[i] = dp[l-1] - A + p
区間の左側に黒線がない場合はdp[i] = dp[0...l-2]の最大値 - A - A + p

マイナスAは黒線を引くことで引かれる点数で、プラスpは区間が完成することで得られる点数。
ここでdpの区間の最大値を取ってくる必要があるが、これはSegTreeを使おう。
累積和でもできるし、計算量はこっちのほうがいい
（けど、頭使わんでいいSegTreeの方をまずは習得するのがおすすめ）
いろいろ注意点があるけど、大枠はこれでいける。
dp[0..N]の最小値が答え。
　
注意点は2つある。
　
①
dp[N]を埋めるときに、右側の黒線は既に引かれているため、Aを引く必要がない。
分岐させるのがちょっと面倒だが、自分は
right := 右側の黒線を引くためのコスト
と変数として分けて、i=Nのときだけright=0としている。

②
区間は右端が早いものから評価していく。
これはdpテーブルの更新を左から順番にしていく必要があるためである。
R[r] := 右端がrである区間の{左端, 得点}の集合
を用意しておき、DP更新のときに該当する区間を評価していくようにしよう。

自分はたぶんこれを解いていたから、この問題を解くことができた。
類題として紹介しておく。

int N, M, A;
SegTree<ll, 1 << 17> dp;
vector<pair<int, int>> R[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> A;
	rep(i, 0, M) {
		int l, r, p; cin >> l >> r >> p;
		R[r].push_back({ l, p });
	}

	rep(i, 0, N + 1) dp.update(i, -infl);
	dp.update(0, 0);

	rep(r, 1, N + 1) {
		fore(p, R[r]) {
			int l = p.first;
			int q = p.second;

			ll right = A;
			if (r == N) right = 0;

			ll ma = -infl;
			chmax(ma, dp.get(0, l - 1) - A - right + q);
			chmax(ma, dp[l - 1] - right + q);

			dp.update(r, max(dp[r], ma));
		}
	}

	cout << dp.get(0, N + 1) << endl;
}