(mathcal{Description})
Link.
给定序列 ({w_n})，选择 (i) 位置的代价为 (w_i)，要求每个位置要不被选择，要不左右两个位置至少被选择一个。求前 (k) 小的选择代价。
(n,kle2.5 imes10^5)。
(mathcal{Solution})
建图，边形如 (lang i,i+j,w_i ang~(j=1,2,3))，再引入左右两个虚点 (s,t)，那么每种方案对应从 (s) 到 (t) 的一条路径，题目即求无负权图上的前 (k) 小路径，是道模板题，很可惜我并不会。（
还是用前 (k) 小的一贯套路：用堆维护，每次取当前最优方案扩展。首先在建出以 (t) 为根的内向最短路树，考虑用一条非树边 (lang u,v,w ang) 替换最短路 (P=lang s,cdots,t ang) 的一段，则有 (P'=lang s,cdots,u,v,cdots,t ang)，且满足 (w(P')=d_S-d_u+w+d_v)，其中 (d_u) 即 (u) 到 (t) 的最短路。这样我们得到了扩展一次的方法：取 (s) 到 (t) 最短路的邻接边 (lang u,v,w ang) 中，(d_v+w-d_u) 最小的边替换最短路。
如果替换多条边呢？可以发现有两种替换方法：
- 将当前最优的 (lang u,v,w ang) 替换为新的 (lang u,v',w' ang)；
- 在当前 (lang u,v,w ang) 的基础上，取 (v) 到 (t) 最短路的邻接边扩展。
那么用可持久化左偏树维护每个点到 (t) 的可用邻接边集合即可支持扩展。设图的点数为 (n)，边数为 (m)，整个复杂度则为 (mathcal O((m+k)log m))，本题则有 (mathcal O((n+k)log n))。
(mathcal{Code})
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef long long LL;
typedef std::pair<LL, int> PLI;
typedef std::pair<int, int> PII;
#define fi first
#define se second
const int MAXN = 2.5e5;
int n, m, pre[MAXN + 5], root[MAXN + 5];
LL dis[MAXN + 5];
std::vector<PII> oriG[MAXN + 5], revG[MAXN + 5];
struct PersistentLeftistTree {
static const int MAXND = 3e7;
int node, ch[MAXND + 5][2], rds[MAXND + 5];
PLI val[MAXND + 5]; // (cost, end point).
inline int newnd( const PLI& v ) {
val[++node] = v, ch[node][0] = ch[node][1] = 0, rds[node] = 1;
return node;
}
inline int merge( int x, int y ) {
if ( !x || !y ) return x | y;
if ( val[x] > val[y] ) std::swap( x, y );
int u = newnd( val[x] );
ch[u][0] = ch[x][0], ch[u][1] = merge( ch[x][1], y );
if ( rds[ch[u][1]] > rds[ch[u][0]] ) std::swap( ch[u][0], ch[u][1] );
return rds[u] = rds[ch[u][1]] + 1, u;
}
} plt;
inline void link( const int s, const int t, const int w ) {
oriG[s].push_back( { t, w } ), revG[t].push_back( { s, w } );
// std::cerr << s << ' ' << t << ' ' << w << '
';
}
inline void dijkstra() {
static std::priority_queue<PLI, std::vector<PLI>, std::greater<PLI> > heap;
memset( dis, 0x3f, sizeof dis );
heap.push( { dis[n + 1] = 0, n + 1 } );
while ( !heap.empty() ) {
PLI p( heap.top() ); heap.pop();
if ( dis[p.se] < p.fi ) continue;
for ( const PII& e: revG[p.se] ) {
if ( dis[e.fi] > p.fi + e.se ) {
heap.push( { dis[e.fi] = p.fi + e.se, e.fi } );
pre[e.fi] = p.se;
}
}
}
}
inline void solve() {
per ( u, n, 0 ) {
root[u] = root[pre[u]];
for ( const PII& v: oriG[u] ) {
if ( pre[u] != v.fi ) {
root[u] = plt.merge( root[u],
plt.newnd( { dis[v.fi] + v.se - dis[u], v.fi } ) );
}
}
}
static std::priority_queue<PLI, std::vector<PLI>, std::greater<PLI> > heap;
std::cout << dis[0] << '
';
if ( root[0] ) heap.push( { plt.val[root[0]].fi, root[0] } );
while ( --m ) {
if ( heap.empty() ) { std::cout << "-1
"; continue; }
PLI p( heap.top() ); heap.pop();
std::cout << dis[0] + p.fi << '
';
int u;
if ( ( u = plt.merge( plt.ch[p.se][0], plt.ch[p.se][1] ) ) ) {
heap.push( { p.fi - plt.val[p.se].fi + plt.val[u].fi, u } );
}
if ( ( u = root[plt.val[p.se].se] ) ) {
heap.push( { p.fi + plt.val[u].fi, u } );
}
}
}
int main() {
std::ios::sync_with_stdio( false ), std::cin.tie( 0 );
std::cin >> n >> m;
rep ( i, 1, n ) {
int w; std::cin >> w;
rep ( j, 1, 3 ) {
if ( i + j <= n || ( i + j == n + 1 && j < 3 ) ) {
link( i, i + j, w );
}
}
}
link( 0, 1, 0 );
if ( n > 1 ) link( 0, 2, 0 );
dijkstra();
// rep ( i, 0, n + 1 ) std::cout << dis[i] << ' ' << pre[i] << '
';
solve();
return 0;
}