---
# System prepended metadata

title: 4/28

---

# 4/28
[TOC]
## STL
1. queue 簡介
    懂排隊就懂queue...先進先出 (First In, First Out)的概念。
    ![](https://i.imgur.com/PDExVMx.png =400x)


    ```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個節點是誰
