题意：
n 个排成一列的哨站要进行通信。第 i 个哨站的频段为 ai。
每个哨站 ii 需要选择以下二者之一：
1.直接连接到控制中心，代价为 W；
2.连接到前面的某个哨站 j(j<i)，代价为 |ai−aj|。 每个哨站只能被后面的至多一个哨站连接。
请你求出最小可能的代价和。
题解：
显然的费用流
然后我耿直的n^2建边，觉得我的费用流很快，应该可以过
然后返回了TLE
然后google了一下题解：发现这题卡了n^2建图,需要优化建边
我这里是通过分治优化的
就是类似与建立一个虚点
一个x要向y的一个前缀建图，所以就可以类似前缀和优化建图那样，
按权值排序然后建出一条链，链上两个点之间的流量为INF，费用为权值之差，然后每个点向对应的点连边
但这样建图是错误的，原因在于我们把点排了序，改变了编号顺序，
所以一个点能到达的点不一定是它可以到达的
所以我们要固定在固定编号顺序的情况下这样连边，也就是说x的一个区间和y的一个区间之间这样连边，
要求两个区间不重合，且x的区间比y的区间小
那么很容易想到分治建图，每次让[l,mid]向[mid+1,r]连边，剩下的递归下去就行了
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map> #define pi acos(-1.0)
#define eps 1e-9
#define fi first
#define se second
#define rtl rt << 1
#define rtr rt << 1 | 1
#define bug printf("******\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define name2str(x) #x
#define fuck(x) cout << #x " = " << x << endl
#define sfi(a) scanf("%d", &a)
#define sffi(a, b) scanf("%d %d", &a, &b)
#define sfffi(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define sffffi(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define sfL(a) scanf("%lld", &a)
#define sffL(a, b) scanf("%lld %lld", &a, &b)
#define sfffL(a, b, c) scanf("%lld %lld %lld", &a, &b, &c)
#define sffffL(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
#define sfs(a) scanf("%s", a)
#define sffs(a, b) scanf("%s %s", a, b)
#define sfffs(a, b, c) scanf("%s %s %s", a, b, c)
#define sffffs(a, b, c, d) scanf("%s %s %s %s", a, b, c, d)
#define FIN freopen("../in.txt", "r", stdin)
#define gcd(a, b) __gcd(a, b)
#define lowbit(x) x & -x
#define IO iOS::sync_with_stdio(false) using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL seed = ;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 1e6 + ;
const int maxm = 8e6 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ; struct Cost_MaxFlow {
int s, t, tot, maxflow, head[maxn], vis[maxn], pre[maxn], last[maxn];
LL mincost, maxcost, dis[maxn], disf[maxn];
struct Edge {
int v, w, nxt;
int cost;
} edge[maxm];
queue<int> q; void init() {
tot = ;
mincost = maxcost = ;
memset(head, -, sizeof(head));
} void add(int u, int v, int f, int e) {
edge[++tot].v = v, edge[tot].nxt = head[u], head[u] = tot, edge[tot].w = f, edge[tot].cost = e;
edge[++tot].v = u, edge[tot].nxt = head[v], head[v] = tot, edge[tot].w = , edge[tot].cost = -e;
} bool spfa_max() {
memset(dis, 0xef, sizeof(dis));
q.push(s), dis[s] = , disf[s] = INFLL, pre[t] = -;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].w && dis[v] < dis[u] + edge[i].cost) {
dis[v] = dis[u] + edge[i].cost, last[v] = i, pre[v] = u;
disf[v] = min(disf[u], 1LL * edge[i].w);
if (!vis[v])
vis[v] = , q.push(v);
}
}
}
return ~pre[t];
} void dinic_max() {
while (spfa_max()) {
int u = t;
maxflow += disf[t];
maxcost += disf[t] * dis[t];
while (u != s) {
edge[last[u]].w -= disf[t];
edge[last[u] ^ ].w += disf[t];
u = pre[u];
}
}
} bool spfa_min() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, , sizeof(vis));
memset(disf, 0x3f, sizeof(disf));
q.push(s), dis[s] = , vis[s] = , pre[t] = -;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = ;
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].w > && dis[v] > dis[u] + edge[i].cost) {
dis[v] = dis[u] + edge[i].cost, pre[v] = u;
last[v] = i, disf[v] = min(disf[u], 1LL * edge[i].w);
if (!vis[v])
vis[v] = , q.push(v);
}
}
}
return pre[t] != -;
} void dinic_min() {
while (spfa_min()) {
int u = t;
maxflow += disf[t];
mincost += disf[t] * dis[t];
while (u != s) {
edge[last[u]].w -= disf[t];
edge[last[u] ^ ].w += disf[t];
u = pre[u];
}
}
}
} F; int n, W, a[maxn], cnt[maxn], sum; void link(int L, int R) {
if (L == R) return;
int num = , mid = (L + R) / ;
for (int i = L; i <= R; i++) cnt[++num] = a[i];
sort(cnt + , cnt + + num);
num = unique(cnt + , cnt + + num) - cnt - ;
for (int i = ; i < num; i++) {
F.add(sum + i, sum + i + , INF, cnt[i + ] - cnt[i]);
F.add(sum + i + , sum + i, INF, cnt[i + ] - cnt[i]);
}
for (int i = L; i <= R; i++) {
if (i <= mid) {
int pos = lower_bound(cnt + , cnt + + num, a[i]) - cnt;
F.add(sum + pos, i + n, , );
} else {
int pos = lower_bound(cnt + , cnt + + num, a[i]) - cnt;
F.add(i, sum + pos, , );
}
}
sum += num;
link(L, mid), link(mid + , R);
} int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif
while (~sffi(n, W)) {
for (int i = ; i <= n; i++) sfi(a[i]);
F.init();
F.s = , F.t = * n + ;
sum = * n + ;
for (int i = ; i <= n; i++) {
F.add(F.s, i, , );
F.add(i + n, F.t, , );
F.add(i, F.t, , W);
}
link(, n);
F.dinic_min();
printf("%lld\n", F.mincost);
}
#ifndef ONLINE_JUDGE
cout << "Totle Time : " << (double) clock() / CLOCKS_PER_SEC << "s" << endl;
#endif
return ;
}