题解

问题分析

这是一个图论 + 区间覆盖 + 最优化问题。我们需要判断每个游客是否可以通过交换通票（花费一定手续费）来获得能够从车站 $1$ 到达所有车站的通行权限。

关键观察

1. 可达性条件：通票 $(l, r)$ 能够到达所有车站，当且仅当包含的路线能够形成从 $1$ 到所有车站的路径
2. 双指针思想：对于固定的左端点 $l$，找到最小的 $r$ 使得通票 $(l, r)$ 满足条件（记为 $f(l)$）
3. 对称性：对于固定的右端点 $r$，找到最大的 $l$ 使得通票 $(l, r)$ 满足条件（记为 $g(r)$）

算法思路

离散化 + 双指针 + 线段树优化：

离散化处理

• 将所有公司编号和查询的 $L_j, R_j$ 一起离散化，减少值域

双指针预处理

1. $f(i)$：对于离散化后的左端点 $i$，最小的右端点使得通票 $(i, f(i))$ 能到达所有车站
2. $g(j)$：对于离散化后的右端点 $j$，最大的左端点使得通票 $(g(j), j)$ 能到达所有车站

线段树维护

• 用线段树维护对于每个左端点 $i$，满足条件的最小花费：$ls[f(i)] - ls[i]$
• 支持区间最小值查询和单点修改

核心数据结构

双指针扫描

for(int i=1, j=1; i<=lsc; ++i) {
    while(j<=lsc && cnt<n) {
        for(auto z:vc[j]) {  // 添加公司j的所有路线
            cnt += !ct[z];
            ct[z]++;
        }
        g[j] = i-1;
        j++;
    }
    if(cnt < n) break;
    f[i] = j-1;
    // 移除公司i的路线
    for(auto z:vc[i]) {
        ct[z]--;
        cnt -= !ct[z];
    }
    E[j-1].push_back(i);
}

线段树查询

// 查询区间[1,l]的最小花费
ans[id] = Ask(1, 1, lsc, 1, l);  
// 考虑对称情况
if(g[i]) ans[id] = min(ans[id], (ll)ls[i] - ls[g[i]]);

算法步骤

1. 离散化：将所有公司编号和查询端点映射到 $[1, lsc]$
2. 预处理：按公司编号分组存储路线终点
3. 双指针扫描：计算 $f(i)$ 和 $g(j)$
4. 线段树处理查询：
   • 按右端点排序查询
   • 维护当前可用的左端点花费
   • 回答每个查询的最小交换花费
5. 判断答案：比较最小花费与可用现金

复杂度分析

• 离散化：$O((M+Q)\log(M+Q))$
• 双指针：$O(M + N)$，每个路线被加入/移除一次
• 线段树：$O(Q\log M)$ 处理所有查询
• 总复杂度：$O((M+Q)\log(M+Q))$

判断逻辑

对于查询 $(L_j, R_j, X_j)$：

• 如果原通票就满足条件：直接输出 Yes
• 否则检查最小交换花费是否 $\leq X_j$：
  • 花费 = $\min(ls[f(l)] - ls[l], ls[r] - ls[g(r)])$
  • 其中 $l, r$ 是离散化后的位置

算法标签

• 离散化
• 双指针
• 线段树
• 图的可达性
• 区间覆盖
• 最优化问题