题解 CF1111C 【Creative Snap】
swiftc
2019-08-05 12:34:45
看了那么多大佬的线段树题解，本萌新瑟瑟发抖，那么就写一篇卡常能过的$dfs$题解吧
首先，对于每一段区间，我们可以用树状数组来维护其中的复仇者数量，然后讨论如何炸毁这段区间：
如果其中没有复仇者，直接炸毁即可
要不然把区间分成两段，枚举每一段是直接炸毁还是继续$dfs$下去，最后取答案的最小值即可
### 但是注意一下数据范围
$1≤n≤30$
这样树状数组一定会$MLE$的
那用$map$代替数组？
复杂度多了一个$log$，又$TLE$了
那么我们就要用一种神奇的数据结构了：```tr1::unordered_map```，它和map的用法一模一样，而且复杂度是$O(1)$的
我们这样就愉快的通过这道题了
### code:
```cpp
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#pragma GCC optimize(3)
using namespace std;
#define int long long
int n,k,A,B,ans,a[100002],l;
tr1::unordered_map<int,int>tt;
void add2(int s,int v){
for(int i=s;i<=l+5;i+=(i&-i)){
tt[i]+=v;
}
}
int ask2(int s){
int sum=0;
for(int i=s;i;i-=(i&-i))sum+=tt[i];
return sum;
}
int work2(int l,int r){
int xr=ask2(r),xl=ask2(l-1);
if(xr-xl==0){
return A;
}
if(l==r){
return B*(xr-xl);
}
int mid=(l+r)/2;
int a1=work2(l,mid),a2=work2(mid+1,r);
int b1=B*(mid-l+1)*(ask2(mid)-xl),b2=B*(r-mid)*(xr-ask2(mid));
if(b1==0)b1=1e8;
if(b2==0)b2=1e8;
return min(B*(r-l+1)*(xr-xl),min(a1+b2,min(b1+a2,a1+a2)));
}
main(){
scanf("%lld%lld%lld%lld",&n,&k,&A,&B);
l=pow(2,n);
for(int i=1;i<=k;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=k;i++){
add2(a[i],1);
}
printf("%lld\n",work2(1,l));
return 0;
}
```