Dynamic Range Prefix Max

概要

数列Aに対して自身の左にそれより大きい値が存在しない要素を結合した数列をprefix_max(A)と呼ぶことにする
例えばprefix_max([2, 1, 5, 3, 4, 6, 9, 8, 7, 10]) = [2, 5, 6, 9, 10] である
セグ木で区間のprefix_maxを管理して長さやk番目の値を取得する

操作

constructor(vector V): 数列Vで初期化
set(int p, T x): p番目の要素をxにする
get(int p): p番目の要素を返す
prod_max(int l, int r): [l, r)の最大値を返す
prod_len(int l, int r): [l, r)のprefix_maxの長さを返す
max_right(int l, f): f(prod_len(l, r), prod_max(l, r))がtrueである最大のrを返す

実装

使用例1

提出(ネタバレ注意)