差分与离散化
https://www.luogu.com.cn/record/176971240 火烧赤壁
前缀和思想:在起火的左端点标注 +1,右端点标注 -1,则做前缀和以后,大于 0 的线段都是起火的,例如:
1[ 0 0 +1 +1 0 -1 -1 0]2[ 0 0 1 2 2 1 0 ]
这里就有长度为 4 的起火段。
由于坐标太大,无法直接前缀和,可以离散化,将大坐标映射到小坐标,即排序 + 去重后用 map 标号,在做前缀和即可。
1n = int(input())2x = []3y = []4for _ in range(n):5 xx, yy = map(int, input().split())6 x.append(xx)7 y.append(yy)8a = sorted(x + y)9b = [a[0]]10for i in range(1, len(a)):11 if a[i] != a[i - 1]:12 b.append(a[i])13di = {}14for i in range(len(b)):15 di[b[i]] = i11 collapsed lines
16pre = [0] * len(b)17for i in range(n):18 pre[di[x[i]]] += 119 pre[di[y[i]]] -= 120ans = 021for i in range(1, len(b)):22 pre[i] += pre[i - 1]23 if pre[i - 1] > 0:24 ans += b[i] - b[i - 1]25
26print(ans)
1n = int(input())2x = []3y = []4for _ in range(n):5 xx, yy = map(int, input().split())6 x.append(xx)7 y.append(yy)8a = sorted(___)9b = [a[0]]10for i in range(1, len(a)):11 if ___:12 b.append(a[i])13di = {}14for i in range(len(b)):15 ___ = i9 collapsed lines
16pre = [0] * len(b)17for i in range(n):18 ___ += 119 ___ -= 120ans = 021for i in range(1, len(b)):22 pre[i] += pre[i - 1]23 if pre[i - 1] > 0:24 ans += ___
T2 # P3029 [USACO11NOV] Cow Lineup S
https://usaco.org/index.php?page=viewproblem2&cpid=89
i 表示当前取的左端点,j 表示右端点。用 map 离散化存储不同品种的奶牛数量。当 i 变动时,向右移动 j 保证奶牛品种数必须为全部品种即可。
作业题 P1904 天际线
https://www.luogu.com.cn/problem/P1904
由于坐标范围很小,可以用 h[i]
表示 i 开始的单位线段所占据的最高楼栋。初值均为 $0$,随后查找 h[i]
变化处输出横纵坐标即可。
1H = [0] * 100052
3while True:4 try:5 a, h, b = map(int, input().split())6 except EOFError:7 break8
9 for i in range(a, b + 1):10 H[i] = max(H[i], h)11
12h = 013for i in range(1, int(1e4)):14 if h != H[i]:15 h = H[i]1 collapsed line
16 print(i, H[i], end=' ')