1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#define zak 200010
using namespace std;

typedef pair<long long,long long> PII;

long long n,m,dl,rep[zak],mn[zak],mx[zak],siz[zak];
long long last,wyn[zak],ILE,t[zak],WYN;
vector<PII> v;
priority_queue<PII,vector<PII>,greater<PII> > q;

long long MUL(long long n)
{
	return n*(n-1)/2;
}

int FIND(int A)
{
	if(rep[A]!=A)rep[A]=FIND(rep[A]);
	return rep[A];
}

void UNION(int A,int B)
{
	if(siz[A]<siz[B])UNION(B,A);
	else
	{
		rep[B]=A;
		ILE+=MUL(siz[A]+siz[B])-MUL(siz[A])-MUL(siz[B]);
		WYN+=(siz[A]+siz[B])*t[min(mn[A],mn[B])]+MUL(siz[A]+siz[B])*last;
		WYN-=siz[A]*t[mn[A]]+MUL(siz[A])*last;
		WYN-=siz[B]*t[mn[B]]+MUL(siz[B])*last;
		siz[A]+=siz[B];
		siz[B]=0;
		mx[A]=max(mx[A],mx[B]);
		mn[A]=min(mn[A],mn[B]);
		if(mx[A]!=n)
		{
		    long long ODL=t[mx[A]+1]-t[mn[A]];
		    long long OD1=ODL/siz[A];
			if(ODL%siz[A]!=0)OD1++;
	 	    q.push(make_pair(OD1,mx[A]));
		}
	}
}

int main()
{
	scanf("%lld%lld",&n,&m);
	siz[0]=1;
	for(int i=1;i<=n;i++)
	{
		mn[i]=mx[i]=rep[i]=i;
		siz[i]=1;
 	    scanf("%lld",&t[i]);
 	}
	for(int i=0;i<n;i++)
	{
		q.push(make_pair(t[i+1]-t[i],i));
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d",&dl);
		v.push_back(make_pair(dl,i));
	}
	sort(v.begin(),v.end());
	last=0;
	for(int i=0;i<m;i++)
	{
		long long DL=v[i].first;
		while(!q.empty()&&q.top().first<=DL)
		{
			long long pos=q.top().second;q.pop();
			if(FIND(pos)!=FIND(pos+1))
			{
				UNION(FIND(pos),FIND(pos+1));
			}
		}
		WYN+=ILE*(DL-last);
		last=DL;
		wyn[v[i].second]=WYN;
	}
	for(int i=0;i<m;i++)printf("%lld\n",wyn[i]);
}