题解：P11587 [KTSC 2022 R2] 编程测试

· · 题解

本文默认下标从 1 开始。

考虑这个复杂度很大的算法：先二分答案，检查函数中建网络流判断是否流满。

这个算法显然是正确的，并且它启示我们这个题相当于匹配问题，我们尝试用 Hall 定理分析出充要条件：

不难发现这个结论和 Hall 定理是等价的。

于是我们有式子：

\dfrac{(a_r - a_{l - 1}) + (b_r - b_{l - 2})}{r - l + 1} \geq x

其中 a, b 已做前缀和处理，且 a_0 = b_0 = a_{-1} = b_{-1} = 0。

这个式子中的 l, r 相关性太强了，把它拆开：

(1 - l)x + (a_{l - 1} + b_{l - 2}) \leq (-r)x + (a_r + b_r)

可以发现每个点作为左端点和右端点时分别对应了一条直线，“[l, r] 中的平均数不小于 x”就可以用上面这个式子表示。

我们发现部分分正好有 l_i = 1，可以二分 + 李超线段树解决，现在已经能得 77 分了，是考场最高分。

进一步受到这个部分分启发，我们发现好像可以套一个分治。具体的，跑一遍猫树，假设当前区间 [L, R]，中点 mid，有一个询问 [l, r] 被 mid 切开。我们计算下面几个值，就可以得到 [l, r] 的答案：

这三个值取 \min 就是答案了。前两个可以直接算，后一个用二分 + 可持久化李超线段树解决。这样复杂度是 O(n\log^2 n)。

 /* NE_Cat 4.15 */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010;
const long long INF = 2e16, mx = 400000000;
int n, m; long long a[N], b[N], pr_a[N], pr_b[N];
struct Range {int l, r, id;}; long long res[N];

int rt[N], idx, Root; long long f[N];
inline long long get_r(int p) {return pr_a[p] + pr_b[p];}
inline long long get_l(int p) {return pr_a[p - 1] + ((p == 1) ? 0 : pr_b[p - 2]);}
struct Line
{
    long long k, b;
    inline long long calc(long long x) {return k * x + b;}
};
inline Line get_line_l(int p) {return {1 - p, get_l(p)};}
inline Line get_line_r(int p) {return {-p, get_r(p)};}
struct SGT
{
    int ls, rs; Line maxn, minn; bool tag_mx, tag_mn;
    #define ls(x) tree[x].ls
    #define rs(x) tree[x].rs
    #define maxn(x) tree[x].maxn
    #define minn(x) tree[x].minn
    #define tag_mx(x) tree[x].tag_mx
    #define tag_mn(x) tree[x].tag_mn
} tree[N * 60];
inline void insert_mx(int &now, int his, int l, int r, Line cur)
{
    now = ++idx; tree[now] = tree[his];
    if(!tag_mx(now)) {tag_mx(now) = true; maxn(now) = cur; return ;}
    int mid = (l + r) >> 1;
    if(maxn(now).calc(mid) < cur.calc(mid)) swap(maxn(now), cur);
    if(l == r) return ;
    if(cur.calc(l) > maxn(now).calc(l)) insert_mx(ls(now), ls(his), l, mid, cur);
    if(cur.calc(r) > maxn(now).calc(r)) insert_mx(rs(now), rs(his), mid + 1, r, cur);
}
inline void insert_mn(int &now, int his, int l, int r, Line cur)
{
    now = ++idx; tree[now] = tree[his];
    if(!tag_mn(now)) {tag_mn(now) = true; minn(now) = cur; return ;}
    int mid = (l + r) >> 1;
    if(minn(now).calc(mid) > cur.calc(mid)) swap(minn(now), cur);
    if(l == r) return ;
    if(cur.calc(l) < minn(now).calc(l)) insert_mn(ls(now), ls(his), l, mid, cur);
    if(cur.calc(r) < minn(now).calc(r)) insert_mn(rs(now), rs(his), mid + 1, r, cur);
}
inline long long query_mx(int now, int l, int r, int pos)
{
    if(!now) return -INF;
    long long res = (tag_mx(now) ? maxn(now).calc(pos) : -INF);
    if(l == r) return res;
    int mid = (l + r) >> 1;
    if(pos <= mid) return max(res, query_mx(ls(now), l, mid, pos));
    else return max(res, query_mx(rs(now), mid + 1, r, pos));
}
inline long long query_mn(int now, int l, int r, int pos)
{
    if(!now) return INF;
    long long res = (tag_mn(now) ? minn(now).calc(pos) : INF);
    if(l == r) return res;
    int mid = (l + r) >> 1;
    if(pos <= mid) return min(res, query_mn(ls(now), l, mid, pos));
    else return min(res, query_mn(rs(now), mid + 1, r, pos));
}

inline void solve(int l, int r, vector < Range > q)
{
    int mid = (l + r) >> 1;

    Root = idx = 0;
    for(int i = mid + 1; i <= r; ++i)
    {
        insert_mx(Root, Root, 0, mx, {1 - i, get_l(i)});
        long long l = 0, r = 4e8; f[i] = 0;
        while(l <= r)
        {
            long long mid = (l + r) >> 1;
            if((-i) * mid + get_r(i) >= query_mx(Root, 0, mx, mid)) f[i] = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(i > mid + 1) f[i] = min(f[i], f[i - 1]);
    }
    Root = idx = 0;
    for(int i = mid; i >= l; --i)
    {
        insert_mn(Root, Root, 0, mx, {-i, get_r(i)});
        long long l = 0, r = 4e8; f[i] = 0;
        while(l <= r)
        {
            long long mid = (l + r) >> 1;
            if((1 - i) * mid + get_l(i) <= query_mn(Root, 0, mx, mid)) f[i] = mid, l = mid + 1;
            else r = mid - 1;
        }
        if(i < mid) f[i] = min(f[i], f[i + 1]);
    }

    idx = 0;
    for(int i = l; i <= r; ++i) rt[i] = 0;
    insert_mn(rt[mid + 1], rt[mid + 1], 0, mx, get_line_r(mid + 1));
    for(int i = mid + 2; i <= r; ++i)
        insert_mn(rt[i], rt[i - 1], 0, mx, get_line_r(i));
    insert_mx(rt[mid], rt[mid], 0, mx, get_line_l(mid));
    for(int i = mid - 1; i >= l; --i)
        insert_mx(rt[i], rt[i + 1], 0, mx, get_line_l(i));
    for(Range qy : q)
    {
        if(qy.l <= mid && qy.r > mid)
        {
            res[qy.id] = min(f[qy.l], f[qy.r]);
            long long l = 0, r = 4e8, cur = 0;
            while(l <= r)
            {
                long long mid = (l + r) >> 1;
                if(query_mx(rt[qy.l], 0, mx, mid) <= query_mn(rt[qy.r], 0, mx, mid)) cur = mid, l = mid + 1;
                else r = mid - 1;
            }
            res[qy.id] = min(res[qy.id], cur);
        }
    }

    if(l == r) return ;
    vector < Range > qL, qR;
    for(Range qy : q)
    {
        if(qy.r <= mid) qL.push_back(qy);
        if(qy.l > mid) qR.push_back(qy);
    }
    q.clear(); q.shrink_to_fit();
    solve(l, mid, qL), solve(mid + 1, r, qR);
}

std::vector<int> testset(std::vector<int> A, std::vector<int> B, std::vector<int> L, std::vector<int> U)
{
    n = A.size(); m = L.size();
    for(int i = 1; i <= n; ++i) a[i] = A[i - 1];
    for(int i = 1; i < n; ++i) b[i] = B[i - 1];
    for(int i = 1; i <= n; ++i)
    {
        pr_a[i] = pr_a[i - 1] + a[i];
        pr_b[i] = pr_b[i - 1] + b[i];
    }
    memset(res, 0x3f, sizeof(res));
    vector < Range > q;
    for(int i = 1; i <= m; ++i)
    {
        int l = L[i - 1], r = U[i - 1]; ++l, ++r;
        if(l == r) res[i] = a[l] + b[l] + b[l - 1];
        q.push_back({l, r, i});
    }
    solve(1, n, q);
    vector < int > rec;
    for(int i = 1; i <= m; ++i) rec.push_back(res[i]);
    return rec;
}
/*
3 1
3 0 3 
4 4 
0 2
*/