読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける遅延評価セグメント木問題まとめ

遅延評価セグメント木

セグ木に区間に対して値の変更を行えるデータ構造。
色んなパターンがあるので、まとめついでに。
あと、よくHL分解と一緒に使われる(難しくなる)

以下、問題

[l,r)にvを足す + [l,r)の最大値

CODE FESTIVAL 2015 決勝 D. 足ゲームⅡ

http://pekempey.hatenablog.com/entry/2015/11/15/193946

[l,r)にvを足す + [l,r)の最小値

ARC 045 B. ドキドキデート大作戦高橋君

http://arc045.contest.atcoder.jp/tasks/arc045_b

天下一プログラマーコンテスト 2016 予選B D. 天下一数列にクエリを投げます

http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_d
考察が難しいので入門ではない。

[l,r)にvを足す + [l,r)の総和

ABC 035 C. オセロ

http://abc035.contest.atcoder.jp/tasks/abc035_c
imos法でいけるが、verifyとしての例が紹介されていた
http://mmxsrup.hatenablog.com/entry/2017/01/02/191018

yukicoder No. 399 動的な領主

http://yukicoder.me/problems/no/399
HL分解と併用

[l,r)をvにする + [l,r)の総和

yukicoder No. 318 学学学学学

http://yukicoder.me/problems/899

yukicoder No. 230 Splarraay スプラレェーイ

https://yukicoder.me/problems/no/230

Codeforces Round #200 (Div. 1) D. Water Tree

http://codeforces.com/contest/343/problem/D
Euler Tourと併用

[l,r)をvにする + [l,r)のOR和

Educatinonal Codeforces Round 6 E. New Year Tree

http://codeforces.com/contest/620/problem/E
EulerTourも必要

[l,r)にxor1する + [l,r)の総和

NJPC2017 H. 白黒ツリー

http://njpc2017.contest.atcoder.jp/tasks/njpc2017_h
HL分解も必要

square869120Contest #2 H. Counting 1's

http://kmjp.hatenablog.jp/entry/2016/04/23/1200

神様向けの問題

AOJ 2450. Do use segment tree

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450
HL分解も必要。人が解く問題じゃない。

yukicoder No. 235 めぐるはめぐる(5)

http://yukicoder.me/problems/640
必要な知識は揃ってるはずなのに解けない問題