Codeforces 1111C Creative Snap分治+贪心

Thanos wants to destroy the avengers base,but he needs to destroy the avengers along with their base.

Let we represent their base with an array,where each position can be occupied by many avengers,but one avenger can occupy only one position. Length of their base is a perfect power of 22. Thanos wants to destroy the base using minimum power. He starts with the whole base and in one step he can do either of following:

• if the current length is at least 22,divide the basE into 22 equal halves and destroy them separately,or
• burn the current base. If it contains no avenger in it,it takes AA amount of power,otherwise it takes his B⋅@H_616_86@na⋅lB⋅na⋅l amount of power,where nana is the number of avengers and ll is the length of the current base.

Output the minimum power needed by Thanos to destroy the avengers‘ base.

#include <bits/stdc++.h>
using namespace std;
long long n,k,a,b;
long long hero[1000001];
long long solve(long long l,long long r) {
    long long num = upper_bound(hero + 1,hero + 1 + k,r) - lower_bound(hero + 1,hero + 1 + k,l);
    if (num == 0) return a;
    long long ans = (r - l + 1) * b * num;
    if (l >= r) return ans;
    ans = min(ans,solve(l,(l + r) / 2) + solve((l + r) / 2 + 1,r));
    return ans;
}
int main() {
    cin >> n >> k >> a >> b;
    for (long long i = 1; i <= k; i++) cin >> hero[i];
    sort(hero + 1,hero + 1 + k);
    cout << solve(1,(1 << n));
}