题意：
\(n\)个哨站排成一列，第\(i\)个哨站的频段为\(a_i\)。
现在每个哨站可以选择:
- 直接连接到中心，代价为\(w\)；
- 连接到前面某个哨站\(j(j<i)\)，代价为\(|a_i-a_j|\)。
- 规定每个哨站只能被后面的至多一个哨站连接。
问最终最小代价和为多少。
思路：
-
直接费用流比较好想：每个点有两个选择，我们将点拆为两个点\(x_i,y_i\)，然后
- \(S->x_i\)容量为\(1\)，费用为\(w\)；
- \(S->y_i\)容量为\(1\)，费用为\(0\)；
- \(y_i->x_j,j>i\)容量为\(1\),费用为\(|a_i-a_j|\)。
-
但直接来搞的话边的数量是\(O(n^2)\)的，时间复杂度不能承受。
-
我们考虑拆绝对值，然后考虑每个位置的贡献。
-
具体来说，采用分治的思想（太妙了QAQ），对于当前区间\([l,r]\)，我们只考虑现在\(x_i\) ~ \(x_{mid}\)到\(y_{mid+1}\) ~ \(y_r\)之间的连边。
-
因为我们是拆绝对值，这里要分两种情况考虑，我们接下来考虑\(a_i>a_j\)的情况。
-
我们将左边的部分提取出来，离散化后从大到小串在一起，那么每个点都有一个贡献，之后视在哪部分连线即可；
-
另外一种情况类似。
-
因为采用分治，每一层我们会多出\(O(n)\)级别的边，所以最后边的总数为\(O(nlogn)\)级别了。
核心思想感觉还是拆分绝对值后单独考虑每个值的贡献，相同的一起计算。但这种串在一起的方式感觉也太巧妙了。。
代码如下：
#include <bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
// #define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 2e5 + 5;int n, w, tot;
int a[N];class Flow
{
bool vis[N],inq[N];ll dis[N];queue<int>q;
struct edge{int to,w,c,nex;}e[N*10];int cur[N],hr[N],en;
bool spfa()
{
for(int i=S;i<=T;++i) cur[i]=hr[i],inq[i]=0,dis[i]=1e18;
for(dis[S]=0,inq[S]=1,q.push(S);!q.empty();)
{
int u=q.front();q.pop(),inq[u]=0;
for(int i=hr[u];i;i=e[i].nex)
if(dis[e[i].to]>dis[u]+e[i].c&&e[i].w)
{
dis[e[i].to]=dis[u]+e[i].c;
if(!inq[e[i].to]) inq[e[i].to]=1,q.push(e[i].to);
}
}
return dis[T]<INF;
}
int dfs(int x,int f)
{
if(x==T||!f) return f;
vis[x]=1;
int w,used=0;
for(int &i=cur[x];i;i=e[i].nex)
if(dis[e[i].to]==dis[x]+e[i].c&&e[i].w&&!vis[e[i].to])
{
w=dfs(e[i].to,min(f-used,e[i].w));
e[i].w-=w;e[i^1].w+=w;used+=w;
if(used==f) break;
}
vis[x]=0;return used;
}
public:
int S,T;
Flow(){S=0;en=1;}
void ins(int x,int y,int w,int c)
{
e[++en]=(edge){y,w,c,hr[x]},hr[x]=en;
e[++en]=(edge){x,0,-c,hr[y]},hr[y]=en;
}
ll Ans(){ll r=0;while(spfa())r+=dfs(S,INF)*dis[T];return r;}
}F;int b[N], D;void solve(int l, int r) {
if(l == r) return;
int mid = (l + r) >> 1;
#define lb(x) lower_bound(b + 1, b + D + 1, x) - b
#define p(x) tot + x
D = 0;
for(int i = l; i <= mid; i++) b[++D] = a[i];
sort(b + 1, b + D + 1); D = unique(b + 1, b + D + 1) - b - 1;
for(int i = 2; i <= D; i++) F.ins(p(i), p(i - 1), INF, 0);
for(int i = l; i <= mid; i++) {
F.ins(i + n, p(lb(a[i])), 1, a[i]);
}
for(int i = mid + 1; i <= r; i++) {
int j = lb(a[i]);
if(j <= D) F.ins(p(j), i, 1, -a[i]);
}
tot += D;
D = 0;
for(int i = mid + 1; i <= r; i++) b[++D] = a[i];
sort(b + 1, b + D + 1); D = unique(b + 1, b + D + 1) - b - 1;
for(int i = 2; i <= D; i++) F.ins(p(i - 1), p(i), INF, 0);
for(int i = mid + 1; i <= r; i++) {
F.ins(p(lb(a[i])), i, 1, a[i]);
}
for(int i = l; i <= mid; i++) {
int j = lb(a[i]);
if(j <= D) F.ins(i + n, p(j), 1, -a[i]);
}
tot += D;
solve(l, mid); solve(mid + 1, r);
}void run() {
for(int i = 1; i <= n; i++) cin >> a[i];
tot = 2 * n;
solve(1, n);
F.T = tot + 1;
for(int i = 1; i <= n; i++) F.ins(F.S, i, 1, w);
for(int i = 1; i <= n; i++) F.ins(i, F.T, 1, 0);
for(int i = 1; i <= n; i++) F.ins(F.S, i + n, 1, 0);
cout << F.Ans() << '\n';
}int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
#ifdef Local
freopen("../input.in", "r", stdin);
freopen("../output.out", "w", stdout);
#endif
while(cin >> n >> w) run();
return 0;
}
