Skip to content

教学计划 差分与离散化

差分与离散化

https://www.luogu.com.cn/record/176971240 火烧赤壁

前缀和思想：在起火的左端点标注 +1，右端点标注 -1，则做前缀和以后，大于 0 的线段都是起火的，例如：

[ 0  0 +1 +1  0 -1 -1 0]
[ 0  0  1  2  2  1  0 ]

这里就有长度为 4 的起火段。

由于坐标太大，无法直接前缀和，可以离散化，将大坐标映射到小坐标，即排序 + 去重后用 map 标号，在做前缀和即可。

n = int(input())
x = []
y = []
for _ in range(n):
    xx, yy = map(int, input().split())
    x.append(xx)
    y.append(yy)
a = sorted(x + y)
b = [a[0]]
for i in range(1, len(a)):
    if a[i] != a[i - 1]:
        b.append(a[i])
di = {}
for i in range(len(b)):
    di[b[i]] = i
pre = [0] * len(b)
for i in range(n):
    pre[di[x[i]]] += 1
    pre[di[y[i]]] -= 1
ans = 0
for i in range(1, len(b)):
    pre[i] += pre[i - 1]
    if pre[i - 1] > 0:
        ans += b[i] - b[i - 1]

print(ans)

n = int(input())
x = []
y = []
for _ in range(n):
    xx, yy = map(int, input().split())
    x.append(xx)
    y.append(yy)
a = sorted(___)
b = [a[0]]
for i in range(1, len(a)):
    if ___:
        b.append(a[i])
di = {}
for i in range(len(b)):
    ___ = i
pre = [0] * len(b)
for i in range(n):
    ___ += 1
    ___ -= 1
ans = 0
for i in range(1, len(b)):
    pre[i] += pre[i - 1]
    if pre[i - 1] > 0:
        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] 变化处输出横纵坐标即可。

H = [0] * 10005

while True:
    try:
        a, h, b = map(int, input().split())
    except EOFError:
        break 

    for i in range(a, b + 1):
        H[i] = max(H[i], h)

h = 0
for i in range(1, int(1e4)):
    if h != H[i]:
        h = H[i]
        print(i, H[i], end=' ')