The 2nd Universal Cup. Stage 3: Binjiang L. Partially Free Meal

_YangZJ_ · 2023-10-06 21:05:38 · 个人记录

提供一个常数小且好写的做法。

首先对于序列按照 b 从小到大排序，考虑分治，在每个区间处理左右都选择点对的贡献，再和左右两侧的答案取 \min ，就可以得到这个区间的答案。

首先递归右区间，这样右边的答案已经处理好了，考虑如何与左边的合并。

此时由于右区间有选择点，那么 \max 一定在右区间里，左区间的贡献就是直接按照 a 排序后从小到大选即可。

那么问题变为，给定两个序列：s_0,s_1,s_2,...;f_1,f_2,... ，s 序列是左区间按照 a 从小到大排序之后的前缀和，f 是右区间求解出来的答案，要求：

后面是个 \min 卷积的形式，直接做不得，观察左边 s 由于有 a 不降，因此 s 相邻两项的差值不降，换言之左边的序列是一个凸包的形式。

有了这个性质，考察 f_j,f_{j+1} 对 g_i 的贡献，发现随着 i 变大，f_j 的贡献会变得更优，因此 g 的转移对于 f 具有决策单调性。

在每个区间更新的时候再用一个分治来做决策单调性得到 g 即可。

code

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define mkp make_pair
#define pii pair<int,int>
#define vc vector
#define pb emplace_back

const int N = 2e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch=='-'), ch = getchar();
    while(isdigit(ch)) x = (x*10)+(ch^48), ch=getchar(); return w?-x:x;
}

int n;
pii a[N];
ll f[N], g[N], dp[N], lf, lg, ldp;

inline void merge(int l, int r, int L, int R) {
    int mid = l + r >> 1, p = -1; dp[mid] = inf;
    for(int i = L, j = mid - L; i <= R; i++, j--) if(j >= 0 && j <= lg && g[j] + f[i] < dp[mid]) 
        dp[mid] = g[j] + f[i], p = i;
    if(l < r) merge(l, mid, L, p), merge(mid + 1, r, p, R);
}

inline vc<ll> solve(int l, int r) {
    if(l == r) {
        vc<ll> res(2); res[1] = a[l].first + a[l].second;
        return res;
    }
    int mid = l + r >> 1; 

    auto R = solve(mid + 1, r); lf = R.size() - 1; g[lg = 0] = 0;
    for(int i = 0; i <= lf; i++) f[i] = R[i];
    for(int i = l; i <= mid; i++) g[++lg] = a[i].second;
    sort(g + 1, g + 1 + lg);
    for(int i = 1; i <= lg; i++) g[i] += g[i - 1];

    merge(1, ldp = r - l + 1, 1, lf); 

    vc<ll> res(ldp + 1, 0);
    for(int i = 0; i <= ldp; i++) res[i] = dp[i];
    auto L = solve(l, mid);
    for(int i = 0; i < L.size(); i++) res[i] = min(res[i], L[i]);

    return res;
}

signed main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i].second = read(), a[i].first = read();
    sort(a + 1, a + 1 + n);
    auto ans = solve(1, n);
    for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);   
    return 0;
}