Author: Tri_Phan

Ý tưởng:

Bản chất của mỗi truy vấn chính là in ra giá trị lớn nhất trong ba giá trị sau:

• ~\text{max}(a[1\dots l-1])~
• ~\text{max}(a[l\dots r])-d~
• ~\text{max}(a[r+1\dots n])~

Subtask 1

Gọi ~F[i][j] = max(a[i\dots j])~. Ta có thể tính mảng ~F~ trong ~O(n^2)~ bằng 2 vòng for và có thể trả lời truy vấn trong ~O(1)~.

ĐPT: ~O(n^2+q)~

Subtask 2

Gọi ~F[i][j] = max(a[i \dots i+2^j-1])~. Dựng sparse table sẽ tốn ~O(nlogn)~ và truy vấn sẽ tốn ~O(1)~.

ĐPT: ~O(nlogn+q)~

Subtask 3

Gọi ~best = max(a[1\dots n])~, ~Pre[i] = max(1\dots i)~, ~Suf[i] = max(i\dots n)~. ~best~ và mảng ~Pre,Suf~ đều có thể tính trong ~O(n)~.

Ta nhận thấy, do ~d\geq 0~ nên đáp án của mỗi truy vấn không thể vượt quá ~best~. Nếu ~max(Pre[l-1],Suf[r+1])=best~ thì đáp án của truy vẫn là ~best~. ngược lại, ~best~ nằm trong đoạn ~l,r~, khi đó ~max(a[l\dots r])-d=best-d~, đáp án sẽ là ~max(Pre[l-1],best-d,Suf[r+1])~.

ĐPT: ~O(n+q)~