sto cmd 学长 orz
题意
给定一个长度为 \(n\) 的排列，试将它分成 \(k\) 段，使得每段的顺序对数量之和最小。
\(n \leq 2.5 \times 10^4, k \leq 25\)
思路
决策单调性优化 dp + 分治乱搞。
dp 做法是显然的：
令 \(f[i][j]\) 表示前 \(i\) 个数分成 \(j\) 段的最小代价。
令 \(c(i, j)\) 表示 \([i, j]\) 内的顺序对数量，则 \(f[i][j] = \min\limits_{k = 0}^{i - 1} f[k][j - 1] + c(k + 1, i)\)
这个方程满足四边形不等式，感性理解：
令 \(p1 \leq p2 \leq p3 \leq p4\)，观察四边形不等式：
\(c(p1, p3) + c(p2, p4) \leq c(p1, p4) + c(p2, p3)\)
令 \(s(l, r, L, R)\) 表示左端点在 \([l, r]\) 且右端点在 \([L, R]\) 的顺序对数量，则：
\(c(p1, p4) - c(p1, p3) = s(p1, p3, p3 + 1, p4) + s(p3 + 1, p4, p3 + 1, p4)\)，记为 \(\Delta1\)
\(c(p2, p4) - c(p2, p3) = s(p2, p3, p3 + 1, p4) + s(p3 + 1, p4, p3 + 1, p4)\)，记为 \(\Delta2\)
那么 \(\Delta1 - \Delta2 = s(p1, p3, p3 + 1, p4) - s(p2, p3, p3 + 1, p4) \geq 0\)
所以四边形不等式成立。
观察发现是 2D/1D 类型的 dp，于是可以考虑单调性分治优化。
问题在于求出 \(c\).
区间数顺序对单次查询可以考虑用树状数组，区间做在不考虑复杂度的情况下可以莫队。然后——
因为分治树的人类智慧性质，直接在分治的时候跑类似莫队状物的复杂度是对的。
void solve(int l, int r, int L, int R)
{
if (l > r) return;
int mid = (l + r) >> 1;
int cost = inf, pos = -1;
for (int i = min(R, mid - 1); i >= L; i--)
{
modify(i + 1, mid);
if (g[i] + cw < cost) cost = g[i] + cw, pos = i;
}
f[mid] = cost;
solve(l, mid - 1, L, pos);
solve(mid + 1, r, pos, R);
}
上面的代码中 modify(i + 1, mid); 代表将莫队的左右端点分别移动到 \(i + 1\) 和 \(mid\)。观察一下，你发现在这里的复杂度是区间长度乘以 \(\log\). 对于下面的递归，递归到左半的复杂度另算，递归到右半时指针会整体向右挪动一次，但是复杂度同上。
于是按普通单调性分治复杂度的证法，这里摊下来只是多一只 \(\log\) 的问题！！！1
时间复杂度 \(O(nk \log^2 n)\)
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 2.5e4 + 5;
const int maxk = 30;
const int inf = 0x3f3f3f3f;
inline int min(const int &a, const int &b) { return (a <= b ? a : b); }
int n, k;
int cl, cr, cw;
int a[maxn];
int f[maxn], g[maxn];
namespace BIT
{
int c[maxn];
int lowbit(int x) { return x & (-x); }
void update(int p, int w) { for (int i = p; i <= n; i += lowbit(i)) c[i] += w; }
int query(int p)
{
int res = 0;
for (int i = p; i; i -= lowbit(i)) res += c[i];
return res;
}
}
void modify(int tl, int tr)
{
while (cl > tl)
{
cw += (cr - cl + 1 - BIT::query(a[--cl]));
BIT::update(a[cl], 1);
}
while (cr < tr)
{
cw += BIT::query(a[++cr] - 1);
BIT::update(a[cr], 1);
}
while (cl < tl)
{
cw -= (cr - cl + 1 - BIT::query(a[cl++]));
BIT::update(a[cl - 1], -1);
}
while (cr > tr)
{
cw -= BIT::query(a[cr--] - 1);
BIT::update(a[cr + 1], -1);
}
}
void solve(int l, int r, int L, int R)
{
if (l > r) return;
int mid = (l + r) >> 1;
int cost = inf, pos = -1;
for (int i = min(R, mid - 1); i >= L; i--)
{
modify(i + 1, mid);
if (g[i] + cw < cost) cost = g[i] + cw, pos = i;
}
f[mid] = cost;
solve(l, mid - 1, L, pos);
solve(mid + 1, r, pos, R);
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
{
BIT::update(a[i], 1);
g[i] = g[i - 1] + BIT::query(a[i] - 1);
}
memset(BIT::c, 0, (n + 1) * sizeof(int));
if (k == 1)
{
printf("%d\n", g[n]);
return 0;
}
cl = 1, cr = 0;
for (int i = 2; i <= k; i++)
{
solve(i, n, i - 1, n);
memcpy(g, f, (n + 1) * sizeof(int));
}
printf("%d\n", f[n]);
return 0;
}