题目重点：把闭区间结束移到end+1事件，按并发数建立压缩长度前缀，支持巨大时间与零并发。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 整数秒，每过程占[start,end]，每查询也含两端；start≤end，k非负。
- 查询可在所有进程生命周期外，k=0仍须统计；空过程和无查询分别处理。
解题路线
- 事件start:+1,end+1:-1；排序事件点后，在at应用变化，得到[at,next)每个整数秒的并发数k，长度next-at。
- 把相同k的段放进自己的starts/ends列表并累积长度。F_k(t)表示所有这些段中严格小于t的秒数，二分定位最后start≤t段，完整此前段加当前截断长度。
- 查询结果F_k(r+1)-F_k(l)，用r+1统一闭区间。t落两个同k段之间的空隙要截到上一段end，而不是持续加长度。
- horizon与limit覆盖全部过程及所有查询范围，加入0变化端点，从而生命周期前后可形成k=0段。缺此边界会漏整个空闲时段。
- 时间跨度到10^15仍只有O(n)变化段。作者密集差分在小时间范围可行，但不能用maxTime大小开数组解决无界坐标；查询k>n无段自然0。
手动走一遍
训练进程[1,2]与[2,4]，并发1在秒1、3、4，并发2在秒2；query(1,1,4)=3，query(0,0,5)=2，即秒0和5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict
from bisect import bisect_right
def exact_concurrency_seconds(processes,queries):
"""Inclusive integer process intervals and queries (k,left,right)."""
if any(s>e for s,e in processes) or any(k<0 or l>r for k,l,r in queries):
raise ValueError("invalid interval or concurrency")
if not queries:return []
delta=defaultdict(int)
for start,end in processes:
delta[start]+=1
delta[end+1]-=1
horizon=min([l for k,l,r in queries]+[s for s,e in processes])
limit=max([r+1 for k,l,r in queries]+[e+1 for s,e in processes])
delta[horizon]+=0
delta[limit]+=0
points=sorted(delta)
groups={}
active=0
for at,nxt in zip(points,points[1:]):
active+=delta[at]
starts,ends,prefix=groups.setdefault(active,([],[],[0]))
starts.append(at)
ends.append(nxt)
prefix.append(prefix[-1]+nxt-at)
def measure_before(k,time):
if k not in groups:return 0
starts,ends,prefix=groups[k]
i=bisect_right(starts,time)-1
if i<0:return 0
return prefix[i]+min(time,ends[i])-starts[i]
return [measure_before(k,r+1)-measure_before(k,l) for k,l,r in queries]
复杂度
n过程、q查询，O(n log(n+1)+q log(n+1))时间、O(n+q)输入/输出及O(n)段状态，独立于时间数值宽度。
易错点与追问
容易失分的边界
- end处减一漏最后一秒。
- 查询闭区间用F(r)漏r。
- k=0没建外部空闲范围。
- 同k两段间空隙误计。
继续深挖
- 在线新增过程怎样改变索引？
- 连续实数时间应怎样改长度定义？
- 只查高并发区间可否省存部分桶？
