题目分析

本题要求计算在满足明星档期限制和比赛安排规则的所有最优方案中，门票收入的中位数。

关键观察

1. 比赛类型限制：Lewis 只与 Valtteri 比赛，因此可能的对阵只有四种：

   • Lewis vs Valtteri（收入 $a_i$）
   • Valtteri vs Max（收入 $b_i$）
   • Valtteri vs Checo（收入 $b_i$）
   • Max vs Checo（收入 $c_i$）

2. 明星档期限制：Max 和 Checo 的出场必须是连续区间，长度分别不超过 $t_m$ 和 $t_c$

3. 最优方案定义：无法通过修改任意一场比赛获得严格更大收入的方案

算法思路

核心思想：区间划分 + 二维数点 + 二分答案

状态设计：

• 用 $[p_m, q_m]$ 表示 Max 的出场区间，$q_m - p_m + 1 \le t_m$
• 用 $[p_c, q_c]$ 表示 Checo 的出场区间，$q_c - p_c + 1 \le t_c$

收入计算： 对于确定的区间 $[p_m, q_m]$ 和 $[p_c, q_c]$，收入为：

• 交集部分：安排 Max vs Checo，收入 $\sum c_i$
• Max 单独出场：安排 Valtteri vs Max，收入 $\sum b_i$
• Checo 单独出场：安排 Valtteri vs Checo，收入 $\sum b_i$
• 都不出场：安排 Lewis vs Valtteri，收入 $\sum a_i$

算法步骤

1. 预处理前缀和：

   a[i] = a[i-1] + a_i  // Lewis vs Valtteri 收入前缀和
   b[i] = b[i-1] + b_i  // 明星参与比赛收入前缀和  
   c[i] = c[i-1] + c_i  // 明星对决收入前缀和
   

2. 分情况处理区间关系： 根据两个区间的相对位置，分为5种情况：

   • 情况1：区间相交或相邻
   • 情况2：Max 区间在 Checo 区间左侧且不重叠
   • 情况3：Checo 区间在 Max 区间左侧且不重叠
   • 情况4：部分重叠的特殊情况
   • 情况5：另一种部分重叠情况

3. 二维数点统计： 对于每种情况，将问题转化为：

   • 固定 Max 区间 $[i, i+L_m-1]$
   • 寻找 Checo 区间 $[j, j+L_c-1]$ 满足位置约束
   • 计算对应的收入值

4. 二分求中位数：

   long long kth(long long k) {
       long long cur = 0;
       for (long long i = 1LL << 50; i; i >>= 1) {
           long long res = 0;
           for (每种情况) res += 收入小于 cur+i 的方案数;
           if (res < k) cur += i;
       }
       return cur;
   }
   

关键技巧

1. 树状数组优化

使用带标记清除的树状数组高效统计满足条件的区间对：

class TreeArr {
    long long d[200005];
    int tag, t[200005];
    // 使用tag机制避免memset，提高效率
};

2. 双指针+排序

对每种情况的区间对按收入排序，使用双指针统计：

void build() {
    sort(a[] by x descending);  // 按收入降序
    sort(b[] by x ascending);   // 按收入升序
}

long long query(long long x) {
    int r = mnj;
    for (每个a[i]) {
        while (b[r].x + a[i].x < x) 
            tree.update(b[r].idx, 1), r++;
        ret += tree.query(a[i].l, a[i].r);
    }
}

3. 中位数计算

根据方案总数的奇偶性：

• 奇数：第 $(sum+1)/2$ 小的收入值
• 偶数：第 $sum/2$ 小和第 $sum/2+1$ 小的收入值的平均数

复杂度分析

时间复杂度：

• 预处理：$O(n)$
• 排序：$O(n \log n)$，最多5种情况
• 二分答案：$O(50 \times 5 \times n \log n) \approx O(250n \log n)$
• 总复杂度：$O(n \log n)$，在 $n \le 2\times 10^5$ 时可接受

空间复杂度：$O(n)$，存储前缀和及临时数组

算法正确性

1. 完备性：5种情况覆盖了所有可能的区间相对位置
2. 最优性：通过二分准确找到中位数位置
3. 高效性：树状数组和双指针优化确保在大数据下的性能

样例验证

样例1：

输入：2 1 1
      1 10 100  
      1 2 3
输出：12.0

4种最优方案收入：101, 12, 12, 4，中位数为12.0

样例2：

输入：3 1 3  
      1 2 3
      5 6 12
      1 5 6
输出：14.0

该算法通过精细的区间划分和高效的数据结构，成功解决了大规模数据下的中位数计算问题。