悬5+关

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int a[200005],c[200005];
int dp[200005][3];
struct ph{
	int p,a;
}h[200005];
struct edge2{
	int p,m,ans;
}w[200005];
bool cmp1(ph x,ph y){
	return x.a<y.a;
}
bool cmp2(edge2 x,edge2 y){
	return x.m<y.m;
}
bool cmp3(edge2 x,edge2 y){
	return x.p<y.p;
}
int zws(int a,int b,int c){
	return a+b+c-max({a,b,c})-min({a,b,c});
}
void ch(int x,int m){
	dp[x][0]=1e18,dp[x][1]=1e18,dp[x][2]=1e18;
	int dpc0=(a[x]<m)?(0):(c[x]);
	int dpc1=(a[x]==m)?(0):(c[x]);
	int dpc2=(a[x]>m)?(0):(c[x]);
	if(x*2>n&&x*2+1>n){
		dp[x][0]=dpc0;
		dp[x][1]=dpc1;
		dp[x][2]=dpc2;
		return;
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				if(zws(i,j,k)==i){
					if(i==0) dp[x][i]=min(dp[x][i],dp[x*2][j]+dp[x*2+1][k]+dpc0);
					if(i==1) dp[x][i]=min(dp[x][i],dp[x*2][j]+dp[x*2+1][k]+dpc1);
					if(i==2) dp[x][i]=min(dp[x][i],dp[x*2][j]+dp[x*2+1][k]+dpc2);
				}
			}
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>c[i];
		dp[i][0]=1e18,dp[i][1]=1e18,dp[i][2]=1e18;
		h[i].p=i,h[i].a=a[i];
	}
	sort(h+1,h+n+1,cmp1);
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>w[i].m;
		w[i].p=i; 
	}
	sort(w+1,w+q+1,cmp2);
	for(int i=n;i>=1;i--){
		ch(i,w[1].m);
	}
	w[1].ans=dp[1][1];
	int cnt1=1,cnt2=1;
	for(int i=2;i<=q;i++){
		for(;cnt1<=n&&h[cnt1].a<w[i].m;cnt1++){
			for(int x=h[cnt1].p;x;x>>=1){
				ch(x,w[i].m);
			}
		}
		for(;cnt2<=n&&h[cnt2].a<=w[i].m;cnt2++){
			for(int x=h[cnt2].p;x;x>>=1){
				ch(x,w[i].m);
			}
		}	
		w[i].ans=dp[1][1];	
	}
	sort(w+1,w+q+1,cmp3);
	for(int i=1;i<=q;i++){
		cout<<w[i].ans<<endl;
	}
	return 0;
}