<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Data Structure ---- - pbds - 掃描線 --- ## Hash 一個比較快的 unordered_map [速度比較](https://codeforces.com/blog/entry/60737) ---- ## 用法 需要引入 <bits/extc++.h> 標頭檔 ``` cpp #include<bits/extc++.h> ``` 然後在__gnu_pbds的namespace下 ```cpp! using namespace __gnu_pbds; ``` 宣告 ```cpp! gp_hash_table<int, int> mp1; cc_hash_table<int, int> mp2; ``` --- ## 名次樹 - 找第k小的元素 - 找元素的排名（第幾小） ---- ## 用法 需要引入 <bits/extc++.h> 標頭檔 ``` cpp #include<bits/extc++.h> ``` 然後在__gnu_pbds的namespace下 ```cpp! using namespace __gnu_pbds; ``` 宣告 ```cpp! tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> tr; 會去重 tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> tr; 不會去重 ``` ---- 大部分功能跟set/multiset一樣 以下是多的功能 ```cpp! auto it = tr.find_by_order(k); // 找第k小，回傳iterator (0-base) int ord = tr.order_of_key(x); // 找x的排名 (0-base) ``` 注意如果用了 **less_equal** 的版本 erase會爛掉 要像底下這樣刪 ```cpp! int ord = tr.order_of_key(x); auto it = tr.find_by_order(ord); tr.erase(it); ``` ---- ## 逆序數對 - 名次樹 從後面掃回來 - insert(x) - ans += tr.order_of_key(x); (查詢他是第幾小 &rarr; 等價於有多少人比他小) ```cpp! for (int i = n - 1; i >= 0; --i) { tr.insert(x); ans += tr.order_of_key(x); } ``` 這樣子做也是 $O(\log n)$。 ---- 名次樹的 常數比較大，在 $(n\ge 5\cdot 10^5)$ 的情況下容易拿到 TLE。 但是實作上比較短，大家可以自己衡量一下要使用哪種 --- ## 掃描線 就是一條線在圖上掃過去 ---- 像這樣 <img src="https://oi-wiki.org/geometry/images/scanning.svg" style="background-color: #f0f0f0; padding: 10px; border-radius: 4px; display: block; " /> ---- 或是這樣 之類的各種掃法   ---- 介紹一些很經典的掃描線題目 ---- ## [二維平面交點數量（水平+垂直線）](https://cses.fi/problemset/task/1740) 在二維平面上有 $n$ 個線段，這 $n$ 個線段不是鉛直線就是水平線， 問你圖上有幾個交點。 每個線段用兩個點來表示：$(x_1,y_1),(x_2,y_2)$。 $1 \leq n \leq 10^5$ $-10^6 \leq x_1 \leq x_2 \leq 10^6$ $-10^6 \leq y_1 \leq y_2 \leq 10^6$ ---- 從最底下掃描線上來 遇到豎線 &rarr; **加值/減值** 遇到橫線 &rarr; **查詢區間總和** 具體例子看圖 ----  ---- 這種情況要注意順序問題 加值 &rarr; 查區間sum &rarr; 減值  ----  ----  ----  ----  ----  ----  ---- 可以發現每次區間查的總和就是交點數量！ ---- ### [經典例題：Area of Rectangles](https://cses.fi/problemset/task/1741/) 二維平面上有 n 個長方形，問你這些長方形的聯集面積。 而長方形給你左下和右上兩個端點：$(x_1,y_1),(x_2,y_2)$ $1 \le n \le 10^5$ $-10^6 \le x_1 < x_2 \le 10^6$ $-10^6 \le y_1 < y_2 \le 10^6$  ---- 掃描線過程 <img src="https://oi-wiki.org/geometry/images/scanning.svg" style="background-color: #f0f0f0; padding: 10px; border-radius: 4px; display: block; " /> 分段算面積 ---- 這邊區間加值 rangemodify(1, 3, 1)  ---- 這邊要先 查詢(查被覆蓋的區間總和, **線段樹內>0** 的格子數量) 然後 * ( 兩次查詢的高度差 ) 計算黃色部分面積 再做加值 rangemodify(2, 4, 1)  ---- 查詢(**線段樹內>0** 的格子數量) 然後 * ( 兩次查詢的高度差 )計算藍色部分面積 再做加值 rangemodify(3, 5, 1)  ---- 查詢(**線段樹內>0** 的格子數量) 然後 * ( 兩次查詢的高度差 )計算紫色部分面積 再做減值 rangemodify(1, 3, -1)  ---- 查詢(**線段樹內>0** 的格子數量) 然後 * ( 兩次查詢的高度差 )計算藍色部分面積 再做減值 rangemodify(2, 4, -1)  ---- 查詢(**線段樹內>0** 的格子數量) 然後 * ( 兩次查詢的高度差 )計算黃色部分面積 再做減值 rangemodify(3, 5, -1)  ---- 因為我們總是查整個線段樹有幾個>0的點 所以只需要往上維護 線段樹存兩個資訊就能夠維護 - 當前區間被幾條線完整覆蓋 - 當前區間被覆蓋的長度 ---- ### [矩形周長](https://acm.hdu.edu.cn/showproblem.php?pid=1828) 二維平面上有 n 個長方形，問你這些長方形的聯集周長。 而長方形給你左下和右上兩個端點：$(x_1,y_1),(x_2,y_2)$ $1 \le n \le 5 * 10^3$ $-10^4 \le x_1 < x_2 \le 10^4$ $-10^4 \le y_1 < y_2 \le 10^4$   ---- 觀察發現從底下掃描線上去，每一次的貢獻都是上一次覆蓋的長度和這一次覆蓋的長度的變化量  ---- 前一次什麼都沒有 貢獻是紫色那段  ---- 前一次是橘色 紫色是變化量 也就是這一次的貢獻  ---- 前一次是橘色 紫色是變化量 也就是這一次的貢獻  ---- 前一次是橘色 紫色是變化量 也就是這一次的貢獻  後面以此類推 然後豎的再做一次一樣的事 --- ## 二維數點問題（偏序問題） ---- [逆序數對](https://www.luogu.com.cn/problem/P1908) 其實可以把逆序數對畫成二維平面上的圖  等價於每個點去找藍色範圍的點有幾個 有時候會遇到數二維平面上的點的問題，可以試著往掃描線去想 --- [練習](https://vjudge.net/contest/713623#problem/A)