题目大意：有一个长度为$2^n(n\leqslant30)$的格子，有$k(k\leqslant10^5)$个球，分布在这些格子中，有两种消灭格子的方法：

1. 若一段格子长度大于等于$2$，可以对半分开

2. 消灭一段格子，若其中有球，代价为$B\times x\times l$，$l$为格子长度，$x$为球个数；若没有球，代价为$A$

求最小代价

题解：动态开点线段树，直接模拟这个$DP$过程即可。可以把$0$号点代价设为$A$，表示没有球。

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       #define maxn 100010long long A, B;namespace SgT {#define N (maxn * 18)	long long V[N];	int lc[N], rc[N], idx, S[N];	void insert(int &rt, int l, int r, int pos) {		if (!rt) rt = ++idx;		++S[rt];		if (l == r) {			V[rt] = B * S[rt];			return ;		}		const int mid = l + r >> 1;		if (pos <= mid) insert(lc[rt], l, mid, pos);		else insert(rc[rt], mid + 1, r, pos);		V[rt] = std::min(B * S[rt] * (r - l + 1), V[lc[rt]] + V[rc[rt]]);	}}int n, k, rt;int main() {	scanf("%d%d%lld%lld", &n, &k, &A, &B); n = 1 << n;	SgT::V[0] = A;	for (int i = 0, x; i < k; ++i) {		scanf("%d", &x);		SgT::insert(rt, 1, n, x);	}	printf("%lld\n", SgT::V[rt]);	return 0;}