凸优化与决策单调性

最近遇到了一些决策单调性和闵可夫斯基和的题，就慢慢放在这里，顺便学习一下相关的国家集训队论文。

CF1601C

性质：

将一个数 \(x\) 插入到一个数组任意的位置，使新数组逆序对最少的位置（若有多个位置，取最小的位置）\(p[x]\) 关于 \(x\) 单调不减。

证明：记 \(w(i,j)\) 表示把 \(i\) 插入到数组的第 \(j\) 个数后新增的逆序对数，\(p[x]=j\) 表示将 \(x\) 的最优位置是数组的第 \(j\) 个数后。

先证明一个引理，也就是四边形不等式：

\(w(i,j) + w(i+1,j+1) \geq w(i,j+1)+w(i+1,j)\)

上式等价于 \((a[j]<i+1)-(a[j]>i+1) \geq (a[j] < i) - (a[j] > i)\) 。

分类讨论 \(a[j]\) 的取值可以得证。

对两个维度分别归纳可以得到完整的四边形不等式假设 \(a \leq b\) ，\(c \leq d\) 。则有：

\(w(a,c)+w(b,d) \geq w(a,d)+w(b,c)\) 。

考虑反证法:假设存在 \(x<y\) ，使得 \(p[x]>p[y]\) 。

根据 \(p[x]\) 的定义，可以得到： \(w(x,p[x])<w(x,p[y])\) 和 \(w(y,p[y]) \leq w(y,p[x])\) 。

两式相加有：\(w(x,p[x])+w(y,p[y])<w(x,p[y])+w(y,p[x])\) 。这和四边形不等式矛盾，得证！

思路：

这个性质其实就是决策单调性本身，它告诉我们直接插入最优决策点不会让 \(b\) 数组之间的数产生逆序对，是最优的策略。因为这个题在相邻决策点之间的转移很简单，所以可以分治求解。

具体地，考虑 \(sol(l,r,x,y)\) 表示 \([l,r]\) 的最优决策点都在 \([x,y]\) 之间，令 \(mid =(l+r)/2\) 。暴力求出 \(mid\) 的最优决策点 \(pmid\) 。递归到 \(sol(l,mid-1,x,pmid)\) 和 \(sol(mid+1,r,pmid,y)\) 。

求出所有的最优的决策点后构建完整的序列求逆序对即可。

分治结构一共有 \(logm\) 层，每层的复杂度都是 \(O(n)\) 。复杂度为 \(O(nlogm)\) 。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int M = 1e6;

int n, m, a[M + 10], b[M + 10],  p[M + 10];


void sol(int l, int r, int x, int y) {
    if (l > r)return;
    int mid = l + r >> 1;
    int sum = 0, pos = x, ans = 0;
    //[1,x) [x,n+1)
    for (int i = x + 1; i <= y; i++) {
        sum += (a[i - 1] > b[mid]);
        sum -= (a[i - 1] < b[mid]);
        if (sum < ans)pos = i, ans = sum;
    }
    p[mid] = pos;
    sol(l, mid - 1, x, pos);
    sol(mid + 1, r, pos, y);
}

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    //[0,x)
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T query(int l, int r) {
        return sum(r) - sum(l);
    }

    //[0,x)和小于等于k最大的x
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << __lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

void solve()
{

    cin >> n >> m;
    vector<int>v;
    for (int i = 1; i <= n; i++)cin >> a[i], v.push_back(a[i]);
    for (int i = 1; i <= m; i++)cin >> b[i], v.push_back(b[i]);
    sort(v.begin(), v.end());
    sort(b + 1, b + m + 1);
    int c = v.size();
    for (int i = 1; i <= n; i++)a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    for (int i = 1; i <= m; i++)b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
    sol(1, m, 1, n + 1);

    ll res = 0;
    Fenwick<int>tr(c);
    for (int i = 1, j = 1; i <= n + 1; i++) {
        while (j <= m && p[j] <= i)res += tr.query(b[j] + 1, c), tr.add(b[j], 1),j++;
        if (i <= n)res += tr.query(a[i] + 1, c), tr.add(a[i], 1);
    }
    cout << res << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; cin >> t;
    while (t--)solve();
    return 0;
}

洛谷 P4983

简要题意

将序列分成 \(m\) 段，每段的权值为 \((1+\sum_{i=1}^{n}a_i)^2\) ，最小化权值和。

思路分析

先简单介绍下 WQS 二分：当我们确认一个函数是关于某个变量的凸函数时，我们可以通过 WQS 二分获取某点处的值。

具体方法为：每次二分一个斜率，找到该斜率的切线与凸函数的切点横坐标，再根据切点横坐标与我们希望的横坐标的大小关系调整二分区间。二分找到合适的斜率后最后再跑一次求切点的过程即可找出点值。

理由如下：不妨设当前二分的斜率为 \(k\) ，找切点本质上就是找一点 \((x,y)\) 使得 \(y-kx\) 最大或最小。

对于本题，记 \(dp[x]\) 为划分为 \(x\) 段的最小代价，可以证明其是关于 \(x\) 的凸函数，那我们就是希望获取它在 \(m\) 处的点值。

对于如何找 \(x\) 使得 \(dp[x]-kx\) 最小，我们把后面那部分均摊到每一段中，也就是让每一段的代价变为 \((1+\sum_{i=1}^{n}a_i)^2-k\) 。在这种情况下，记 \(f[i]\) 表示前 \(i\) 个数的所有划分方案中的最小代价，\(g[i]\) 表示相应的划分段数（有多个取最小），那么 \(g[n]\) 就是我们要找的切点横坐标。同时最后也可以通过 \(f[i]\) 确定最开始的代价为： \(f[i]+k*g[i]\) 。

考虑 \(f[i]\) 的转移，枚举上一段的终点 \(j(0 \leq j < i)\) ，其中 \(j\) 取 \(0\) 表示不存在上一段，得 \(f[i]=min(f[j]+(1+s[i]-s[j])^2+k)\) ，这是个经典的斜率优化 dp 。于是问题就解决了。

最后提一下为什么可以在整数域上二分，因为相邻的两点横坐标之差为 \(1\) ，这就保证了这条线段的斜率为整数，于是我们总能找到一条斜率为整数的切线符合我们的条件。

实际上要保证多种方案选择最小的点有很多需要讨论的地方，所有下面这份代码还不算太完善。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 10;

int n, m, a[N], g[N];
int q[N], hh, tt;
ll f[N], s[N];

ll c(int x) {

    return f[x] + s[x] * s[x] - 2 * s[x];
}

long double slope(int i, int j) {
    return (long double)(c(i) - c(j)) / (s[i] - s[j]);
}

bool check(ll k) {
    hh = tt = q[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (hh > tt && slope(q[tt], q[tt + 1]) <= 2 * s[i] )tt++;
        int j = q[tt];
        f[i] = f[j] + (1 + s[i] - s[j]) * (1 + s[i] - s[j]) - k;
        g[i] = g[j] + 1;
        while (hh > tt && slope(i, q[hh]) < slope(q[hh], q[hh - 1]))hh--;
        q[++hh] = i;
    }
    return g[n] >= m;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];
    ll l = -1e18, r = 1e18;
    while (l < r) {
        ll mid = l + (r - l) / 2;
        if (check(mid))r = mid;
        else l = mid + 1;
    }
    check(l);

    cout << f[n] + m * l << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}