「KTSC 2023 R2」团队建设 题解

问题分析

我们需要在 $Q$ 个场景中，为每个场景找到最优的男女配对，使得团队实力 $(A_1[i] + A_2[j]) \times (B_1[i] + B_2[j])$ 最大。

关键性质：

• 男生：$A_1$ 递增，$B_1$ 递减
• 女生：$A_2$ 递增，$B_2$ 递减
• 数据规模：$N, M, Q \leq 10^5$

核心思路

1. 决策单调性优化

对于固定的女生 $j$，考虑函数 $f(i) = (A_1[i] + A_2[j]) \times (B_1[i] + B_2[j])$。由于男生能力的单调性，存在决策单调性：最优的男生选择随女生编号单调变化。

2. 支配点维护

代码维护的是支配点序列，而不是几何凸包：

• 每个支配点 $(x, j)$ 表示：从男生 $x$ 开始，女生 $j$ 是最优选择
• 支配点具有单调性：随着 $x$ 增大，最优的女生编号也单调变化

代码详解

支配序列构建

inline void build1(int rt, int l, int r) {
    for (int i = l; i <= r; i++) {
        // 维护支配序列：删除被支配的女生
        while (T1[rt].size()) {
            pair<ll, ll> p = T1[rt].back();
            if (F(-p.first, i) > F(-p.first, p.second))
                T1[rt].pop_back();
            else break;
        }
        
        // 添加新的支配点
        if (T1[rt].empty())
            T1[rt].push_back({-n, i});
        else if (F(1, i) > F(1, T1[rt].back().second)) {
            // 二分查找支配边界
            pair<ll, ll> p = T1[rt].back();
            int L = 1, R = -p.first - 1;
            while (L < R) {
                int mid = (L + R) >> 1;
                if (F(mid + 1, p.second) < F(mid + 1, i))
                    L = mid + 1;
                else R = mid;
            }
            T1[rt].push_back({-L, i});
        }
    }
}

支配序列原理：

• 每个元素 {-x, j} 表示：对于男生 $\geq x$，女生 $j$ 比之前的所有女生更优
• 使用栈维护支配序列，保证序列中女生的"优势区间"不重叠

查询处理

inline int ask(int rt, int l, int r, int L, int R, int x) {
    if (L <= l && r <= R) {
        // 在支配序列中二分查找对男生x最优的女生
        auto p = upper_bound(T1[rt].begin(), T1[rt].end(), 
                            make_pair((ll)-x, (ll)m + 1)) - 1;
        return (*p).second;
    }
    
    // 递归处理子区间
    int ret = 0;
    int mid = (l + r) >> 1;
    if (L <= mid) ret = Max(ret, ask(lc, l, mid, L, R, x), x);
    if (R > mid) ret = Max(ret, ask(rc, mid + 1, r, L, R, x), x);
    return ret;
}

算法流程

$1.$ 构建支配序列：为每个女生区间预处理支配关系

$2.$ 收集查询：按男生区间分组存储查询

$3.$ 分层求解：对每个男生区间，求解对应的女生区间查询

$4.$ 合并结果：汇总所有查询答案

复杂度分析

时间复杂度

• 支配序列构建：$O(M \log M)$，每个女生在每层被处理一次
• 查询处理：$O(Q \log N \log M)$
• 总复杂度：$O((M + Q \log N) \log M)$

空间复杂度

• 支配序列：$O(M \log M)$
• 查询存储：$O(Q \log N)$
• 总空间：$O((M + Q) \log N)$

算法优势

$1.$ 利用单调性：基于学生能力的严格单调性质

$2.$ 支配性优化：通过维护支配序列避免无效比较

$3.$ 决策单调性：利用最优配对的单调变化规律

$4.$ 分层处理：通过线段树结构实现高效查询

总结

该解法通过维护支配序列和利用决策单调性，在 $O((M + Q \log N) \log M)$ 的时间内解决了大规模的最优配对问题。虽然思想类似凸包优化，但实际上是基于支配性和单调性的组合优化算法，充分体现了对问题性质的深入理解和巧妙利用。