掃描線

我還沒學計算幾何學這東西幹啥

在二維平面中給出 \(n\) 個矩形，對于第 \(i\) 個矩形給出對角坐标 \(x_{1_i},y_{1_i},x_{2_i},y_{2_i}\)，求它們的面積并。

\(1\le n\le 10^5,0\le x_{1_i},y_{1_i},x_{2_i},y_{2_i}\le 10^9\)

主要問題是如何處理兩個矩形相交的問題

矩形好就好在它的形狀十分規則，我們可以把下面這樣一個複合圖形分割成許許多多的小矩形。

比如上圖這個矩形，就可以分成好幾塊。

對于每一個塊，我們發現其寬是幾個矩形所占占據的縱坐标區間，長就是我們劃分的塊長，首先可以考慮到對整個縱坐标建立線段樹，然後做區間合并。按橫坐标向後掃描，維護縱坐标是否被覆寫，每次求一遍區間并長度和。

但是再看一下資料範圍，就會立刻打消暴力建樹的念頭。非常非常顯然還要再優化。

我們發現瓶頸在于橫縱坐标是在是太太太太大了，就在這個上面做文章。

現在我們要把矩形的各個豎邊拆開來看，設第 \(i\) 條豎邊的橫坐标是 \(x_i\)，豎邊覆寫的縱坐标區間是 \(l_i,r_i\)。

對于橫坐标上的掃描，能發現我們根本不需要每一個橫坐标都做一遍求和，事實上在 \(x_i\) 和 \(x_{i+1}\) 之間的區間覆寫情況一定是一樣的，也就是說一定是一個矩形，我們可以在 \(x_i\) 做一遍區間并長度和之後直接先乘 \(x_{i+1}-x_i\)。橫坐标上的最壞時間 \(10^9\Rightarrow 10^5\)。

對于縱坐标上的維護區間合并。區間合并時，我們其實隻會關心區間各個端點的大小關系，類似地沿用上面的方法。我們先把所有的 \(l,r\) 放在一起排序得到數組 \(y\)，在這上面建立線段樹，每個節點維護的是 \(y_i,y_{i+1}\) 之間的區間被覆寫的次數，如果我們想要覆寫一個區間 \(L,R\) 的話我們就可以把 \(y_{i_L},y_{i_r-1}\) 區間 \(+1\) 即可。

線段樹維護區間覆寫次數和區間長度即可(結果這裡還卡了我很久)。