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)~

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 3;

int pre[N], suf[N], a[N];
int n, m, x, k, q;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k >> x >> q;
  a[1] = x;
  for (int i = 2; i <= n; i++)
    a[i] = (1LL * a[i - 1] * k) % m;
  for (int i = 1; i <= n; i++)
    a[i] -= q;
  // for (int i = 1;i<=n;i++) cout << a[i] << " "; cout << "\n";
  pre[0] = -2e9;
  suf[n + 1] = -2e9;
  for (int i = 1; i <= n; i++)
    pre[i] = max(pre[i - 1], a[i]);
  for (int i = n; i >= 1; i--)
    suf[i] = max(suf[i + 1], a[i]);

  int t;
  cin >> t;
  int best = suf[1];
  while (t--) {
    int l, r, d;
    cin >> l >> r >> d;
    if (pre[l - 1] == best || suf[r + 1] == best)
      cout << best << "\n";
    else
      cout << max(max(suf[r + 1], pre[l - 1]), best - d) << "\n";
  }
}