JOI Open Contest 2019-1問目 三段跳び

問題概要

1以上10^9以下の長さNの数列Hがある。

Qつのクエリに答える。

L<=a<b<c<=R && (b-a)<=(c-b) なるindexの組(a,b,c)に対してH[a]+H[b]+H[c]の和の最大値を求めよ。

N,Q=5*10^5

小課題１

N,Q=100であるため、愚直O(QN^3)

小課題２

N=5000である。解法はいくつか考えられるが、例えば、aとcの組すべてに対してH[a]+H[b]+H[c]の和の最大値を前処理で求めておけば良い。O(N^2+Q) 

小課題３

Q=1である。解法がいくつか考えられるが、満点に繋がらないものを述べる。

a,b,cのいずれかが大きい方からlog2_N番目以内のものである。よってaやbやcを決め打って他の二ペアの値の和の最大値を求めることができ、O(QNlogN) 

小課題４

aとbのペアが限定できる。具体的には、min(H[a],H[b])>max(H[a+1~b-1])となるようなものに限定される。H[a],H[b]の値は大きい方が良く、またaとbは近い方が良い（他のものを内包するなら不要）ことに由来する。このようなペアは高々2Nつであり、setなどで適当に求められる。b=2b-aとし、a<b<cの制約のみを残すと考えやすくなる。

[a,b)の区間Nつとc｜a<b<cを処理する問題となった。いまcに対する制約がindexオーダーの不等号ひとつで非常に自由な状態であることから、indexのオーダーで走査することを考える。

クエリの区間[L,R)が更新の区間[a,b)を内包する形であり、bはオーダーに関係のない値であるから、右から左に境界を移動させ、区間の左端（Lやa）で処理を行うべきである。具体的に、x[i]を変数、y[i]をH[i]の値として、クエリの区間ではx[i]+y[i]の最大値を求め、更新の区間ではx[i]の最大化処理を行えば良い。それぞれのバケットにはx[i]+y[i]の最大値を持ち、区間更新はその値をx[i]+(バケット内のy[i]の最大値）で最大化することで実現できる。バケットが結合律を持ち遅延評価がO(1)でできるため、Segtreeを使うことができ、計算量はO((N+Q)logN)

区間の内包外包関係についての深い理解が問われる問題。