题解

#include <cstdio>
#include <algorithm>
#define int long long
#define maxn 100005

int n, k, A, B;
int a, rt = 1;
int c[maxn<<5], d[maxn<<5], cnt = 1; // c为区间人数，d为价值
int ls[maxn<<5], rs[maxn<<5];
// 注意动态开点线段树空间要开 log(区间长度) 倍（像我这种比较懒的就直接 << 5 了qwq）

void pushup(int cur, int len) {
    c[cur] = c[ls[cur]] + c[rs[cur]];
    d[cur] = std::min(B*c[cur]*len, d[ls[cur]] + d[rs[cur]]);
    // 更新d的过程对应2种方式：将cur看作1个区间的价值，拆分成2个区间的价值和
}

void ins(int& cur, int l, int r, int pos) {
    if(!cur) cur = ++cnt; // 动态开点
    if(l == r) {
        ++c[cur];
        d[cur] = B*c[cur];
        return;
    }
    int mid = (l+r)>>1;
    if(mid >= pos) ins(ls[cur], l, mid, pos);
    else ins(rs[cur], mid+1, r, pos);
    pushup(cur, r-l+1);
}

signed main() {
    scanf("%I64d%I64d%I64d%I64d", &n, &k, &A, &B);
    d[0] = A; // 空区间的价值为A（由于空区间一定没被访问，所以直接修改 d[0] 即可）
    while(k--) {
        scanf("%I64d", &a);
        ins(rt, 1, 1<<n, a); // 依次插入
    }
    printf("%I64d", d[1]);
    return 0;
}