Aは長さN(1ある数a1,a2,a3,s1,s2,s3,e1,e2,e3(1<= ai, si,ei <= 50000)が与えられた時、
A[i] = (a1*i*i+a2*i+a3)%9973
S[i] = (s1*i*i+s2*i+s3)%(N/2)
E[i] = S[i]+(e1*i*i+e2*i+e3)%(N/2)
R[i] = min(A[S[i]], A[S[i]+1], ..., A[E[i]])
と定義される。
R[j] = max(R[0], R[1], ..., R[M-1])となる、最小のjを求めよ。

サイズlog(N) * Nで、
B[i][j] = min(A[j],A[j+1], ..., A[j+(1<となる配列Bを作ってしまえばよい。
B[i][j] = (i==0? A[j]: min(B[i-1][j], B[i-1][j+(1<<(i-1))]))
とする事で、B全体は、O(N*log(N))で作ることが出来る。
Bを参照する事により、Rの各要素はlog(N)で求めることができるので、
R全体もO(N*log(N))で作ることが出来る。

1341.cpp