由于不想保存了所以全部汇总到这来了。正好从新审视一下那些题再评个级。

CF1111C [1]

这题刚一看觉得很水，仔细一看数据范围……

其实也不难，主要是数据范围过大。要用一种类似离散化的做法。

对数组a排序。对于一段区间[l,r]的英雄数量等于a中第一个比r大的数的下标减1减a中第一个大于等于l的数的下标加1，这样就可以做了(k很小)。

不过要注意剪枝：若区间[l,r]的英雄数量等于0，就直接返回A。

(还可以从动态开点线段树来理解

#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));
}