Codeforces 1111 C 스냅 만 들 기 (동적 오픈 라인 트 리)

wow 문제 내 는 사람 너무 양심 적 이다.
문제 의 뜻 을 이해 하고 우리 가 유지 해 야 할 것 은 길이 가 2n 2 ^ n 2n 인 구간 임 을 발견 했다.
그래서 우 리 는 선분 나무 로 지 키 고 싶 었 다.
선분 트 리 의 각 노드 는 구간 내의 인원수 와 가 치 를 유지 한 다음 에 제목 에 따라 p u s h u p pushup pushup pushup 을 유지 하면 됩 니 다.
한 구간 에 있 는 사람 이 000 이면 이 구간 의 가 치 는 A A A 가 될 수 있 음 을 주의 하 라.
2n 2 ^ n 2n 이 크기 때문에 우 리 는 동적 으로 노드 를 열 어야 합 니 다.
나 무 를 만 들 때 모든 사람 을 선분 트 리 에 순서대로 삽입 합 니 다.
마지막 답 은 바로 뿌리 노드 의 가치 이다.
시간 복잡 도 O (k l o g 2 n) = O (k n) O (klog 2 ^ n) = O (kn) O (klog2n) = O (kn).

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define loop(s, v, it) for (s::iterator it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (int i = head[x]; i; i = e[i].nxt)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, sum) memset(a, sum, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define iv inline void
#define enter cout << endl
#define siz(x) ((int)x.size())
#define file(s) freopen(s".in", "r", stdin), freopen(s."out", "w", stdout)
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <int, int> pii ;
typedef vector <int> vi ;
typedef vector <pii> vii ;
typedef queue <int> qi ;
typedef set <int> si ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int N = 100010 ;
const int INF = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 2e18 ;
const int MOD = 1000000007 ;
const double eps = 1e-7 ;
void print(int x) { cout << x << endl ; exit(0) ; }
void PRINT(string x) { cout << x << endl ; exit(0) ; }
void douout(double x){ printf("%lf
", x + 0.0000000001) ; }

int n, m, A, B, rt = 1, cnt = 1 ;
int tr[N << 5], d[N << 5], ls[N << 5], rs[N << 5] ;

void pushup(int now, int len) {
	tr[now] = tr[ls[now]] + tr[rs[now]] ;
	d[now] = min(B * tr[now] * len, d[ls[now]] + d[rs[now]]) ;
}

void modify(int &now, int l, int r, int pos) {
	if (!now) now = ++cnt ;
	if (l == r) {
		tr[now]++ ;
		d[now] = B * tr[now] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	if (mid >= pos) modify(ls[now], l, mid, pos) ;
	else modify(rs[now], mid + 1, r, pos) ;
	pushup(now, r - l + 1) ;
}

signed main(){
	scanf("%lld%lld%lld%lld", &n, &m, &A, &B) ;
	d[0] = A ;
	while (m--) {
		int x ; scanf("%lld", &x) ;
		modify(rt, 1, 1 << n, x) ;
	}
	printf("%lld
", d[1]) ;
	return 0 ;
}

/*
       ：
	1.ll？    ，  ？    ？
	2.  ？
	3.  ？
	4.     
    ：
	1.     ->  ？
	2.     ？  dp   
	3.     
	4.           ？
	5.      dp？   ？
	6.    ？
*/