Để dễ hình dung hơn, với mỗi truy vấn có các tham số ~s,f,c,r~, ta sẽ hiểu là cần xây dựng một dãy ~a_{p_1}, a_{p_2}, a_{p_3}, ... ,a_{p_{r+1}}~, với dãy ~p~ không giảm và ~p_1 = s~ và ~p_{r+1} = f~, sao cho ~val = max (a_{p_i}-a_{p_{i-1}})~ là bé nhất.

Kết quả của truy vấn sẽ chính là ~val*c~. Như vậy kết quả của bài toán sẽ là ~max(val*c)~ với mọi truy vấn.

Subtask 1

• Ta sẽ dùng phương pháp chặt nhị phân kết quả để tìm giá trị ~val~ .
• Với mỗi giá trị ~mid~, ta có thể kiểm tra xem nó có thỏa mãn không bằng cách xuất phát từ ~a_s~, đi đến một vị trí ~i~ sao cho ~i~ lớn nhất, ~i > s~ và ~a_i - a_s \le mid~. Ta tính đây là một lần dừng lại. Sau đó, ta lại xuất phát từ ~i~ và lặp lại hành động tương tự. Nếu ta có thể đi tới được ~f~ mà không cần dừng lại quá ~r~ lần, giá trị ~mid~ sẽ thỏa mãn.
• Như vậy, ta có thể chặt nhị phân để tìm ~val~ nhỏ nhất thỏa mãn.
• Độ phức tạp ~O(n*log)~ cho một truy vấn.

Subtask 3

• Tuy lần này, ~n \le 400~, nhưng ~m~ lại rất lớn, lên tới ~5*10^5~ nên một thuật toán như ~subtask~ ~1~ sẽ không thể chạy.
• Ta cần sử dụng kĩ thuật quy hoạch động cho bài toán này. Gọi ~dp(l,r,k)~ là kết quả tối ưu (giá trị ~val~) cho đoạn ~[l,r]~ nếu ta chỉ được dừng lại ~k~ lần. Như vậy, với mỗi truy vấn ta sẽ lấy kết quả với ~max (c*dp(s,f,r))~.
• Ta có công thức quy hoạch động như sau: ~dp(l,r,k) = min(max(dp(l,x,k-1),a[r]-a[x]))~, với ~x \in [l,r-1]~.
• Như vậy ta sẽ thu về thuật toán có độ phức tạp ~O(n^4)~, chỉ đủ để qua ~subtask~ ~2~.
• Đến đây ta cần tối ưu công thức này như sau:
  • Gọi ~optimize(l,r,k) = x~ là vị trí tốt nhất mà ~dp(l,r,k) = max (dp(l,x,k-1),a[r]-a[x])~ đạt ~min~.
  • Ta có nhận xét rằng ~optimize(l,r,k) \le optimize(l,r+1,k)~.
  • Mặt khác, ta có ~dp(l,r,k) = min (max (dp(l,x,k-1),a[r]-a[x]))~, mà ~dp(l,x,k-1) \le dp (l,x+1,k-1)~, đồng thời ~a[r] - a[x] > a[r] - a[x+1]~ và hàm ~y = max (dp(l,x,k-1),a[r]-a[x])~ sẽ có dạng giảm dần xuống đáy với từng giá trị ~x~ rồi sau khi chạm đáy giá trị sẽ tăng dần. Như vậy, ta chỉ cần tăng ~x~ tới khi nào ~max (dp(l,x,k-1),a[r]-a[x])~ chạm đáy.
  • Vậy ta có thể thực hiện thuật toán ~2~ con trỏ để tính được mảng ~optimize~ song song với việc tính mảng ~dp~.
  • Từ đó ta thu được thuật toán ~O(n^3)~.
• Tuy vậy, ta cần tối ưu hóa bộ nhớ, dễ thấy ta không cần lưu chiều ~l~ của ~dp(l,r,k)~, đồng thời không cần lưu mảng ~optimize~. Từ đó bộ nhớ giảm xuống còn ~N^2~.

Code:

#include<iostream>
#include<vector>
using namespace std;
const int N = 405;
const int M = 1e5+5;
int d[N][N];
int n,m;
int a[M];
long long res = 0;
struct qr {
    int f,c,r;
};
vector<qr> v[N];
namespace sub1 {
    int s,f,c,r;
    bool check (int mid) {
        int res = 0;
        int st = s;
        for (int i=s; i<=f; i++) {
            int j = i;
            while (j < f && a[j+1]-a[i] <= mid) {
                j++;
            }
            if (j == i) return false;
            i = j-1;
            res++;
            if (j == f) break;
        } res--;
        return res <= r;
    }
    void solve () {
        for (int i=1; i<=n; i++) cin >> a[i];
        cin >> s >> f >> c >> r;
        long long lef = 0, rig = 1e9, res = 1e9;
        while (rig >= lef) {
            int mid = (rig+lef) >> 1;
            if (check(mid)) res = mid, rig = mid - 1;
            else lef = mid + 1;
        }
        cout << 1ll*res*c << '\n';
    }
}
void cal () {
    for (int l=1; l<=n; l++) {
        for (int r=l; r<=n; r++) {
            d[r][0] = a[r] - a[l];
        }
        for (int k=1; k<=n; k++) {
            int opt = l;
            for (int r=l; r<=n; r++) {
                while (opt < r && max (d[opt][k-1],a[r]-a[opt]) >= max (d[opt+1][k-1],a[r]-a[opt+1])) {
                    opt++;
                }
                d[r][k] = max (d[opt][k-1],a[r]-a[opt]);
            }
        }
        for (auto val : v[l]) {
            int f = val.f, c = val.c, r = val.r;
            res = max (res,1ll*d[f][r]*c);
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    if (m == 1) {
        sub1::solve();
        return 0;
    }
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    for (int i=1; i<=m; i++) {
        int s,f,c,r;
        cin >> s >> f >> c >> r;
        v[s].push_back({f,c,r});
    }
    cal();
    cout << res;
}