「KTSC 2022 R2」编程测试 题解

题目分析

本题要求我们为每个查询区间 $[L_j, U_j]$ 计算最大可组成的比赛数量。关键在于处理那些难度不确定的题目（$B[i]$），它们可以灵活分配为 $i$ 级或 $i+1$ 级。

核心思路

通过前缀和转换，我们将原问题转化为在二维平面上求最小斜率的问题：

• 定义 $a[i]$ 为前 $i$ 级固定难度题目的累计数量
• 定义 $b[i]$ 为考虑 $B[i-2]$ 不确定题目时的特殊值
• 对于区间 $[l, r]$，最大比赛数等于 $\min\left\{\frac{a[j] - b[i]}{j-i}\right\}$，其中 $l \leq i < j \leq r$

算法实现

采用分治+凸包的方法高效处理所有查询：

#include "codingtest.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int n, m, sta[N], top, fa[N], f[N][20], dep[N];
ll a[N], b[N];
vector<int> ans;
vector<tuple<int, int, int>> Q[N << 2];

// 将查询分配到分治线段树中
void pushseg(int x, int l, int r, int L, int R, int id) {
    int mid = (l + r) >> 1;
    if (L <= mid && R > mid) {
        Q[x].emplace_back(L, R, id);
        return;
    }
    if (R <= mid) pushseg(x * 2, l, mid, L, R, id);
    else pushseg(x * 2 + 1, mid + 1, r, L, R, id);
}

关键优化

在分治过程中，我们维护左右两侧的凸包来快速计算最小斜率：

// 在分治区间内处理查询
void solve(int x, int l, int r) {
    int mid = (l + r) >> 1;
    if (l == r) return;
    
    solve(x * 2, l, mid);
    solve(x * 2 + 1, mid + 1, r);
    
    if (Q[x].empty()) return;
    
    // 构建左侧凸包并预处理最小斜率
    top = 0;
    for (int i = mid; i >= l; i--) {
        // 维护凸包性质
        while (top >= 2 && (a[sta[top-1]] - a[sta[top]]) * (sta[top] - i) 
               <= (a[sta[top]] - a[i]) * (sta[top-1] - sta[top])) {
            top--;
        }
        sta[++top] = i;
    }
    
    // 类似处理右侧凸包
    // ...
    
    // 处理当前节点的所有查询
    for (auto [ql, qr, id] : Q[x]) {
        ans[id] = min({ans[id], mnl[ql], mnr[qr], query(ql, qr)});
    }
}

主函数实现

vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U) {
    n = A.size();
    ans.resize(L.size(), (int)1e9);
    
    // 预处理前缀和数组
    for (int i = 2; i <= n + 1; i++) a[i] += A[i - 2];
    for (int i = 2; i <= n; i++) a[i] += B[i - 2];
    for (int i = 2; i <= n + 1; i++) a[i] += a[i - 1];
    for (int i = 2; i <= n; i++) b[i] = a[i] - B[i - 2];
    
    // 分配查询到分治结构中
    m = L.size();
    for (int i = 0; i < m; i++) {
        pushseg(1, 1, n + 1, L[i] + 1, U[i] + 2, i);
    }
    
    solve(1, 1, n + 1);
    return ans;
}

算法复杂度

• 时间复杂度：$O((N+M)\log^2 N)$，分治过程中每个节点构建凸包和回答查询都是 $O(\text{区间长度})$ 或 $O(\log N)$
• 空间复杂度：$O(N\log N)$，用于存储分治结构和凸包信息

总结

本题通过巧妙的数学转换，将原问题转化为几何中的最小斜率问题，再利用分治凸包技术高效解决。这种分治+凸包的技巧在处理区间最值查询问题时非常有效，特别是在需要维护某种单调性的场景下。