UVa 12663 High Bridge Low Bridge

题目描述

河上有nnn座桥，每座桥有一个高度hih_ihi​。河水会泛滥mmm次，每次洪水会将水位从上次洪水结束后的高度bi−1b_{i-1}bi−1​上升到aia_iai​，然后回落到bib_ibi​。初始水位为111。

题目规定：如果一座桥在洪水结束后仍然在水下（即水位不低于桥的高度），那么下次洪水时它不会被视为再次被淹。也就是说，每次洪水只记录上升阶段（水位从bi−1b_{i-1}bi−1​上升到aia_iai​期间）被淹的桥。

给定nnn座桥的高度和mmm次洪水的数据，求有多少座桥至少被淹了kkk次。

输入格式

输入最多包含252525个测试用例。每个测试用例的第一行包含三个整数n,m,kn, m, kn,m,k（1≤n,m,k≤1051 \leq n, m, k \leq 10^51≤n,m,k≤105）。第二行包含nnn个整数hih_ihi​，表示每座桥的高度（2≤hi≤1082 \leq h_i \leq 10^82≤hi​≤108）。接下来的mmm行每行包含两个整数aia_iai​和bib_ibi​（1≤bi<ai≤108,ai>bi−11 \leq b_i < a_i \leq 10^8, a_i > b_{i-1}1≤bi​<ai​≤108,ai​>bi−1​）。整个输入的文件大小不超过5MB5\text{MB}5MB。

输出格式

对于每个测试用例，输出至少被淹了kkk次的桥的数量。

题目分析

核心逻辑

对于第iii次洪水：

• 洪水开始前的水位是bi−1b_{i-1}bi−1​（第一次洪水前b0=1b_0 = 1b0​=1）
• 水位上升到aia_iai​
• 然后回落到bib_ibi​

桥被淹的条件：在上升阶段，水位超过了桥的高度，即bi−1<h≤aib_{i-1} < h \leq a_ibi−1​<h≤ai​。
为什么不是bib_ibi​？因为下降阶段不影响本次是否被淹的记录，只影响下次洪水是否算作“再次被淹”。

关键点

1. 只考虑上升阶段：题目描述中的文字游戏关键就在于，下降阶段不影响计数，只影响下次判断。
2. 区间更新：对于每次洪水，需要给所有高度在(bi−1,ai](b_{i-1}, a_i](bi−1​,ai​]范围内的桥的计数+1+1+1。
3. 高效处理：直接遍历每座桥更新会超时（O(nm)O(nm)O(nm)），需要使用差分技巧。

算法步骤

1. 将桥的高度排序，以便二分查找。
2. 使用差分数组记录每座桥被淹的次数。
3. 遍历每次洪水：
   • 用二分查找找到高度>bi−1> b_{i-1}>bi−1​的第一个桥的索引leftleftleft
   • 用二分查找找到高度≤ai\leq a_i≤ai​的最后一个桥的索引rightrightright
   • 如果left≤rightleft \leq rightleft≤right，则在差分数组中标记区间[left,right][left, right][left,right]加111
4. 通过差分数组前缀和计算每座桥的实际被淹次数。
5. 统计次数≥k\geq k≥k的桥的数量。

时间复杂度

• 排序桥高度：O(nlog⁡n)O(n \log n)O(nlogn)
• 每次洪水二分查找：O(log⁡n)O(\log n)O(logn)，总O(mlog⁡n)O(m \log n)O(mlogn)
• 前缀和统计：O(n)O(n)O(n)
• 总复杂度：O((n+m)log⁡n)O((n+m) \log n)O((n+m)logn)，可以处理10510^5105的数据规模。

空间复杂度

• 存储桥高度和差分数组：O(n)O(n)O(n)

代码实现

// High Bridge Low Bridge// UVa ID: 12663// Verdict: Accepted// Submission Date: 2025-12-23// UVa Run Time: 0.040s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100010;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcaseNo=1;intn,m,k;intbridgeHeight[MAXN],diff[MAXN];inta,b;while(cin>>n>>m>>k){for(inti=0;i<n;i++){cin>>bridgeHeight[i];diff[i]=0;}sort(bridgeHeight,bridgeHeight+n);intlastWaterLevel=1;// 初始水位为1，也是第一次洪水前的b₀for(inti=0;i<m;i++){cin>>a>>b;// 本次洪水影响：高度在 (lastWaterLevel, a] 范围内的桥// 使用 upper_bound 找到第一个 > lastWaterLevel 的桥// 使用 upper_bound 找到第一个 > a 的桥，然后-1得到最后一个 ≤ a 的桥intleft=upper_bound(bridgeHeight,bridgeHeight+n,lastWaterLevel)-bridgeHeight;intright=upper_bound(bridgeHeight,bridgeHeight+n,a)-bridgeHeight-1;if(left<=right){diff[left]++;diff[right+1]--;}lastWaterLevel=b;// 更新为本次洪水结束后的水位}// 计算每座桥被淹的次数intcurrentFloodCount=0;intanswer=0;for(inti=0;i<n;i++){currentFloodCount+=diff[i];if(currentFloodCount>=k)answer++;}cout<<"Case "<<caseNo++<<": "<<answer<<'\n';}return0;}

样例解释

样例111

输入： 2 2 2 2 5 6 2 8 3

• 桥高度：2,52, 52,5
• 第111次洪水：影响(1,6](1, 6](1,6]→ 桥2,52, 52,5各+1+1+1
• 第222次洪水：影响(2,8](2, 8](2,8]→ 桥555+1+1+1（桥222高度为222，不在(2,8](2,8](2,8]区间）
• 统计：桥222被淹111次，桥555被淹222次
• 输出：111（只有桥555被淹≥2\geq 2≥2次）

样例222

输入： 5 3 2 2 3 4 5 6 5 3 4 2 5 2

• 桥高度：2,3,4,5,62, 3, 4, 5, 62,3,4,5,6
• 第111次洪水：影响(1,5](1, 5](1,5]→ 桥2,3,4,52,3,4,52,3,4,5各+1+1+1
• 第222次洪水：影响(3,4](3, 4](3,4]→ 桥444+1+1+1
• 第333次洪水：影响(2,5](2, 5](2,5]→ 桥3,4,53,4,53,4,5各+1+1+1
• 统计：桥2:12:12:1次，桥3:23:23:2次，桥4:34:34:3次，桥5:25:25:2次，桥6:06:06:0次
• 输出：333（桥3,4,53,4,53,4,5被淹≥2\geq 2≥2次）

总结

本题的关键在于理解题目描述中的文字游戏：每次洪水只记录上升阶段被淹的桥，下降阶段只影响下次是否算作“再次被淹”。
通过将桥高度排序并使用差分技巧，可以高效地处理区间更新问题。
注意数据范围较大，需要使用O((n+m)log⁡n)O((n+m) \log n)O((n+m)logn)的算法才能通过。