# 第六章 :進階資結

## 前言
請先確定自己可以很好的使用基礎資結的內容，否則會太毒瘤。
:::spoiler 裡面是平板電視，想看得再點開，應該不會教。
## gp_hash_table
使用方法跟`map`一模一樣。
e.g.

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
signed main() {
    gp_hash_table<int, int> cnt;
    cnt[1]=20, cnt[9191921]=1234;
    cout<<cnt[1]<<" "<<cnt[9191921]; //20 1234
}

但常數在理想情況比`map`好太多了，`map`是使用紅黑樹，每次操作的時間複雜度是 $(O\log n)$，而`gp_hash_table`則是透過 [hash 進行運算](https://ithelp.ithome.com.tw/articles/10208884)，在 hash 不碰撞的情況，時間複雜度是 $O(1)$
* [$\text{Codeforces}$上其他使用者所補充的時間差距](https://codeforces.com/blog/entry/60737)


### 自訂hash
由於原本hash很容易被卡，所以可以自訂hash。
e.g.

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<int, int, chash> table;

## rb_tree_tag
參考 [$\text{Codeforces}$](https://codeforces.com/blog/entry/11080)。
更強大的`set`。
e.g.

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
signed main() {
    ordered_set s;
    s.insert(1);
    s.insert(2);
    s.erase(1);
    s.insert(3);
    cout<<*s.lower_bound(1)<<'\n';
    cout<<*s.find_by_order(1)<<'\n';//第1個元素是誰(0-based)。
    cout<<s.order_of_key(4)<<'\n'; //有幾個元素比4小。
}

操作的時間複雜度為 $O(\log n)$。
## 補充
* [rope](https://hackmd.io/@Viecon-342524/SJ1C2BUE9) 偏毒瘤，小心食用。
:::
## 線段樹
### 區間查詢
> 有一個數列 $a_1, a_2,...,a_n$，要對陣列做兩種操作。
> 1. $\text{sum L R :}$ 計算 $a_L+a_{L+1}+...+a_R$。
> 2. $\text{add P V :}$ 把 $a_P+整數$ $V$。
> * 條件限制
>
> $1 \le n, q \le 10^6$

本章要教的線段樹
線段樹有三個主要的部分以及兩個操作。
1. $\text{build}$
2. $\text{modify}$
3. $\text{query}$
4. $\text{pull}$
5. $\text{push}$

## 練習題目
[Josephus Problem II CSES](https://cses.fi/problemset/task/2163/)
[奇怪的老闆](https://judge.cchs.chc.edu.tw/ShowProblem?problemid=a041)