# NYCU PCCA 2022 Winter Camp 0125
## [Part 1. STL](https://www.youtube.com/watch?v=Pp4tgANoWC4&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=1)
### I. vector
#### 1. 常用函式
``` cpp=
#include <vector>
vector<int> v;
v.size(); // v 的長度
v.resize(n); // 調整大小為 n
v.clear(); // 初始化 v
v.push_back(val); // 放 val 在 v 後面
v.begin(); v.end(); // v 的 iterator
```
#### 2. vector vs. array
|vector|array|
|------|-----|
|可更動大小|不能更動大小|
|宣告較複雜|宣告簡單|
|功能多|很單純的陣列|
#### 3. 其他函式說明
* `vector<int> v(n, 0);`
>int: 陣列中要放的型別
v: 名字
n: 長度
0: 初始值(沒放的話則會是預設值)
二維陣列
```cpp
vector<vector<int>> v(n,vector<int> (n, 0));
```
* `v.push_back(val);`
把 val 的值複製
* `v.emplace_back(val);`
把 val 做為參數來宣告
>兩者速度基本沒差 除非加入的東西很大
>**push_back() v.s. emplace_back()**
emplace_back() 的好處在於它可以減少「宣告」的繁瑣(如下)
``` cpp=
vector<pair<int, int>> arr;
int main() {
arr.push_back(make_pair(2, 5));
// 要先產生 pair 才可以被複製
arr.emplace_back(2, 5);
// 簡潔許多
return 0;
}
```
* `v.resize(n)`
把 v 長度設為 n
* `v.resize(n, val)`
如果 v 需要增加長度，值會是 val
已存在的值不會被改變！！！
* `v.assign(n, val)`
把 v 初始化成長度為 n 且值為 val
* `v.reserve(n)`
在陣列後面預留 n 的空間
>v 的 size 仍不變
>
>用來避免 push_back() 時，可能需要花 O(n) 的時間搬移 v 到連續記憶體更長的地方
* **請不要用 erase(), insert()**
vector 是連續儲存的，所以移除或插入在中間會需要 O(n) 的時間
**" 這兩個東西是毒瘤啊！ "**
---
所以現在是 iterator 時間
> " iterator 迭代器，簡單來說就是指標。 "
* `v.begin()`: 回傳指向第 0 個的 iterator
* `v.end()`: 回傳指向最後一項的下一項的 iterator
所以 v.begin() 到 v.end() 是左閉右開
* `v.rbegin()`: 回傳指向最後一項的 iterator
* `v.rend()`: 回傳指向第 0 項的前一項的 iterator
``` cpp=
#include <vector>
vector<int> v(10);
int main() {
for (int &i: v) cin >> i; // 輸入 10 個東西到 v
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it << '\n'; // 記得加 * 在變數前面來取值
}
}
```
### II. tuple
適合==儲存一組資料的東西==（例如： x, y 座標）
```cpp=
#include <tuple>
#include <string>
#include <vector>
tuple<int, long long, string> t = {13, 53, "hello"};
pair<int, long long> p = {11, 42};
pair<int, vector<int> > pp; // 要存 vector 也可以
get<0>(t) // 回傳 t 的第 0 個東西 (13)
p.first; p.second; // 分別回傳 p 的第 0 項跟第 1 項
```
tuple 最多可以存 10 樣東西，但是較難使用
而 pair 是特化版的 tuple ，只能存兩種東西
宣告方式有以下兩種：
```cpp
pair<int, long long> p = {11, 42};
make_pair(11, 42);
```
> 小技巧
> 使用 #define 讓 first, second 更短
```cpp
#define first f
#define second s
```
### III. algorithm
```cpp
#include <algorithm> // 我都用萬用標頭檔哈哈
```
* **sort()**
" 你只要知道它的時間複雜度是 O(n log n)，很快就對了。 "
`sort(v.begin(), v.end());`
把 v.begin() 到 v.end() 之間排序
`sort(v.begin(), v.end(), cmp);`
依照自訂的 cmp 函式來排序
```cpp=
#include <algorithm>
#include <vector>
vector<int> v = {1, 3, 5, 2, 4};
bool cmp(const int &x, const int &y) {
return x > y;
}
int main() {
sort(v.begin(), v.end()); // 由小到大（預設）
sort(v.begin(), v.end(), cmp); // 由大到小（利用 cmp 函式）
sort(v.rbegin(), v.rend()); // 也是由大到小（倒著排序）
}
```
* **lower_bound(), upper_bound()**
配合二分搜尋，時間複雜度 O(log n)，特別注意==vector要先排好！==
`lower_bound(v.begin(), v.end(), val);`
在範圍找出 ≥ val 中，最小的 iterator
`upper_bound(v.begin(), v.end(), val);`
在範圍找出 > val 中，最小的 iterator
* **nth_element()**
`nth_element(v.begin(), v.begin() + val, v.end());`
時間複雜度 O(n)，類似快速排序(?)
在範圍中，找出第 val 項
第 val 項之前的值都會 ≤ 第 val 項
第 val 項之後的值都會 ≥ 第 val 項
可以放 cmp
* **next_permutation()**
`next_permutation(v.begin(), v.end());`
時間複雜度 O(n / 2)
可以找出下一字典序大的排列 (prev_permutation() 可以找下一小的)
也可以放 cmp
{1, 2, 3, 4, 5} -> {1, 2, 3, 5, 4}
### IV. set
沒錯，就是數學課教的集合
#### 1. 常用函式
```cpp=
#include <set>
set<int> s;
s.insert(val); // 在 s 中放入 val
s.erase(val); // 把 val 從 s 中移除
s.clear(); // 清空 s
s.size(); // s 的大小
s.find(val); // 找 val 的 iterator
s.count(val); // 找 val 在 s 中的數量
s.begin(); s.end(); // iterator
```
#### 2. 特色
* **值不能重複** （multiset 支援插入重複的值）
* **會自動排序**
可以快速取最大、最小值
(unordered_set 則不會排序)
* **不能隨機取值**
就是不行用 s[2] 來找第 2 小的東西啦
* **可以用 iterator 迭代**
#### 3. 說明
* `set<int> s;`
* `set<int, cmp> sc;`
依照 cmp 去排序
但是跟普通宣告 cmp 的方式不太一樣…
```cpp=
#include <set>
struct cmp {
bool operator() (const int &a, const int &b) const {
return a > b;
}
};
set<int> s; // 由小到大排列
set<int, cmp> sc; // 由大到小排列
```
* `s.insert(val);`
放 val 進 s 裡面
* `s.emplace(val);`
和 vector 一樣
* `s.erase(val);`
在 set 中移除值為 val 的東西
回傳被移除後的個數
val 也可以是 iterator
回傳被移除後的下一個 iterator（下一個比它大的）
:::info
erase() 的毒瘤操作
```cpp=
#include <set>
set<int> s;
int main() {
s.emplace(1); s.emplace(2); s.emplace(3);
for (auto it = s.begin(); it != s.end(); ) {
if (*it == 2) it = s.erase(it);
// 如果 it 指向 2，erase() 以後會回傳 3 的 iterator
else it++;
}
}
```
:::
* `s.find(val);`
回傳 val 的 iterator
如果 ==val 不存在，則會回傳 s.end()==
* `s.count(val);`
回傳 val 的個數
set 同樣的值只能有一個，所以==只會回傳 0 或 1==
---
所以現在是 iterator 時間
* s.begin() 指向第 0 項（最小值）
* s.rbegin() 指向最後一項（最大值）
跟 vector 一樣，可以用 for 迴圈迭代
### V. map
" 跟字典一樣，問一個答一個。 "
#### 1. 常用函式
```cpp=
#include <map>
map<int, string> m; // <key, value>
m[1] = "NYCU"; m[5] = "PCCA"; // 定義
m.clear(); // 清空
m.find(val); // 回傳 key = val 的 iterator
m.count(val); // 回傳 key = val 的個數
m.begin(); m.end(); // iterator
```
#### 2. 特色
* **每個元素一個 pair** ({key, value})
* **key 不能重複** (multimap 支援 key 重複)
* **會自動排序** (依據 key 進行排序(小 → 大))
unordered_map 則不會排序
```cpp=
#include <map>
map<int, int> m;
m[2] = 7; // 定義
m[4]++; // 如果索取的 key 未被定義，則會使用預設(0)
// m[4] = 1
```
#### 3. 其他函式
* `m.find();`
例如： m.find(2)
尋找 key = 2 的元素
回傳 pair {2, 7}
* **iterator**
```cpp=
#include <map>
map<int, int> m;
for (pair<const int, int> &i: m) {
cout << "key: " << i.first << ' ';
cout << "value: " << i.second << '\n';
}
```
### VI. priority queue
#### 1. 常用函式
```cpp=
#include <queue> // 它在queue裡面欸呵呵
priority_queue<int> pq;
pq.empty(); // 是否空了
pq.size(); // 大小
pq.top(); // pq 中，值最大的
pq.pop(); // pq 中，移除值最大的
pq.push(val); // 把 val 放入 pq 中
```
:::warning
**跟 queue 的不同**
queue 是 FIFO ( first in first out )
priority queue 不是用時間作為排序依據，而是以大小排序
:::
#### 2. 特色
* **預設是<font color="#f00">從大到小</font>排列！！！**(可以使用cmp)
`priority_queue<T, vector<T>, less<T>>`
T 表示資料型態
less<T> 表示資料由大到小排(預設)
改為使用 greater<T> 就會是由大到小排
你也可以寫 cmp
```cpp=
struct cmp { // 由小到大
bool operator() (int &a, int &b) {
return a > b; // 跟前面的反過來，有點毒瘤，要小心
}
};
```
### VII. stringstream
#### 1. 常用函式
```cpp=
#include <sstream>
stringstream ss;
int a, b;
ss << "12 53"; // ss 寫入 "12 53"
ss >> a >> b; // 從 ss 讀出，a = 12, b = 53
ss.clear(); // 清除 flag
ss.str("PCCA"); // 把 ss 的內容設定為 "PCCA"
```
stringstream 宣告速度不快，所以==請避免重複宣告==，多資源回收～
* **寫入讀出**
寫入： ss << "Hello";
讀出： ss >> s;
其實就跟 cin 、 cout 一樣啦
* **`ss.clear()`**
它只會初始化 ss 裡的 flag ，裡面的 buffer 不會清空！<font size = 5>不會清空！</font><font size = 6>不會清空！</font>
那我們要怎麼把它清空呢？ 請使用下方的工具 str()
* **`ss.str()`**
`ss.str("PCCA");`
把 ss 的內容設成 “PCCA”
`ss.str();`
回傳目前 ss 裡的字串
:::success
**清空 stringstream 的方式**
``` cpp
ss.str("") // 把它變成空字串
ss.clear() // 把一些不用的東西(例：EOF)清掉
```
:::
---
## [Part 2. DSU](https://https://www.youtube.com/watch?v=8dsEw2ndqCI&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=2)
DSU = Disjoin-Set Union
有些集合，他們<font color="#f00">**互相交集為空集合**，</font>則這些集合稱為並查集，又稱互斥集。
### 舉個例子：
學校裡有一些幫派，每個人只會屬於一個幫派，若某人==不加入別人，代表他自己就是一個單人幫派。==
幫派之間會互相鬥爭，==贏得一方可以把對方所有人納入自己的幫派==，也就是把兩個幫派合併成一個。
剛剛說的幫派是一群人組成的，我們只知道他是一個群體，但要怎麼表示這個群體最簡單呢？
我們可以從這個幫派之中，隨便挑一個人來當老大，==老大的作用就是用來代表這群體。==
我們可以透過不斷詢問老大的老大的老大的老大. . . 直到有人的老大是自己，就可以確定這個人是群體的代表。
▲ 框在一起的是同個幫派的成員；紅色底的是該幫派的老大。
#### 但這樣會比較快嗎？ 最差狀況還是 O(n) 查詢
* parent[n] (boss[n])
用來表示你的上層是誰，用 parent[i] == i 來偵測自己是否是最上層。
* size[n]
用來紀錄集合的大小，只有在 index 是最終老大時才有意義。
* 精簡版陣列 pa_sz[n]
``` cpp
if (parent[i] != i) {
pa_sz[i] = parent[i];
} else {
pa_sz[i] = -size[i];
}
```
* find()
find() 用來尋找最終老大。剛剛說過，一個一個找，最差情況會花費 O(n) 的時間。
``` cpp
int find(int index) {
if(parent[index] == index) return index;
return find(parent[index]); // 一路往上找
}
```
▲ 假設今天1的幫派和5的幫派打架，5的幫派獲勝，那1的幫派就會被5的幫派併吞。
▲ 而我們就把1的老大設定成5，5的幫派因此人數增加。1也因為不是最終老大，所以size[1]沒有用了。
* find 路徑壓縮
路徑壓縮就是在找老大的過程中
順便把路徑上所有點的老大也設成最終老大
``` cpp
int find(int index) {
if(parent[index] == index) return index;
return parent[index] = find(parent[index]); // 路徑壓縮
}
```
* union
合併兩個集合a, b
``` cpp
void Union(int a, int b) {
int fa = find(a), fb = find(b);
size[fa] += size[fb];
parent[fb] = fa;
}
```
* 啟發式合併
把小的集合接在大的集合下面，之後find會更快
``` cpp
void Union(int a, int b) {
int fa = find(a), fb = find(b);
if(size[fb] > size[fa]) swap(fa, fb);
size[fa] += size[fb];
parent[fb] = fa;
}
```
* 時間複雜度
都沒有： O(n)
路徑壓縮： O(log n)
啟發式合併： O(log n)
啟發式合併＋路徑壓縮： O(α(n)) (α = 反阿卡曼函數)
* 課後練習
[Kattis - Ladice](https://open.kattis.com/problems/ladice)
[Kattis - Association for Control Over Minds](https://open.kattis.com/problems/control)
[Codeforces - Social Network](https://codeforces.com/contest/1609/problem/D)
---
## [Part 3. Heap](https://www.youtube.com/watch?v=cdakZQa2pXE&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=3)
### 1. 資料型態
* min heap (最小堆積)：母節點的值恆小於等於子節點
* max heap (最大堆積)：母節點的值恆大於等於子節點
### 2. 操作 (以 min heap 為例)
* push()
將元素加入 heap 中
* top()
從 heap 中取出最小元素
* pop()
將 heap 中最小的元素去除
還有很多，只是這些夠玩了
### 3. 如何實現
把資料擺成 Complete Binary Tree
保證子樹一定不小於自己，但左右子樹大小不保證
示意圖：
### 4. 樹的儲存方法
因為是 binary tree，所以可用array存取。
根節點 idx=0
對於所有節點，若節點編號為 i，則左邊的孩子編號為 2i+1，且右邊的孩子編號為 2i+2
### 5. how 函式 work？
* **top**
獲得最小值(根節點)
* **push**
把要加入的值放入heap最後面，再慢慢跟上面的值比大小
例如：把0加入heap中
▼ 先把0放到最後面(vector的push_back())
▼ 跟上面的值比大小，比較小就往上移，像泡泡浮起來一樣
▼ 比到最後，就會發先0是最小的，所以位置在根節點
* **pop**
如果直接把最小值(根節點)刪掉，heap就會分裂成2個，下次要找最校值就會比較難處理。所以先把最小值和尾端交換，再把最後一個元素刪除(pop_back)，然後將現在的根節點和下面兩個值比，並且跟最小值交換
例如：把0刪掉
▼ 先把0和最後一個元素交換
▼ 刪除最後一個元素
▼ 讓19和下面兩個值比大小，並跟最小值(1)交換
▼ 繼續比直到19為3數值中最大或到達根部
### 6. 時間複雜度分析
* top： O(1)
* push, pop： O(log n)
### 7. 課後練習
priority queue
[Kattis - Jane Eyre](https://open.kattis.com/problems/janeeyre)
[Kattis - Continuous Median](https://open.kattis.com/problems/continuousmedian)
## [Part 4. BIT (Binary Index Tree)](https://www.youtube.com/watch?v=bCsU5hlc5jI&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=4)
用來處理動態區間和
BIT 會把原本的陣列
用很多長度為二的冪次的小塊區間表示，
在計算或是修改時，都去對那些小區間修改。
使用 BIT 會將時間複雜度變為 O(log n)
* bit[maxn] : 長度為整個區間 [1, n] 的一維陣列。
上面每個點儲存的不是該點真正的值，而是從這個節點往前**二的冪次**長度的區間和。
注意這是 1-base 的陣列。
* lowbit：我們定義最右邊出現的第一個 1 為 lowbit。
e.g. 10010 的 lowbit 為右邊第二個 bit 的 1。
一個點編號 13=8+4+1=1101 (2-base)
可以由 [1,8]+[9,12]+[13,13] 加總起來疊加出正確的 [1,13] 區間。
至於為什麼是這些區間，跟 lowbit 有很大關係。
#### 要如何正確且快速地找出那些小區間塊呢？
不斷找出當前 index 的 lowbit 將其扣掉，得出新的 index。
在查詢[1, i]的區間和時，先查格子 i (1101)，
再把lowbit拿掉，如此重複下去：
``` cpp
i=1101 -> sum+=bit[1101], i-=0001
i=1100 -> sum+=bit[1100], i-=0100
i=1000 -> sum+=bit[1000], i-=1000
i=0000 -> break
```
#### 只花 O(1) 找出 lowbit 的方法：
``` cpp
lowbit = i & -i;
```
舉例：
i = 10100, -i = 01100 (二補數)
i & -i = 00100
原理：
i 與 -i 加起來要讓它變成全部位數都是0 (溢位不算)
然後取 i 與 -i 位數都是 1 的就是 lowbit
> **二補數**
一個數的二補數是從它二進位表示的最左方開始，找到第一個 1 之後，右邊的 0, 1 互換
* query (詢問)
在詢問某區間和時
只要用剛剛的方法看他被哪些小區塊覆蓋
把他們加起來就是該區間和。
``` cpp
ll sum(int i) {
ll ret = 0;
while(i > 0) ret += bit[i], i -= i & -i; // 1-base
return ret;
}
```
要查詢閉區間 [l, r] 時，只要找出 [1, r]，扣掉 [1, l - 1]，就是[l, r] 的區間和了。
#### 但要修改怎麼辦？
當我們改了 index 這個點，要怎麼知道上面有哪些點有包含 bit[index] 所代表的區間呢？
* 單點修改
假設要修改 5 = 101 (2-base)
先改 i 的值，再把 i 加上 lowbit，反覆改 i，加值。
``` cpp
i = 101 -> bit[101]+=val, i = 110
i = 110 -> bit[110]+=val, i = 1000
i = 1000 -> bit[1000]+=val, i = 10000
i = 10000 -> bit[10000]+=val, i = 100000
// ...直到 i 超過 maxn -> break
```
* 區間修改
可以用線段樹做(詳情見Part 5. Segment Tree)
* 先找出某個單點 i，被哪些子區間重疊到
要把這個單點的值增加 val
就把跟他有關的所有區間都加上 val
``` cpp
void modify(int i, int val) {
while(i <= MAXN) bit[i] += val, i += i & -i;
}
```
#### 課後練習
[TIOJ - 1080](https://tioj.ck.tp.edu.tw/problems/1080)
[Codeforces round 196 - C](https://codeforces.com/contest/276/problem/C)
---
## [Part 5. Segment Tree](https://www.youtube.com/watch?v=Hfue-_pVFPc&list=PLtRlodjJ-YdIizrpGnftvH7hgJEQN7j9E&index=5)
前面 BIT 有提到，做區間和的時候如果每次都從頭計算，詢問的話要花 O(n) 的時間，實在是有點太久了。你其實可以動一下腦，你就會發現，你可以預處理好前綴和，前綴和做完可以大幅加速詢問的效率。但缺點是，你每修改一個值，你就要花 O(n) 時間改你做好前綴和的表。
於是線段樹這個東西就出現了，它是個很好玩的資料結構。
### 1. 功能介紹
<font color = "#f00" size = 4>每次操作都是 O(log n)！！！</font>
* 單點修改
* 區間查詢
* 區間修改
線段樹有另一個好處是，它不只可以求區間和，它可以做任何有結合律的二元運算子的操作，像是找最小值、最大值，或是乘法。
當你要訪問一個區間的時候，其實不用按照你擺的順序從頭到尾做。
### 2. 基本概念
* 善用運算子具有結合率的性質
* 每次詢問時，將大問題切成子問題
* 事先預處理一些區間的答案
* 更新時只需要更新與之相關的區間
### 3. 實現方法：建樹
* 所有節點都有各自代表的範圍的答案
* 每個節點都可以利用子樹資訊得到
* 葉節點存初始陣列數值
* 用陣列存最多只有 4n 個節點
▼ 例如： arr = [-9, 11, 1, 3, -7, -4, 10, -5]
它的存法跟 Heap 一樣，因為它也是一棵二元樹，所以你可以把根節點的 index 設成 0，它的 left child 和 right child 就分別是 2n+1 和 2n+2。
### 區間查詢
在 [l, r) 區間內詢問 [L, R) 時只會有以下三種狀況：
* 1. [L, R) = [l, r)
* 2. [L, R) ⊊ [l, r)
2-1. 目標區間在左半或右半 ( L ≥ mid ∨ R ≤ mid )
2-2. 目標區間橫跨中點
**狀況一**：目標區間與當前區間相等
直接回傳當前區間
**狀況二**：目標區間與當前區間不相等（都在左半或右半）
縮小問題，進入左（右）子區間
**狀況三**：目標區間與當前區間不相等（橫跨中點）
縮小問題，分別進入左、右子區間詢問
回傳子區間合併後的答案
例：求 [2, 4) + [4, 7) 的區間和
▼ 會變成求 [2, 4) + [4, 6) + [6, 7) 的區間和
最後答案是 4 + (-11) + 10 = 3
### 單點修改
利用類似二分搜的想法找到目標
回溯時依序更改與之相關的節點資訊
例：a[2] = 7
### 4. 使用時機
* max(),min(),gcd(),lcm()
* +, *, 矩陣乘法
* 線段樹上二分搜
二分搜 query 出來的答案需要 O(log^2^ n)
但直接在線段樹上二分搜只需要 O(log n)
A. 0 的個數 (搜尋第 k 個 0 在哪裡)
B. 給定前綴和
C. lower_bound
### 5. 進階技巧
* lazy tag (懶標)
懶標代表該區間應該被修改，但尚未操作
* 區間修改
#### 區間修改實作
經過含有懶標的節點時，順便推懶標
pull 之前確定左右子樹已被懶標作用
``` cpp=
typedef long long loli;
```
``` cpp=
void push(int l,int r,int v){
summ[v]+=tag[v]*(r-l);
if(r-l==1)
return tag[v]=0,void();
tag[2*v+1]+=tag[v];
tag[2*v+2]+=tag[v];
tag[v]=0;
}
```
``` cpp=
void pull(int l,int r,int v){
if(r-l==1)
return;
int mid=(l+r)/2;
push(l,mid,2*v+1);
push(mid,r,2*v+2);
summ[v]=summ[2*v+1]+summ[2*v+2];
}
```
**建樹**
遞迴把左右子樹建出來
拿建好的兩棵子樹合併出自己
``` cpp=
void build(int l,int r,int v=0){
if(r-l==1){
summ[v]=arr[l];
return;
}
int mid=(l+r)/2;
build(l,mid,2*v+1);
build(mid,r,2*v+2);
pull(l,r,v);
}
```
#### 區間查詢實作
在 [l,r) 中查詢 [L,R) 區間的答案
``` cpp=
loli query(int L,int R,int l,int r,int v=0){
push(l,r,v);
if(l==L && R==r) // 區間相同
return summ[v];
int mid=(l+r)/2;
if(R<=mid) // 在左半邊
return query(L,R,l,mid,2*v+1);
else if(mid<=L) // 在右半邊
return query(L,R,mid,r,2*v+2);
else // 區間橫跨中點
return query(L,mid,l,mid,2*v+1)
+query(mid,R,mid,r,2*v+2);
}
```
#### 區間修改實作
在 [l,r) 中將 [L,R) 區間的值增加 val
找到 [L,R) 後，將其懶標打上 val
``` cpp
void update(int L,int R,loli val,int l,int r,int v=0){
push(l,r,v);
if(l==L && R==r){
tag[v]+=val;
push(l,r,v);
return;
}
int mid=(l+r)/2;
if(R<=mid)
update(L,R,val,l,mid,2*v+1);
else if(mid<=L)
update(L,R,val,mid,r,2*v+2);
else
update(L,mid,val,l,mid,2*v+1),update(mid,R,val,mid,r,2*v+2);
pull(l,r,v);
}
```
### 6. 課後練習
[Codeforces - DZY Loves Fibonacci Numbers](https://codeforces.com/contest/446/problem/C)
[Codeforces - Circular RMQ](https://codeforces.com/problemset/problem/52/C)
[Kattis - Just for Sidekicks](https://open.kattis.com/problems/justforsidekicks)
[Codeforces - Array Stabilization (GCD version)](https://codeforces.com/problemset/problem/1547/F)
[Codeforces - Not Equal on a Segment](https://codeforces.com/contest/622/problem/C)
[Codeforces - Boring Segments](https://codeforces.com/contest/1555/problem/E)
[Ab Initio](https://open.kattis.com/problems/abinitio)
[Ultra-QuickSort](https://open.kattis.com/problems/ultraquicksort)
[Codeforces - NGGYU](https://www.youtube.com/watch?v=dQw4w9WgXcQ)
---
<font size = 5>結束了！！！好耶！！！
Sign in with Wallet
Connect another wallet