【2018-国庆雅礼-NOIP-培训】-D4T3-z

发表于

题面

这里是链接

题解

由题面，如果存在一个 $x_i$ 使得 $x_i−1$ = $x_i$ 或 $x_{i−1} < x_i < x_{i+1}$ 或 $x_{i−1} > x_i > x_{i+1}$，那么可以删去它。

需要行走的路径可以表示为一正一负的位移，有两种情况：

  • 当 $l$ 不超过最小的位移绝对值时，答案是一个 一次函数。

  • 当 $l$ 超过这个值时，意味着当我们到达一个位置时，后继位置直接被接触到，我们需要将 $3$ 个位移合并为 $1$ 个（当然在首尾位置时可能要特判），答案又是一个一次函数。

所以我们用 $map$/$链表$维护位移序列，$priority queue$ 维护最小位移绝对值，离线询问即可。

标程

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
88
89
90
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
int n,m;
ll tot,ans[maxn];
vector<int> x;
vector<pair<int,int> > a;
map<int,int> mp;

inline ll calc(ll k){
	if(!mp.empty()&&mp.begin()->second<0)
		return tot-(mp.size()-1)*k;
	else
		return tot-mp.size()*k;
}
inline void solve(){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	int t=0;
	for(int i=0;i<x.size();++i){
		tot+=abs(x[i]);
		mp[i]=x[i];
		q.push(make_pair(abs(x[i]),i));
	}
	while(!q.empty()){
		int id=q.top().second,tmp=q.top().first;q.pop();
		map<int,int>::iterator p=mp.lower_bound(id);
		if(p==mp.end()||p->first!=id||abs(p->second)!=tmp)
			continue;
		while(t<a.size()&&abs(p->second)>a[t].first)
			ans[a[t].second]=calc(a[t].first),++t;
		if(p!=mp.begin())
			if(p!=prev(mp.end())){
				tmp=p->second,tot-=abs(p->second);
				tmp+=prev(p)->second,tot-=abs(prev(p)->second);
				tmp+=next(p)->second,tot-=abs(next(p)->second);
				mp.erase(prev(p));
				mp.erase(next(p));
				p->second=tmp,tot+=abs(tmp);
				q.push(make_pair(abs(tmp),id));
			}
			else{
				tot-=abs(p->second);
				mp.erase(p);
			}
		else if(p->second>0)
			if(p!=prev(mp.end())){
				tmp=p->second,tot-=abs(p->second);
				tmp+=next(p)->second,tot-=abs(next(p)->second);
				mp.erase(next(p));
				if(tmp){
					p->second=tmp,tot+=abs(tmp);
					q.push(make_pair(abs(tmp),id));
				}
				else
					mp.erase(p);
			}
			else{
				tot-=abs(p->second);
				mp.erase(p);
			}
	}
	while(t<a.size())
		ans[a[t].second]=calc(a[t].first),++t;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0,p,last=0;i<n;++i){
		scanf("%d",&p);
		if(p==last)
			continue;
		if(!x.empty()&&(x.back()<0&&p<last||x.back()>0&&p>last))
			x.back()+=p-last;
		else
			x.push_back(p-last);
		last=p;
	}
	for(int i=0,l;i<m;++i){
		scanf("%d",&l);
		a.push_back(make_pair(l,i));
	}
	sort(a.begin(),a.end());
	solve();
	for(int i=0;i<m;++i)
		printf("%lld\n",ans[i]);
	return 0;
}