# 4/28
[TOC]
## STL
1. queue 簡介
懂排隊就懂queue...先進先出 (First In, First Out)的概念。
```cpp=
#include <queue>
...
int main {
// 1. 宣告
queue<int> q; // 和vector差不多 vector<int> v;
// 2. 加資料到queue裡
q.push(2); // front -> back: 2 end
q.push(3); // front -> back: 2 3 end
q.push(1); // front -> back: 2 3 1 end
q.push(4); // front -> back: 2 3 1 4 end
// 3. 刪除資料
q.pop(); // front -> back: 3 1 4 end
// 4. 查詢最前面排的人（數字）是什麼
cout << q.front() << endl; // "3"
// notice: 查詢隊伍中間是誰(X) -> 沒有此操作
// 5. 清空
while(q.empty() == false) q.pop();
while(q.size() != 0) q.pop();
while(q.size()) q.pop();
}
```
queue使用時機：
1. bfs
練習題 :
https://zerojudge.tw/ShowProblem?problemid=e155
https://zerojudge.tw/ShowProblem?problemid=e447
https://zerojudge.tw/ShowProblem?problemid=e564
如何將 queue裡面的元素clear掉
~~Que.clear();~~
queue沒有clear()函式
2. priority queue
想像有一個資料結構，把字料丟進去會幫你排序(由小到大)
`pq = [2, 3, 7, 9, 20]`
after insert 4
`pq = [2, 3, 4, 7, 9, 20]`
1. array 實作方法
`a = [2, 3, 7, 9, 20]`
找到4應該要在index=2的位置，把東西往後推
`a = [2, 3, , 7, 9, 20]`
再插入4
`a = [2, 3, 4, 7, 9, 20]`
insert時間複雜度$O(n)$
2. priority queue
把陣列編成一顆二元樹的形式，每次花費$O(logn)$的時間去維護好資料(insert)。
想了解內部怎麼做的可以從了解heap下手
實作方法和queue很像！
```cpp=
// code from cppreference: https://en.cppreference.com/w/cpp/container/priority_queue
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
// 印出priority_queue的內容（同時會把pq清空），queue也是用同樣的方法印。
void print_queue(auto q) { // NB: pass by value so the print uses a copy
while(!q.empty()) {
cout << q.top() << ' ';
// 注意queue取最前面的是用q.front()，
// priority_queue取最大值是用q.top()，因為他底層是一棵樹。
q.pop();
}
cout << '\n';
}
int main() {
const vector<int> data = {1,8,5,6,3,4,0,9,7,2};
// 初始化，把一個陣列丟給priority_queue
priority_queue<int> q;
for(int n : data) q.push(n);
// 上面兩行等同於
// priority_queue<int> q(data.begin(), data.end());
print_queue(q);
}
```
自定義排序規則
```cpp=
// 使用內過greater<>方法，讓priority_queue按照由小到大
priority_queue<int, vector<int>, greater<int>> q2(data.begin(), data.end());
print_queue(q2);
// 用lambda自定義比較方法
auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
for(int n : data) q3.push(n);
print_queue(q3);
```
練習題:
https://zerojudge.tw/ShowProblem?problemid=b606
## pbds
又稱黑魔法
[treap](https://byvoid.com/attachments/wp/2010/12/treap-analysis-and-application.pdf)是一個好用的資料結構，自己寫的話大概長這樣:
:::spoiler code
```cpp=
// 有人可以在5分鐘打完，我需要三天三夜 到三更半夜 飄浮只靠音樂
// srand(time(NULL))
//treap.init()
//treap.insert(val)
//treap.delet(val)
//treap.get_val(val) 印出val是第幾大
//treap.get_rank(val) 印出第val大的數
//treap.get_pre(val) 印出<val的max
//treap.get_next(val) 印出>val的min
const int maxn = 1e5+5;
struct node {
int sz, val, key, l, r;
};
struct Treap {
int tot = 1, root = 1;
node t[maxn];
int NEW(int val) {
t[tot] = {1, val, rand(), 0, 0};
return tot++;
}
void update(int now) {
t[now].sz = t[t[now].l].sz + t[t[now].r].sz + 1;
}
void merge(int &now, int a, int b) {
if( a == 0 || b == 0 ) {
now = a + b;
return;
}
else if( t[a].key < t[b].key) {
now = a;
merge(t[a].r, t[a].r, b);
}
else {
now = b;
merge(t[b].l, a, t[b].l);
}
update(now);
}
void split(int now, int &a, int &b, int val) {
if(now == 0) {
a = b = 0;
return;
}
if(t[now].val <= val) {
a = now;
split(t[a].r, t[a].r, b, val);
}
else {
b = now;
split(t[b].l, a, t[b].l, val);
}
update(now);
}
void find(int now, int rank) {
while(t[t[now].l].sz + 1 != rank) {
if(t[t[now].l].sz >= rank) now = t[now].l;
else rank -= t[t[now].l].sz + 1, now = t[now].r;
}
cout<<t[now].val<<endl;
}
void insert(int val) {
int a = 0, b = 0, nw = NEW(val);
split(root, a, b, val);
merge(a, a, nw);
merge(root, a, b);
}
void delet(int val) {
int a = 0, b = 0, d = 0;
split(root, a, b, val);
split(a, a, d, val-1);
merge(d, t[d].l, t[d].r);
merge(a, a, d);
merge(root, a, b);
}
void get_val(int val) {
find(root, val);
}
void get_rank(int val) {
int a = 0, b = 0;
split(root, a, b, val-1);
cout<<t[a].sz + 1<<endl;
merge(root, a, b);
}
void get_pre(int val) {
int a = 0, b = 0;
split(root, a, b, val-1);
find(a, t[a].sz);
merge(root, a, b);
}
void get_next(int val) {
int a = 0, b = 0;
split(root, a, b, val);
find(b, 1);
merge(root, a, b);
}
void init() {
memset(t, 0, sizeof(t));
NEW(2147483647);
t[1].sz = 0;
}
} treap;
```
:::
```cpp=
#include <bits/extc++.h>
using namespace __gnu_pbds;
tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> tree;
/*
null_type //无映射(低版本g++为null_mapped_type)
less<int> //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式
*/
tr.insert(x); //插入;
tr.erase(x); //删除;
tr.order_of_key(x); //求排名
tr.find_by_order(k); //找k小值，返回迭代器
tr.join(tr2); //将b并入tr，前提是两棵树类型一样且没有重复元素
tr.split(k, tr2); //分裂，key小于等于k的元素属于tr，其余的属于b
tr.lower_bound(x); //返回第一个大于等于x的元素的迭代器
tr.upper_bound(x); //返回第一个大于x的元素的迭代器
//以上所有操作的时间复杂度均为O(logn)
```
## 打競技程式會用到的語法
一些很髒的東西...
1. 萬用標頭檔
把你比賽會用到的函式庫都include進去了！
缺點：本機編譯速度會比較慢:(
```cpp=
#include <bits/stdc++.h>
```
3. 把型別簡寫
```cpp=
using ll = long long;
int main() {
ll a = 1e18;
}
```
2. 把一堆東西define簡寫簡寫
```cpp=
#define for0(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define all(a) (a).begin(), (a).end();
int main() {
srand(time(0));
int n = 20;
vector<int> v;
// for(int i = 0; i < n; i++) v.push_back(i);
for0(i, n) v.pb(i);
//random_shuffle(v.begin(), v.end());
random_shuffle(all(v));
// for(int i = 0; i < n; i++) cout << v[i] << endl;
for(int t : v) cout << t << endl;
}
```
3. pair
相當於以下的東西，運算子(<, >, >=, <=)已經內建好了，會先比較第一個數值(first)，再比較第二個數值。
```cpp=
struct pair {
int first;
int second;
}
```
```cpp=
pair<int, int> p = {1, 2};
cout << p.first << ' ' << p.second;
```
一樣用#define增加一點便利性
```cpp=
#define for0(i, n) for(int i = 0; i < n; i++)
#define pb push_back
using ii = pair<int, int>;
#define fs first
#define sc second
int main() {
vector<ii> v;
for0(i, 10) {
v.pb({i+5, i-5});
}
// 輸出第一種方法
for(ii p : v) {
cout << p.fs << ' ' << p.sc << endl;
}
// 輸出第二種方法
for(auto [f, s] : v) {
cout << f << ' ' << s << endl;
}
}
```
5. debug模板
```cpp=
#define deg(x) cout << (#x) << "=" << x << endl;
```
```cpp=
#ifdef acacac
#define deg(x) cout << (#x) << "=" << x << endl;
#elseif
#define deg(x)
#endif
```
在編譯器那邊設定
```shell=
-Dacacac
```
6. 很髒的強制轉型
你寫了一段程式碼，發現忘記開long long...
```cpp=
using ii = pair<int, int>;
int main() {
int n, sum = 0;
cin >> n;
}
```
。。。。。
```cpp=
#define int long long
...
signed main() {
...
}
```
6. 我很醜的模板...
:::spoiler 我很抱歉寫出這麼醜的東西...
```cpp=
#include <bits/stdc++.h>
using namespace std;
#ifndef LONGLONG
#define LONGLONG
#define int long long
#endif
using ll = long long;
using pi = pair<int, int>;
using vec = vector<int>;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define forr(i, a, n) for(int i = n; i >= a; i--)
#define fs first
#define sc second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define CASE int _T; cin >> _T; for1(tt, _T)
// DEBUG TEMPLATE (from tourist)
template <typename A, typename B>
string to_string(pair<const auto&, const auto&>);
string to_string(const string& s) { return '"' + s + '"'; } // string -> string
string to_string(bool b) { return (b ? "true" : "false"); } // bool -> string
string to_string(const auto &v) {
string res = "";
for(auto it = v.begin(); it != v.end(); res += to_string(*it++) + ",");
return "{" + res + "}";
}
template <typename A, typename B> // pair -> string
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
void dbg() { cerr << endl; }
template<class T, class ...Args> void dbg(const T& x, const Args&... rest) {
cerr << " " << to_string(x);
dbg(rest...); }
#ifdef rrr
#define wer(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]:", dbg(__VA_ARGS__)
#else
#define wer(...)
#endif
void setup() {
#ifdef rrr
cout << "┌---------------------------┐\n";
#ifdef LONGLONG
cout << "| int is now long long |\n";
#endif
cout << "└---------------------------┘\n";
#else
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#endif
}
/*-+-+-+-+-+-+-+-+-+- have fun -+-+-+-+-+-+-+-+-+-*/
signed main() { setup();
}
```
:::
## 樹相關主題
1. [樹直徑](https://drive.google.com/file/d/1Ciq-dur4CGBiSDes9bpoXPEN_5Vteo9W/view?usp=sharing)
[code](https://ideone.com/kUke4t)
3. 任一點的子樹大小
4. 任一點的子樹節點個數
5. [任一點到其他點的距離總和]((https://drive.google.com/file/d/1uLCUu0JszAILn0zsiSt63HCGaKTBw-bh/view?usp=sharing))
6. RMQ sparse table
:::spoiler code
```cpp=
//RMQ Sparse table
#define p2(i) (1<<(i))
const int maxn = 2e5 + 50;
int rm[maxn][__lg(maxn)];
void build_RMQ() { //build RMQ from a array
rep0(i,n) rm[i][0] = a[i];
rep1(k,__lg(n))
for(int i=0;i<=n-p2(k);i++)
rm[i][k] = min(rm[i][k-1],rm[i+p2(k-1)][k-1]);
}
int query(int l, int r) {
int k = __lg(r-l+1);
return min(rm[l][k], rm[r-p2(k)+1][k]);
}
```
:::
7. 樹上一條鏈的倍增（我頭上第k個節點是誰
Sign in with Wallet
Connect another wallet