B - Beam Cannon(掃描線)

求給定

w

×

h

w\times h

w×h的矩形覆寫的最多的點數。

經典掃描線。

對一個點建立兩條邊，一條入邊(x,y,y+h)權為1，一條出邊(x+w,y,y+h)權為-1。

然後用線段樹維護y，每次查詢整個區間的max即可。

這裡我們枚舉的是矩形的右上角，顯然對于一個點

(

x

,

y

)

(x,y)

(x,y)。

(x,y)到

+

(x+w,y+h)

(x+w,y+h)這個矩形的所有範圍都可以作為右上角包括該點。

而邊的權就是控制

x軸，線段樹

y就是維護答案。

是以本題隻需寫一個，區間更新，查詢就是

a

1

.

s

u

m

a_1.sum

a1​.sum即可。

時間複雜度：

O

n

l

o

g

O(nlogn)