信息學不是數學，所以樂子題解當樂子看看就行了 /lh

思路

大膽猜測，當查詢的 \(h\) 變小時，用按鈕的次數一定不會減少，于是上決策單調性可以直接秒掉。

接下來嘗試證明一下。設允許的最高高度為 \(h\)，令 \(f(x)\) 表示按 \(x\) 次按鈕的代價，\(g(h,x)\) 表示按 \(x\) 次后還需要單獨操作的貢獻以達到 \(h\)，則當詢問 \(h\) 時先按 \(x\) 次按鈕的代價就是 \(c(h,x) = f(x) + g(h,x)\)。

把 \(f(x),g(h,x)\) 表示出來，其中 \(cnt_i\) 表示 \(a\) 中 \(\leq i\) 的元素數量，\(sum_i\) 表示 \(a\) 中 \(\geq i\) 的元素之和，\(s_i\) 表示 \(a\) 中 \(= i\) 的元素之和，\(v_i\) 表示 \(a\) 中 \(= i\) 的元素數量：

考慮 \(c(h,x)\) 與 \(c(h,x + 1)\) 的增量 \(\Delta c(h,x)\)：

顯然 \(\Delta c(h,x)\) 隨 \(h\) 的增大而減小，且 \(c(h,x)\) 是一個單谷函數。我們希望對于每一個詢問每一次選擇的 \(c(h,x)\) 都盡量的小，因此我們的決策點 \(p\) 一定為最小的滿足 \(\Delta c(h,x) \geq 0\) 的數。

由于 \(\Delta c(h,x)\) 單調遞減，因此對于一個較大的 \(h\) 其決策點 \(p\) 一定較小。于是滿足決策單調性的定義，證畢！

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
const int inf = (int)(1e18) + 10;
int n,t,s,k,q,m;
int arr[N],cnt[N],sum[N],cst[N],ans[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void dfs(int l,int r,int vl,int vr){
    if (l > r) return;
    int mid = l + r >> 1;
    int Min = inf,pos = 0;
    for (re int i = vl;i <= vr;i++){
        int val = cst[i] + (sum[mid + i + 1] - (cnt[m] - cnt[mid + i]) * (i + mid)) * t;
        if (Min > val) Min = val,pos = i;
    } ans[mid] = Min;
    dfs(l,mid - 1,pos,vr); dfs(mid + 1,r,vl,pos);
}

signed main(){
    n = read(),t = read(),s = read(),k = read();
    for (re int i = 1;i <= n;i++){
        cnt[arr[i] = read()]++; sum[arr[i]] += arr[i];
    } m = *max_element(arr + 1,arr + n + 1);
    for (re int i = 1;i <= 2 * m;i++) cnt[i] += cnt[i - 1];
    for (re int i = m;~i;i--) sum[i] += sum[i + 1];
    for (re int i = 1;i <= m;i++) cst[i] = cst[i - 1] + s + k * cnt[i - 1];
    dfs(0,m,0,m); q = read();
    while (q--) printf("%lld ",ans[read()]);
    return 0;
}