<style> .reveal .slides { text-align: left; font-size:30px; } </style> # Data Structure Introduction to Competitive Programming 03/27 ---- - Policy-Based Data Structures(pbds) - Sweep line with data structure --- ## Policy-Based Data Structures(pbds) 人稱「平板電視」 - Hash - 平衡樹 - rope ---- ## 先複習一下 map vs unordered_map ||map|unordered map| |----|----|----| |標頭檔|`#include <map>`|`#include <unordered_map>`| |內部實作|紅黑樹|Hash| |內部順序|有序|無序| |查詢|log(n)|平均O(1)，最差O(n)| |插入|log(n)|平均O(1)，最差O(n)| |刪除|log(n)|平均O(1)，最差O(n)| ---- ## Hash - cc_hash_table - gp_hash_table 基本上跟 STL 的 `unordered_map` 差不多但是有時候會快有時候會慢，看資料的類型和大小。 以上兩者只能用來插入、刪除、查詢某個值存不存在或者 key 對應到的 value 是多少。 ---- ## 用法 不在標頭檔 `bits/stdc++.h` 裡 要另外宣告標頭檔： ```cpp! #include<bits/extc++.h> ``` 並且要寫命名空間： ```cpp! using namespace __gnu_pbds; ``` ---- ## 範例 ```cpp= #include <bits/extc++.h> using namespace __gnu_pbds; gp_hash_table<int, int> mp; cc_hash_table<int, int> mp2; int main(){ mp[3] = 12; cout << mp.size() << endl; if(mp.find(123) == mp.end()){ cout << "Not found" << endl; } } ``` ---- 複雜度： 搜尋新增刪除等期望複雜度為 O(1)，但在資料量大的時候可能會變 O(N)。 [測試速度比較!](https://codeforces.com/blog/entry/60737) ---- ## 平衡樹(名次樹) 當成是一個很多用途的 set/multiset ---- ## 宣告 同樣需要： ```cpp! #include<bits/extc++.h> using namespace __gnu_pbds; ``` 如果資料沒有重複數字: ```cpp! tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; ``` 如果資料有重複數字: ```cpp! tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>; ``` ---- ## 宣告： 如果想要裡面放 int ```cpp! tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; ``` 如果想要裡面放 pair<int,int> ```cpp! #define pii pair<int,int> tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>; ``` ---- ## 可以做到哪些事情 在 $O(\log N)$ 求當前集合中第 $k$ 小的值，求當前值第幾小等功能 用法跟 set 差不多，一樣會將元素由小到大照順序放 - `.insert(x)` 插入元素 x - `.erase(x)` 刪除元素 x - `.clear()` 把整個容器清空 - `.find(x)` 找尋 x 在容器中的位置(回傳 iterator) - `.find_by_order(k)` 找出第 k 小的值的位置(回傳 iterator) - `.order_of_key(val)` 找出 val 在容器中是第幾小 特別注意的是 pbds 沒有 count 函數 ```cpp if(s.find(x) != s.end()) //判斷有沒有值 x 存在的寫法 ``` ---- ## sample code ```cpp= #include <bits/extc++.h> using namespace __gnu_pbds; tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s; int main(){ // Insert some entries into s. s.insert(12); s.insert(505); // The order of the keys should be: 12, 505. assert(*s.find_by_order(0) == 12); assert(*s.find_by_order(3) == 505); // The order of the keys should be: 12, 505. assert(s.order_of_key(12) == 0); assert(s.order_of_key(505) == 1); // Erase an entry. s.erase(12); // The order of the keys should be: 505. assert(*s.find_by_order(0) == 505); // The order of the keys should be: 505. assert(s.order_of_key(505) == 0); cout << s.size() << endl; } ``` ---- 例題：[ZJ 排名順序](https://zerojudge.tw/ShowProblem?problemid=d788) 你可以選擇砸 BIT+離散化，線段樹+離散化。 我們試試看用名次樹! ---- - 宣告名次樹 ```cpp! tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> s; ``` - 假設一個人的成績是 k ```cpp! s.insert(k); ``` - 查詢他的名次 ```cpp! int rank=s.size()-s.order_of_key(k); ``` 複雜度：$O(n\log n)$ ---- ## 例題：逆序數對 題目就不多贅述，大家都遇過。 相信大家只會 BIT 和分治或是線段樹的解法。 來看看名次樹是怎麼做的 ---- 一樣從後面做到前面，每次跑以下操作： - 插入這個數字 k 到名次樹 ```cpp! s.insert(k); ``` - 查詢這個數字 k 是第幾小 ```cpp! s.order_by_key(k); ``` 沒錯就是這麼簡單，複雜度為$O(n\log n)$ ---- ## 缺點： 因為 pbds tree 特別肥，在 $(n\ge 5\cdot 10^5)$ 的情況下容易拿到 TLE。 在這個情況下建議乖乖刻 BIT， ---- 因此在求動態第幾小且資料量沒有很大時，不仿試試名次樹。 在實作方面，它可以節省非常多的時間👍！ ---- ## rope 聽說是因為要跟 string(細繩)比較所以叫做 rope(粗繩)。 可以當成是一個超強的 string，內部是可持久化平衡樹，支援區間操作、持久化(以後會教)。 ---- ## 宣告 - 標頭檔和命名空間 ```cpp! #include<ext/rope> using namespace __gnu_cxx; ``` - 宣告一個內部為 char 的 rope ```cpp! rope<char> r; crope r; ``` - 宣告一個內部為 int 的 rope ```cpp! rope<int>r; ``` ---- 特別的是，rope 裡面為 char 就可以直接輸出 ```cpp! rope<char>a="123456"; cout<<a<<endl;//可以編譯 ``` ```cpp! crope b="123456"; cout<<b<<endl;//可以編譯 ``` ```cpp! rope<int>c; cout<<c<<endl;//CE ``` ---- ## rope 支援的操作 宣告 `rope<int>r;` - `r.push_back(x);`or`r+=x;` //在最後加上 x - `r.pop_back();` //去掉最後一個元素 - `r.insert(pos, x);` //在 pos 位置加入 x - `r.erase(pos, x);` //從 pos 位置刪除 x 個元素 - `r.copy(pos, len, x);` //從 pos 開始的 len 個元素用 x 代替 - `r.replace(pos, x);` //從 pos 開始的元素全部換成 x - `r.substr(pos, x);` //取得以 pos 開始的 x 個元素 - `r.at(i);`or`r[i];` //詢問第 i 個元素 ---- 以上有任何進行區間操作或是刪除的行為，複雜度皆為 $O(\log n)$。 要注意的是如果進行 `r.insert(int pos,crope x)`的操作， 最壞複雜度會到 $O(n)$。 當然他的常數也很大，請謹慎服用。 [rope 和 string 複雜度比較](https://en.wikipedia.org/wiki/Rope_(data_structure)#Comparison_with_monolithic_arrays) --- 休息 --- ## Sweep Line with data structure ---- ## Sweep Line 掃描線是什麼？ 通常是在二維平面上，可以用一條(或兩條)水平線或鉛直線直接掃過整個平面，這樣的想法就叫掃描線  ---- 除了點以外，二維平面上的線段也可以被掃描線壓成一維  ---- 接下來要說說掃描線這個概念要怎麼套用在資料結構上 ---- ## 例題：Intersection Points 在二維平面上有 $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$ ---- 圖中有三條鉛直線，兩條水平線，交點有五個。  怎麼掃描線呢？ ---- ## 作法 對於鉛直線，可以當作是去查詢 $(y_1,y_2)$ 這個區間有幾條水平線  ---- 對於水平線的兩個端點 $(x_1,x_2)$，可以當作兩次修改 在 $x_1$ 的時候，y 這個點多了這一條線(單點 update) 在 $x_2$ 的時候，y 這個點少了這一條線(單點 update)  ---- 這時候用掃描線從左往右掃過去，資料結構裡存的是 $y$ 的資訊，就會過了  ---- 由於從左往右掃過去，會有 struct 存鉛直線和水平線的資訊 ```cpp! struct Line{ int x,y1,y2,mode; }; vector<Line>all; ``` 鉛直線: ```cpp! void add_vertical_line(int x1,int y1,int x2,int y2){ all.push_back({x1,y1,y2,0});//mode==0代表鉛直線 } ``` 水平線: ```cpp! void add_horizontal_line(int x1,int y1,int x2,int y2){ all.push_back({x1,y1,y1,-1});//mode==-1代表水平線左側端點 all.push_back({x2,y1,y1,1});//mode==1代表水平線右側端點 } ``` ---- 按照 x 來排序，如果 x 一樣，以水平線左側端點 $\rightarrow$ 鉛直線 $\rightarrow$ 水平線右側端點的順序排序 ```cpp! bool compare(Line a,Line b){ if(a.x==b.x)return a.mode<b.mode; else return a.x<b.x; } ``` ---- ### 經典例題：Area of Rectangles 二維平面上有 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$  ---- ## 作法： 掃描線除了從左往右，也可以從下到上，這裡用從下到上舉例 如果用下到上舉例的話，每個長方形要分成上側的邊和下側的邊兩種 case。  ---- 對於所有下側的邊當作區間$(x_1,x_2)$，會做區間查詢和加值： - 查詢線段樹內有幾個地方不為 0 - 把線段樹中的區間 $(x_1,x_2)$ 都 +1  ---- 記得在查詢的時候要維護目前這個區間和上一個區間的高度相差為多少。 像是下方黃色部份，他的面積為(高度相差)\*(線段樹內有幾個地方不為 0)。  ---- 算完面積之後記得要對線段樹做區間加值!!  ---- 接下來是每個長方形上側的邊，同樣當作區間 $(x_1,x_2)$，做區間查詢和減值，跟下側的邊差不多： - 查詢線段樹內有幾個地方不為 0 - 把線段樹中的區間 $(x_1,x_2)$ 都 -1  ---- 面積計算方式跟下側的邊一樣  ---- 從下往上掃完所有邊，把每個有顏色的面積用個變數記錄起來就好了。  ---- 線段樹裡每個區間裡面會放兩個數字。 - 第一個是紀錄這個區間被加值的總和 - 第二個是紀錄這個區間內有幾個地方有數字 維護完直接查根節點的第二個數字就好了 怎麼維護？ ---- 由於只要查詢最根節點的資訊，所以可以知道我們只要好好的往上維護，下方的資訊比起來不太重要。 首先可以很直觀的想到，如果當前區間內有被做加值，也就是第一個數字 > $0$，代表這個區間內的數字都不為零，那他的第二個數字就等於當前區間的長度。 如果這個區間內沒有被做加值的話，第二個數字直接取兩個子節點的第二個數字加總就行。 ---- 模板： ```cpp [|31-35|36-47] struct AreaofRectangles{ #define cl(x) (x<<1) #define cr(x) (x<<1|1) int n, id, sid; pair<int,int> tree[MXN<<3]; // count, area vector<int> ind; tuple<int,int,int,int> scan[MXN<<1]; void puint(int i, int l, int r){ if(tree[i].first) tree[i].second = ind[r+1] - ind[l];//當前區間有被做加值 else if(l != r){//沒有就直接拿兩個子節點的第二個數字 int mid = (l+r)>>1; tree[i].second = tree[cl(i)].second + tree[cr(i)].second; } else tree[i].second = 0; } void upd(int i, int l, int r, int ql, int qr, int v){ if(ql <= l && r <= qr){ tree[i].first += v; puint(i, l, r); return; } int mid = (l+r) >> 1; if(ql <= mid) upd(cl(i), l, mid, ql, qr, v); if(qr > mid) upd(cr(i), mid+1, r, ql, qr, v); puint(i, l, r); } void init(int _n){ n = _n; id = sid = 0; ind.clear(); ind.resize(n<<1); fill(tree, tree+(n<<2), make_pair(0, 0)); } void addRectangle(int lx, int ly, int rx, int ry){ ind[id++] = lx; ind[id++] = rx; scan[sid++] = make_tuple(ly, 1, lx, rx); scan[sid++] = make_tuple(ry, -1, lx, rx); } int solve(){ sort(ind.begin(), ind.end()); ind.resize(unique(ind.begin(), ind.end()) - ind.begin());//離散化 sort(scan, scan + sid); int area = 0, pre = get<0>(scan[0]); for(int i = 0; i < sid; i++){ auto [x, v, l, r] = scan[i]; area += tree[1].second * (x-pre);// upd(1, 0, ind.size()-1, lower_bound(ind.begin(), ind.end(), l)-ind.begin(), lower_bound(ind.begin(),ind.end(),r)-ind.begin()-1, v); pre = x; } return area; } }rect; ``` 複雜度：$O(n\log n)$ ---- ### 例題：2023ICPC台灣站 pE Slabstones Rearrangement $t$ 筆測資，每筆測資給你 $n$ 個長方形和最小水平間隔 $k$，每個長方形給你左下和右上兩個端點：$(x_1,y_1),(x_2,y_2)$。 這些長方形要盡可能的向中間移動，並且長方形和長方形水平間隔不能小於 $k$，問你一開始的最小包覆長方形和後來的最小包覆長方形的兩個面積相差多少？ $4 \le n \le 100$，$0 \lt k \le 10^9$ $0 \le x_1 < x_2 \le 10^9$ $0 \le y_1 < y_2 \le 10^9$ ---- 答案為(開始面積-移動後面積)=96-72=24  ---- 一樣用掃描線的概念去想，把每個長方形左側的邊當作區間 $(y_1,y_2)$ 當做一次區間查詢和改值。 - 區間查詢：查詢這個區間的的最大值 w，代表左方最靠右的長方形離最左邊的長方形的左側距離。 - 區間改值：把這個區間改成 w+k+這個長方形的寬度 記得離散化$\rightarrow$AC! 因為 n 很小，官方解答給的是 DP on DAG 的做法，可以想一下 DAG 怎麼做 ---- pE只有32個人寫掉，會這題基本上就有銀牌了～ ~~Rurudo_daisuki在結束前四分鐘AC這題，差點連銀牌都沒有~~ [ICPC2023 台灣站記分板](https://github.com/GuanH/Rurudo_daisuki_Codebook/blob/main/scoreboard/icpc2023.png) ###### <font color="black">然後這題期中考可能會考，噓</font> --- 題目們：[link](https://vjudge.net/contest/616559) 下周清明連假，但課有點趕因此會錄影給大家線上看 記得看 discord 公告 : D