题目描述

本来有很多想说的，这道题对于初学的我很痛苦，相信你看到也是。痛苦在，扫描线是什么?离散化是什么?动态维护一个什么?怎么计算面积等等.，还有考虑覆盖的情况。
一开始直接看视频，用线段树，当时头很大，都还没看到线段树真正登场就看不下去了。其实最后发现，线段树只是一个工具，用于动态维护的工具，不难，类似于这里维护这个cnt的更新一样。难的是，标题里的这三个的结合。我去蓝桥官网上看了，标签也是线段树，但差分就可以解决。如下面所示，我只展示了代码。不要恼怒，因为这时讲太多也是无用的，你需要去把这上面所有问题解决才能看懂代码。我在这上面花了一天一夜。最后在这里解释一些难题。，离散化是为了将有需要的循环才循环。可能样本个数很少，很离散。这个是模板来的，其他地方可以套用。扫描线就是沿着y轴或x轴去扫描，每次计算覆盖的长度，再乘以y的变化值就可以计算面积。聪明的你想到了，那是不是从0-10000去扫呢，也可以，但没必要。用事件的概念，嗯嗯，就是只有事件发生时才去考虑，其余时间是不用管的，也就减少了循环数，得到的是2k的循环，k是样本数。为什么取名叫事件，只能说第一个总结了的人。我更喜欢用最本质的语言来说，就是遇到矩形的边界时。但是这个就是事件的定义和概念。最后是差分数组，每次遇到一个值，会影响以后的变化。这里不适合用差分，差分适用于延迟计算，这里是要实时更新的。例如我们现在是直接更新，如果换成差分，就需要对于边界+1,-1，然后利用前缀和来复原，额，每次更新都要一遍，实际上的差分适用于最后才更新的合适。

样例

# 最原始的暴力做法，一个都跑不了。1e10*n的复杂度
# n = int(input())
# rects = [tuple(map(int, input().split())) for _ in range(n)]
# res = 0
# for x in range(10001):            # 遍历每个格子的横坐标
#     for y in range(10001):        # 遍历每个格子的纵坐标
#         for x1, y1, x2, y2 in rects:  # 检查每个矩形
#             if x1 <= x < x2 and y1 <= y < y2:
#                 res += 1
#                 break  # 只要被一个矩形覆盖，就计一次面积
# print(res)

# #暴力做法,能成3个
# n=int(input())
# paint=set()
# for _ in range(n):
#     x1,y1,x2,y2=map(int,input().split())
#     for x in range(x1,x2):
#         for y in range(y1,y2):
#             paint.add((x,y))

# print(len(paint))

#会超时，那就优化它，
# n = int(input())
# rects = [tuple(map(int, input().split())) for _ in range(n)]

# res = 0
# for y in range(10001):
#     diff = [0] * 10002  # 差分数组，多1防止越界
#     for x1, y1, x2, y2 in rects:
#         if y1 <= y < y2:
#             diff[x1] += 1
#             diff[x2] -= 1
#     cover = 0
#     for x in range(10001):
#         cover += diff[x]
#         if cover > 0:
#             res += 1
# print(res)



#下面是最终写法
n=int(input())
x_coord=set()
rectangulars=[]

for _ in range(n):
  x1,y1,x2,y2=map(int,input().split())
  rectangulars.append((x1,y1,x2,y2))
  x_coord.add(x1)
  x_coord.add(x2)

#开始离散化
x_list=sorted(x_coord)
x_id={x:i for i,x in enumerate(x_list)}

#开始定义事件，扫描线，以平行于x轴的线扫描
events=[]
for x1,y1,x2,y2 in rectangulars:
  events.append((y1,x1,x2,1))
  events.append((y2,x1,x2,-1))
events.sort()

#定义扫描时，获取覆盖长度
def get_length():
  length=0
  for i in range(len(x_list)-1):
    if cnt[i]>0:
      length+=x_list[i+1]-x_list[i]

  return length

cnt=[0]*(len(x_list))
area=0
pre_y=0
length=0
for y,x1,x2,flag in events:
  delta_y=y-pre_y
  area+=length*delta_y
  for i in range(x_id[x1],x_id[x2]):
    cnt[i]+=flag

  length=get_length()
  pre_y=y

print(area)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla