翻译题面地址
原地址

根据题目要求,灭霸有两种方式来摧毁复仇者的基地,其中一种是把基地分为等长的两段。于是由分段联想到分治。
我们可以通过观察题目的A,B大小而得出结论:假设说一段基地下有hero,那么一定是不分开处理更优,除非英雄全部堆在某一边。
那么就可以写一个分段的深搜来做这道题。那我们怎么判断英雄在一个区间的数量呢?,当然是二分啦,把英雄的pos按升序存在数组里,于是就可以lowerbound与upperbound在数组里愉快的查找并返回下标,具体的话看一下代码里的solve函数把~
下面贴上代码

#include<iostream>
#include<algorithm> 
using namespace std;
typedef long long ll;
ll ans,n,k,A,B,av,a[100005];
inline ll solve(ll lr, ll ri)
{
    return (upper_bound(a+1,a+1+k,ri)-upper_bound(a+1,a+1+k,lr-1));
}
inline ll dfs(ll L,ll R)
{
    //cout<<L<<" "<<R<<endl;
    ll mid=(L+R)>>1;
    ll tmp=mid+1;
    ll ls=solve(L,R);
    ll res=0;
    //cout<<ls<<endl;
    //cout<<solve(L,mid)<<endl;
    //cout<<solve(tmp,R)<<endl;
    if(L==R)
    {
        if(ls)
        {
            return B*ls;
        }
        else
        {
            return A;
        }
    }
    if(ls==0)
    {
        return A;
    }
    else
    {
        if(solve(L,mid)==ls||solve(tmp,R)==ls)
        {
            ll ls1=dfs(L,mid);
            ll ls2=dfs(tmp,R);
            if(ls1+ls2<((R-L+1)*B*ls))
            {
                res=res+ls1+ls2;
            }
            else
            {
                res+=((R-L+1)*B*ls);
            }
        }
        else
        {
            res+=dfs(L,mid);
            res+=dfs(tmp,R);
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>A>>B;
    for(register int i=1;i<=k;i++)
    {
        cin>>a[i];
    }
    n=(ll)pow(2,n);
    sort(a+1,a+k+1);
    ans+=dfs(1,n/2);
    ans+=dfs(n/2+1,n);
    cout<<ans;
    return 0;
}