\(\mathcal{Description}\)
??Link.
??给定序列 \(\{w_n\}\)，选择 \(i\) 位置的代价为 \(w_i\)，要求每个位置要不被选择，要不左右两个位置至少被选择一个。求前 \(k\) 小的选择代价。
??\(n,k\le2.5\times10^5\)。
\(\mathcal{Solution}\)
??建图，边形如 \(\lang i,i+j,w_i\rang~(j=1,2,3)\)，再引入左右两个虚点 \(s,t\)，那么每种方案对应从 \(s\) 到 \(t\) 的一条路径，题目即求无负权图上的前 \(k\) 小路径，是道模板题，很可惜我并不会。（
??还是用前 \(k\) 小的一贯套路：用堆维护，每次取当前最优方案扩展。首先在建出以 \(t\) 为根的内向最短路树，考虑用一条非树边 \(\lang u,v,w\rang\) 替换最短路 \(P=\lang s,\cdots,t\rang\) 的一段，则有 \(P‘=\lang s,\cdots,u,v,\cdots,t\rang\)，且满足 \(w(P‘)=d_S-d_u+w+d_v\)，其中 \(d_u\) 即 \(u\) 到 \(t\) 的最短路。这样我们得到了扩展一次的方法：取 \(s\) 到 \(t\) 最短路的邻接边 \(\lang u,v,w\rang\) 中，\(d_v+w-d_u\) 最小的边替换最短路。
??如果替换多条边呢？可以发现有两种替换方法：
- 将当前最优的 \(\lang u,v,w\rang\) 替换为新的 \(\lang u,v‘,w‘\rang\)；
- 在当前 \(\lang u,v,w\rang\) 的基础上，取 \(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 << ‘\n‘;
}
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] << ‘\n‘;
if ( root[0] ) heap.push( { plt.val[root[0]].fi, root[0] } );
while ( --m ) {
if ( heap.empty() ) { std::cout << "-1\n"; continue; }
PLI p( heap.top() ); heap.pop();
std::cout << dis[0] + p.fi << ‘\n‘;
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] << ‘\n‘;
solve();
return 0;
}