N 要素の配列、たとえば A[] が与えられます。最初は、それらのすべてが負の無限大に等しくなります。
ここで、2 種類のクエリ (合計 M クエリ) を実行するよう求められます。
1 を入力します。2 つの整数 a と d が与えられた場合、配列 A[] をインデックス l からインデックス r に更新する必要があります。正確に行う必要があるのは、「val」と言う値を含む各インデックスl + i（0 <= i <= rl）について、そのインデックスの値を最大a + i * dで更新する必要があり、 val、つまり、A[l+i] = max(A[l+i], a+i*d)。
2 を入力します。整数 'i' が与えられた場合、A[i] の値を報告する必要があります。
例 : N = 5、M = 4 とする
initially A[] = {-inf, -inf, -inf, -inf, -inf}
query 1: l = 2, r = 4, a = 2, d = 3
new A[] = {-inf, 2, 5, 8, -inf}
query 2: i = 3
output = 5
query 3: l = 3, r = 5, a = 10, d = -6
new A[] = {-inf, 2, 10, 8, -2}
query 4: i = 5
output = -2
注: N と M の値は 100000 にもなる可能性があるため、O(N*M) よりも優れたアルゴリズムを探しています。
ありがとう。