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
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<vector>
#include<functional>

using namespace std;

typedef long long int int64;

typedef struct {
	int64 distance;
	int count;
	int next;
	bool exists;
} segment_t;

priority_queue<pair<int64, int>, vector<pair<int64, int> >, greater<pair<int64, int> > > q;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	segment_t* segs = (segment_t*)malloc((n + 8) * sizeof(segment_t));
	segs[0].count = 1;
	segs[0].distance = 0;
	segs[0].exists = true;
	segs[0].next = 1;
	int64 last = 1000008;
	for (int i = 0; i < n; ++i) {
		int64 cur;
		scanf("%lld", &cur);
		cur += 1000008;
		segs[i + 1].count = 1;
		segs[i].distance = cur - last;
		segs[i + 1].exists = true;
		segs[i + 1].next = i + 2;
		q.push(make_pair(segs[i].distance, i));
		last = cur;
	}
	segs[n].next = -1;
	int64* results = (int64*)malloc(1000008 * sizeof(int64));
	int64 delta = 0;
	int64 sum = 0;
	for (int64 i = 0; i <= 1000000; ++i) {
		sum += delta;
		while (!q.empty()) {
			pair<int64, int> t = q.top();
			int s = t.second;
			if (!segs[s].exists) {
				q.pop();
				continue;
			}
			if (t.first > i) {
				break;
			}
			q.pop();
			int s2 = segs[s].next;
			if (s2 == -1) {
				continue;
			}
			segs[s2].exists = false;
			segs[s].next = segs[s2].next;
			int64 c1 = (int64)segs[s].count;
			int64 c2 = (int64)segs[s2].count;
			if (segs[s].distance < c1 * i) {
				sum += c2 * (c1 * i - segs[s].distance);
			}
			delta -= c1 * (c1 - 1) >> 1;
			delta -= c2 * (c2 - 1) >> 1;
			delta += (c1 + c2) * (c1 + c2 - 1) >> 1;
			segs[s].distance += segs[s2].distance;
			segs[s].count += (int)c2;
			if (segs[s].next != -1) {
				q.push(make_pair(segs[s].distance / segs[s].count + 1, s));
			}
		}
		results[i] = sum;
	}
	for (int i = 0; i < m; ++i) {
		int d;
		scanf("%d", &d);
		printf("%lld\n", results[d]);
	}
	return 0;
}