5125: [Lydsy1712月赛]小Q的书架 [决策单调性]

很显然的dp式子
(dp_i = dp_j + calc(j + 1,i))

然后发现这个 (calc(i-1,j+1) + calc(i,j) geq calc(i-1,j) + calc(i,j+1))

满足四边形不等式，然后就可以决策单调性，区间逆序对搞个莫队就完了。

#include <bits/stdc++.h>

using namespace std;

template <int maxn>
struct BIT {
  int c[maxn];
  int low(int x) { return x & -x; }
  void add(int x, int y) {
    for (; x < maxn; x += low(x)) c[x] += y;
  }
  int qry(int x) {
    int ans = 0;
    for (; x; x ^= low(x)) ans += c[x];
    return ans;
  }
};

int n, k;
const int maxn = 4e4 + 44;
BIT<maxn> bit;
int a[maxn], f[maxn], g[maxn];

int l, r, ans = 0;
void modify(int ql, int qr) {
  while (l < ql) {
    bit.add(a[l], -1);
    ans -= bit.qry(a[l++] - 1);
  }
  while (l > ql) {
    bit.add(a[--l], 1);
    ans += bit.qry(a[l] - 1);
  }
  while (r < qr) {
    bit.add(a[++r], 1);
    ans += bit.qry(n) - bit.qry(a[r]);
  }
  while (r > qr) {
    bit.add(a[r], -1);
    ans -= bit.qry(n) - bit.qry(a[r--]);
  }
}

void solve(int l, int r, int L, int R) {
  if (l > r) return;
  int mid = l + r >> 1, p;
  for (int i = min(mid - 1, R); i >= L; --i) {
    modify(i + 1, mid);
    if (g[i] + ans < f[mid]) f[mid] = g[i] + ans, p = i;
  }
  solve(l, mid - 1, L, p);
  solve(mid + 1, r, p, R);
}

signed main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  l = 1, r = 0;
  for (int i = 1; i <= n; i++) {
    modify(1, i), f[i] = ans;
  }
  for (int i = 2; i <= k; i++) {
    for (int j = 1; j <= n; j++) g[j] = f[j];
    for (int j = 1; j <= n; j++) f[j] = 1e9;
    solve(1, n, 1, n);
  }
  printf("%d
", f[n]);
  return 0;
}