---
title: 2021 一中資奧研習
slideOptions: # 簡報相關的設定
theme: solarized # 顏色主題
---

# 2021 一中資奧研習

<!-- Put the link to this slide here so people can follow -->
slide: https://bit.ly/2M2ueUN

---

# Who am I?

- 張集貴
- [pr3pony](https://clist.by/coder/pr3pony/) :heart: :carousel_horse:
- i use arch btw
<!--{%youtube E8Nj7RwXf0s %}-->

----

- 2014 會 Hello World! 的高一
- 2015 全國賽, 差 2 名三等獎
- 2016 入營考, 沒進
- 2016 全國賽第四名
- 2017 TOI 2! 第九名

---

# outline
- 選手之路
- DEBUG
- 基本演算法：複雜度，C++ STL，枚舉，二分，排序
- DS
- 圖論

----

- DS 內建ㄉ：
- array
- stack
- queue
- deque
- priority queue(heap)

----

- DS 要自己寫ㄉ：
- DSU
- 前綴和
- 分塊法
- Segment tree
- Fenwick tree
- Treap
- 可持久化線段樹
- 可持久化 Treap
- 時間線段樹 + 可回溯 DSU

----

- 圖論
- DFS, BFS
- MST
- 單源最短路
- 全點對最短路
- 樹直徑
- 樹 LCA
https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all

---

# 選手之路
[演算法比賽網路資源整理](https://hackmd.io/@xQGCDZGPSKutcn2ux55kvA/HysEHoYe8)

----

## 主線任務
- 整年: TOI 海選, APCS
- 上學期
- ? 月校內初選
- 11 月中區賽
- 12 月全國賽，前 10 名進入 TOI 1!
- 下學期
- 3 月初 TOI 初選，前 20 名進入 TOI 1!
- 3 月中 TOI 1!，前 12 名進入 TOI 2!
- 4 月中 TOI 2!，前 4 名成為 IOI 國手
- https://ioi2021.sg/

----

## 支線任務
- NPSC
- ISSC
- HP CodeWars
- TOI 2! 成員可比 APIO
- YTP 少年圖靈計畫

----

## 線上大賽（拿 T-shirt!）
- Google Code Jam
- TopCoder Open
- Facebook Hacker Cup

----

## 變強的方法
[SECRET](https://youtu.be/dQw4w9WgXcQ)

----

## 刷題網站
- [code-drills](https://recommender.codedrills.io/profile?handles=pr3pony)
- [AtCoder Problems](https://kenkoooo.com/atcoder/#/table/pr3pony)
- [OI Checklist](https://oichecklist.pythonanywhere.com/)

----

## 考古題
- [~2018入營考考古題 ](https://tioj.ck.tp.edu.tw/contests/70)
- [~2015 全國賽考古題](https://tioj.ck.tp.edu.tw/contests/46)
- [TIOJ 全國賽考古題](https://tioj.ck.tp.edu.tw/problems?tag=%E5%85%A8%E5%9C%8B%E8%B3%BD)
- [ZeroJudge 全國賽考古題](https://zerojudge.tw/Problems?tag=%E5%85%A8%E5%9C%8B)
- [2015 ~ 2020 TOI 模考題目 - 資訊競賽選手新手村](https://www.facebook.com/groups/1500275723594463/files)
- [部份 TOI 模考題目](https://tioj.ck.tp.edu.tw/problems?tag=TOI)

----

## 廣告(?)
[USACO Second Contest: Jan 22-25](http://usaco.org/index.php)

----

## 活動
- 台大 [IOICamp](https://www.facebook.com/ioicamp/)
- 交大 [PCCA Winter Camp](https://www.facebook.com/NCTUPCCA)
- 清大 [ION Camp](https://www.facebook.com/nthuioncamp/)

---

# DEBUG
- 用看的
- printf 大法
- assert 大法
- sanitizer 大法

----

## printf 大法
- fprintf(stderr, "x = %d\n", x);
- cerr << "x = " << x << endl;
- puts("meow"); 二分搜壞掉行數
- default code 裡放輸出 macro: [例一](https://codeforces.com/contest/1444/submission/97321479) [例二](https://codeforces.com/contest/1467/submission/104600563)

----

## assert 大法

#include <bits/stdc++.h>
using namespace std;
template<typename T> void mysort(T a, T b) {/*miracle!*/}
int main()
{
    int n;
    assert(cin >> n);
    assert(n >= 0);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        assert(cin >> a[i]);
    mysort(a.begin(), a.end());
    assert(is_sorted(a.begin(), a.end()));
}

- assert 自己算法保證的東西
- assert 輸入符合範圍
- <del>偷測資</del>

----

## sanitizer 大法

$ g++ a.cpp -fsanitize=address -fsanitize=undefined -g

題外話： -Wall -Wextra -Wconversion -Wshadow

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << a[0] * a[0] << endl;
    cout << a[87] << endl;
}

---

# 複雜度

---

# C++ STL

---

# 枚舉

---

# 二分

----

假設有一個函數 $ok : \{ 1,2,\cdots,n \}\rightarrow \{true, false\}$，且存在 $i$ 滿足 $ok(j) = true \Leftrightarrow j \le i$

int l = 1, r = n;
while (l <= r) {
    int m = l + (r - l) / 2;
    if (ok(m))
        l = m + 1;
    else
        r = m - 1;
}

while 結束後
- $l=i+1, r = i$
- $l$ 是第一個 false, $r$ 是最後一個 true

----

## 單一指標的二分搜

int p = 0;
for (int s = 1 << __lg(n); s; s >>= 1)
    if (p + s <= n && ok(p + s))
        p += s;

for 結束後，$p=i$

---

# 排序

----

## insertion sort

for (int i = 1; i < n; ++i)
    for (int j = i; j > 0 && a[j] < a[j - 1]; --j)
        swap(a[j], a[j - 1]);

----

## quick sort

----

## merge sort
- 例題：逆序數對
- https://tioj.ck.tp.edu.tw/problems/1080
- https://judge.tcirc.tw/ShowProblem?problemid=d064
- https://zerojudge.tw/ShowProblem?problemid=a457

---

# array

#include<algorithm>
#include<cassert>
#include<cstring>
using namespace std;
const int N = 1e6 + 87;
int tmp[N];
int tmd[1'588'806]; // single quote separator (since C++ 14)
int main()
{
    for (int i = 0; i < N; ++i) assert(tmp[i] == 0);
    fill_n(tmp, N, 1e9); 
    memset(tmd, 0x78, sizeof tmd);
    for (int i = 0; i < 1588806; ++i) {
        assert(tmd[i] == 0x78787878); 
        assert(tmd[i] == 2021161080);
    }
    int tmt[514] = {};
    for (int & x : tmt) {
        assert(x == 0);
        x = 514;
    }
    // swap(tmt, tmp); // CE
    int * PrincessTwilight = tmt, * PinkiePie = tmp;
    assert(PrincessTwilight[5] == 514 && PinkiePie[0] == 1e9);
    swap(PrincessTwilight, PinkiePie);
    assert(PrincessTwilight[5] == 1e9 && PinkiePie[0] == 514);
    PinkiePie = new int [N]();
    for (int i = 0; i < N; ++i)
        assert(PinkiePie[i] == 0);
}

----

## std::vector

#include<algorithm>
#include<cassert>
#include<vector>
using namespace std;
int main()
{
    int N = 1450;
    vector<long long> a(N, 87);
    auto b = a;
    assert(b.size() == 1450);
    for (long long x : b) assert(x == 87);
    a.assign(1450145, 0x123456789abcdef0);
    b.resize(514514, 0x123456789abcdef0);
    for (int i = 0; i < 1450; ++i)
        assert(b[i] == 87);
    for (int i = 1450; i < 514514; ++i)
        assert(b[i] == 0x123456789abcdef0);
    a.swap(b); b.swap(a); // O(1)
    swap(a, b); //  O(1)
    assert(b.size() == 1450145);
    for (auto x : b) assert(x == 0x123456789abcdef0);
}

----

## std::array

#include<algorithm>
#include<cassert>
#include<array> // since C++ 11
using namespace std;
const int N = 1e6 + 87;
array<double, N> c, d;
int main()
{
    for (int i = 0; i < N; ++i) assert(c[i] == 0);
    for (int i = 0; i < N; ++i) assert(d[i] == 0);
    c.fill(8.7); d.fill(6.5);
    for (auto x : d) assert(x == 6.5);
    for (auto x : c) assert(x == 8.7);
    swap(c, d); // O(1)
    for (auto x : d) assert(x == 8.7);
    for (auto x : c) assert(x == 6.5);
}

---

# stack

- LIFO
- DFS
- 括號匹配

----

## 例題

----

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
const int N = 100000 + 87;
int n, h[N], lt[N], rt[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    while (cin >> n, n) {
        h[0] = h[n + 1] = -1;
        for (int i = 1; i <= n; ++i)
            cin >> h[i];
        stack<int> s;
        s.push(0);
        for (int i = 1; i <= n; ++i) {
            while (h[s.top()] >= h[i])
                s.pop();
            lt[i] = s.top();
            s.push(i);
        }
        while (s.size()) s.pop();
        s.push(n + 1);
        for (int i = n; i >= 1; --i) {
            while (h[s.top()] >= h[i])
                s.pop();
            rt[i] = s.top();
            s.push(i);
        }
        long long ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, (rt[i] - lt[i] - 1ll) * h[i]);
        cout << ans << '\n';
    }
}

---

# queue

- FIFO
- BFS

----

## 例題

----

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN (1000 + 42)
#define R first
#define C second
using namespace std;
typedef pair<int, int> pii;
char g[MAXN][MAXN];
int b[MAXN][MAXN];
int w[MAXN][MAXN];
int R, C;
pii d[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

pii walk(pii a, pii b) {
    a.R += b.R;
    a.C += b.C;
    return a;
}

bool inrange(pii p) {
    return 0 <= p.R && p.R < R && 0 <= p.C && p.C < C;
}

bool block(pii p) {
    return g[p.R][p.C] == '#';
}

int& burn_t(pii p) {
    return b[p.R][p.C];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        queue<pii> f, j;
        scanf("%d%d ", &R, &C);
        for (int r = 0; r < R; r++)
            memset(b[r], -1, C * sizeof(int));
        for (int r = 0; r < R; r++)
            memset(w[r], -1, C * sizeof(int));
        for (int r = 0; r < R; r++) {
            fgets(g[r], sizeof(g[r]), stdin);
            for (int c = 0; c < C; c++)
                switch (g[r][c]) {
                    case 'F':
                        b[r][c] = 0;
                        f.push({r, c});
                        break;
                    case 'J':
                        w[r][c] = 0;
                        j.push({r, c});
                        break;
                }
        }
        while (!f.empty()) {
            pii p = f.front();
            f.pop();
            int t = burn_t(p) + 1;
            for (pii x : d) {
                pii n = walk(p, x);
                if (inrange(n) && !block(n) && burn_t(n) == -1) {
                    burn_t(n) = t;
                    f.push(n);
                }
            }
        }
        int fin = -1;
        while (!j.empty()) {
            pii p = j.front();
            j.pop();
            int t = w[p.R][p.C] + 1;
            for (pii x : d) {
                pii n = walk(p, x);
                if (inrange(n)) {
                    if (!block(n) && (burn_t(n) > t || burn_t(n) == -1) && w[n.R][n.C] == -1) {
                        w[n.R][n.C] = t;
                        j.push(n);
                    }
                } else {
                    fin = t;
                    goto output;
                }
            }
        }
output:
        if (fin != -1)
            printf("%d\n", fin);
        else
            puts("IMPOSSIBLE");
    }
}    

---

# deque

- push_front
- push_back
- pop_front
- pop_back
- 完全可以取代 stack 跟 queue！:satisfied:

----

## 例題

TIOJ 1566：簡單易懂的現代都市
有一個長度 $N$ 的正整數序列 $h[1,N]$，
輸出所有滿足 $max(h[L,R]) - min(h[L,R]) = K$ 的長度為 M 的區間 $(L, R)$。
（($L = 1$ 或 $R = N$) 且長度不超過 $M$ 的區間也算）
（$N \leq 10^7, M \leq 10^6, 1 \leq h_i, K \leq 2^{31}$）
[\CSY教我/](https://csy54.github.io/2019/02/TIOJ-1566/)

----

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    ll k;
    cin >> n >> m >> k;
    m = min(m, n);
    deque<pll> mn, mx;
    vector<pii> ans;
    for (int i = 0; i < n + m - 2; ++i) {
        if (i < n) {
            ll h;
            cin >> h;
            while (mn.size() && mn.back().second >= h)
                mn.pop_back();
            mn.emplace_back(i, h);
            while (mx.size() && mx.back().second <= h)
                mx.pop_back();
            mx.emplace_back(i, h);
        }
        while (mn.front().first + m <= i)
            mn.pop_front();
        while (mx.front().first + m <= i)
            mx.pop_front();
        if (mx.front().second - mn.front().second == k)
            ans.emplace_back(max(0, i - m + 1), min(n - 1, i));
    }
    cout << ans.size() << endl;
    for (auto x : ans)
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
}

---

# priority queue
- usually implemented with binary heap
- Dijkstra's algorithm

----

## 例題
UVa 11367: Full Tank?

給你一張 $n$ 點 $m$ 邊有邊權的無向圖，第 $i$ 條邊的權重是 $d_i$，
你是一台車子，走一單位距離要花一單位油，你的油箱容量上限是 $c$，
每個節點是一個加油站，在點 $i$ 加一單位油的價錢是 $p_i$，
求從給定的起點走到終點最少要花多少錢。
($n \le 1000, m \le 10000, c \le 100$, $1 \le p_i, d_i \le 100$)

----

$dp[w][i] = 從起點走到 i 且油箱剩下 w 單位油的最小花費$

發現等價在一張 $V = n \times (c + 1)$ 的圖上找最短路。
用 Dijkstra 去更新 dp 表格。

----

#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const int maxn = 1024;
const int maxc = 125;
const int inf = 0x7f7f7f7f;
int p[maxn];
typedef pair<int,int> pii;
vector<pii> g[maxn];
int minc[maxn * maxc];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		scanf("%d", p + i);
	while (m--) {
		int u, v, d;
		scanf("%d%d%d", &u, &v, &d);
		g[u].emplace_back(d, v);
		g[v].emplace_back(d, u);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int c, s, e;
		scanf("%d%d%d", &c, &s, &e);
		priority_queue<pii, vector<pii>, greater<pii> > pq;
		memset(minc, 0x7f, (c + 1) * n * sizeof(int));
		minc[s] = 0;
		pq.push({0, s});
		while (pq.size()) {
			pii t = pq.top();
			pq.pop();
			pii u(t.second / n, t.second % n);
			if (t.first > minc[t.second])
				continue;
			else if (u.second == e)
				break;
			int nxt;
			if (u.first < c) {
				int cost = t.first + p[u.second];
				nxt = (u.first + 1) * n + u.second;
				if (minc[nxt] > cost) {
					minc[nxt] = cost;
					pq.push({cost, nxt});
				}
			}
			for (const pii & x : g[u.second])
				if (u.first >= x.first) {
					nxt = (u.first - x.first) * n + x.second;
					if (minc[nxt] > t.first) {
						minc[nxt] = t.first;
						pq.push({t.first, nxt});
					}
				}
		}
		if (minc[e] < inf)
			printf("%d\n", minc[e]);
		else
			puts("impossible");
	}
}

---

# DSU

maintains a partition of a finite set

----


----

#include <bits/stdc++.h>
const int MAXN = 100001;
#define U first
#define V second
using namespace std;
typedef pair<int, int> pii;
pii edges[MAXN];
int qry[MAXN];
bool ruin[MAXN];
int ans[MAXN];
struct DS
{
    vector<int> p, s;
    int setn;
    DS(int n)
    {
        p.resize(n + 1);
        iota(begin(p), end(p), 0);
        s.assign(n + 1, 1);
        setn = n;
    }
    int Find(int x)
    {
        return x == p[x] ? x : p[x] = Find(p[x]);
    }
    void Union(int x, int y)
    {
        x = Find(x); y = Find(y);
        if (x == y)
            return;
        if (s[x] > s[y])
            swap(x, y);
        p[x] = y;
        s[y] += s[x];
        setn--;
    }
};
int main()
{
    int n, m, q;
    cin >> n >> m;
    DS s(n);
    for (int i = 1; i <= m; i++)
        cin >> edges[i].U >> edges[i].V;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> qry[i];
        ruin[qry[i]] = true;
    }
    for (int i= 1; i <= m; i++)
        if (!ruin[i])
            s.Union(edges[i].U, edges[i].V);
    for (int i = q - 1; i >= 0; i--) {
        ans[i] = s.setn;
        s.Union(edges[qry[i]].U, edges[qry[i]].V);
    }
    for (int i = 0; i < q - 1; i++)
        cout << ans[i] << ' ';
    cout << ans[q-1] << endl;
}

----

## 酷炫實做

struct DS
{
    vector<int> p, s;
    int setn;
    DS(int n)
    {
        p.assign(n + 1, -1);
        setn = n;
    }
    int Find(int x)
    {
        return p[x] < 0 ? x : p[x] = Find(p[x]);
    }
    void Union(int x, int y)
    {
        x = Find(x); y = Find(y);
        if (x == y)
            return;
        if (-p[x] > -p[y])
            swap(x, y);
        p[y] += p[x];
        p[x] = y;
        setn--;
    }
};

---

# 前綴和
區間和問題
給 $N(N \le 10^8)$ 個數字 $v_i(1\le i\le N)$，跟$Q(Q \le 10^8)$筆詢問
- query l r: 詢問區間 $[l,r]$ 的總和
https://zerojudge.tw/ShowProblem?problemid=e346

----

long long v[N + 1], s[N +１];
for (int i = 1; i <= n; ++i)
    s[i] = s[i - 1] + v[i];
while (Q--) {
    int l, r;
    cin >> l >> r;
    cout << s[r] - s[l - 1] << '\n';
}

---

# 分塊法

----

### 區間和問題
給 $N(N \le 10^5)$ 個數字 $v_i(1\le i\le N)$，跟$Q(Q \le 10^5)$筆操作，操作包含兩種：
- add i d: 將 $v_i$ 加上 $d$
- query l r: 詢問區間 $[l,r]$ 的總和
https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

----

- naive 做法：修改 $O(1)$, 查詢 $O(N) \rightarrow$ TLE
- 前綴和：修改 $O(N)$, 查詢 $O(1) \rightarrow$ TLE
- 每 $S$ 個一塊，每塊存一個和？
- 修改 O(1)，查詢 $O(S + N/S)$
- S 取 $\sqrt{N} \Rightarrow O(\sqrt{N})$

----

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZE = sqrt(MAXN);
int a[MAXN], b[MAXN / SIZE + 1];
void add(int i, int d)
{
   a[i] += d; 
   b[i / SIZE] += d;
}
int query(int i)
{
    int ret = 0, k = i / SIZE;
    for (int j = 0; j < k; ++j)
        ret += b[j];
    for (int j = k * SIZE; j <= i; ++j)
        ret += a[j];
    return ret;
}
int query(int l, int r)
{
    return query(r) - query(l - 1);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    while (q--) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0)
            add(x, y);
        else
            cout << query(x, y) << '\n';
    }
}

----

### RMQ 問題
給 $N(N \le 10^5)$ 個數字 $v_i(0 \le i\le N-1)$，跟$Q(Q \le 10^5)$筆操作，操作包含兩種：
- add i d: 將 $v_i$ 設為 $d$
- query l r: 詢問區間 $[l,r]$ 的最小值
https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_A

----

- 不能用前綴和了
- 分塊：更新 $O(S)$，查詢 $O(S+N/S)$
- 更新：重新計算一塊的 min
- 查詢：
- $l$ 那塊：$O(S)$
- $r$ 那塊：$O(S)$
- 中間那些塊：$O(N/S)$

----

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZE = sqrt(MAXN);
int n, q, a[MAXN], b[MAXN / SIZE + 1];
void upd(int i, int d)
{
   a[i] = d; 
   int k = i / SIZE;
   b[k] = INT_MAX;
   for (int j = k * SIZE; j < (k + 1) * SIZE && j < n; ++j)
       b[k] = min(b[k], a[j]);
}
int query(int l, int r)
{
    int ret = INT_MAX;
    int kl = l / SIZE, kr = r / SIZE;
    if (kl == kr) {
        for (int j = l; j <= r; ++j)
            ret = min(ret, a[j]);
    } else {
        for (int j = l; j < (kl + 1) * SIZE; ++j)
            ret = min(ret, a[j]);
        for (int j = kr * SIZE; j <= r; ++j)
            ret = min(ret, a[j]);
        for (int j = kl + 1; j < kr; ++j)
            ret = min(ret, b[j]);
    }
    return ret;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    fill_n(a, n, INT_MAX);
    fill_n(b, (n - 1) / SIZE + 1, INT_MAX);
    while (q--) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 0)
            upd(x, y);
        else
            cout << query(x, y) << '\n';
    }
}

---

# Segment tree

----

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

----

給 $N=5$、$v=1,16,2,8,4$，則線段樹每個節點代表的區間資訊如下圖所示。

----

假設我們想知道區間 $[1,4]$ 的總和，原本需要跑過陣列 $1 \sim 4$，現在只需要得到 $[1,3]$ 以及 $[4,4]$ 節點的資訊再將他們加總即可得知。可以證明的是如此一來查詢的複雜度爲 $O( \lg N )$。

----

一般而言，線段樹都會包含三個主要的函式：
- build: 初始化線段樹
- modify: 修改線段樹，又分爲區間修改或單點修改
- query: 線段樹查詢區間資訊

----

## pointer implementation
### node

typedef long long ll;
struct Node{
  ll val;
  Node *lc , *rc;
  Node(){ val = 0; lc = rc = NULL; }
  void pull(){
    val = lc->val + rc->val;
  }
};
int n , v[ N ]; // assume already stored the input
// v is 1-indexed here

----

### build

Node* build( int L , int R ){
  Node *node = new Node();
  if( L == R ){
    node->val = v[ L ];
    return node;
  }
  int mid = ( L + R ) >> 1;
  node->lc = build( L , mid );
  node->rc = build( mid + 1 , R );
  node->pull();
  return node;
}

----

### modify

void modify( Node* node , int L , int R , int i , int d ){
  if( L == R ){
    assert( L == i );
    node->val += d;
    return;
  }
  int mid = ( L + R ) >> 1;
  if( i <= mid ) modify( node->lc , L , mid , i , d );
  else modify( node->rc , mid + 1 , R , i , d );
  node->pull();
}

----

### query

ll query( Node* node , int L , int R , int ql , int qr ){
  if( ql > R || qr < L ) return 0;
  if( ql <= L && R <= qr ) return node->val;
  int mid = ( L + R ) >> 1;
  return query( node->lc , L , mid , ql , qr ) +
         query( node->rc , mid + 1 , R , ql , qr );
}

----

## array implementation
### heap indexing

- $root = 1, left\_child(i) = 2i, right\_child(i) = 2i+1$
- 從長度 $2^k$ 的陣列建構的線段樹會把 $[1,2^{k+1}-1]$ 的編號用好用滿
- 令 $k = \lceil \lg(N) \rceil$， $2N \ge 2^k$, $4N \ge 2^{k+1}-1$
- 開 $4N$ 一定安全！

----

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 87;
typedef long long ll;
int n , v[ N ]; // assume already stored the input
// v is 0-indexed here
ll t[N * 4];
void pull(int o)
{
    t[o] = t[o + o] + t[o + 1 + o];
}
// \左閉右開/
void build(int o = 1, int l = 0, int r = n) 
{
    if (r - l == 1) {
        t[o] = v[l];
        return;
    }
    int m = l + (r - l) / 2;
    build(o + o, l, m);
    build(o + 1 + o, m, r);
    pull(o);
    return;
}
void modify(int i, int d, int o = 1, int l = 0, int r = n)
{
    if (r - l == 1) {
        assert( l == i );
        t[o] += d;
        return;
    }
    int m = l + (r - l) / 2;
    if (i < m)
        modify(i, d, o + o, l, m);
    else
        modify(i, d, o + 1 + o, m, r);
    pull(o);
    return;
}
ll query(int ql, int qr, int o = 1, int l = 0, int r = n)
{
    if (ql >= r || qr <= l)
        return 0;
    if (ql <= l && r <= qr)
        return t[o];
    int m = l + (r - l) / 2;
    return query(ql, qr, o + o, l, m) +
        query(ql, qr, o + 1 + o, m, r);
}

----

## array implementation
### Euler tour indexing

長度 $N$ 的陣列建構的線段樹只會用到恰 $2N-1$ 個節點，前面 heap indexing 需要至多 $4N$ 空間，能否開剛好？
觀察在線段樹上 dfs （先走左子樹再走右子樹），會得到一個自然的編號方法，能把 $[1,2N-1]$ 用好用滿！

----

- 一個節點用左閉右開的區間 $[l,r)$ 來表示
$m = \lfloor \frac{l + r}{2} \rfloor = l + \lfloor \frac{r - l}{2} \rfloor = l + \lfloor \frac{len}{2} \rfloor$
左孩子是 $[l,m)$，右孩子是 $[m,r)$
- $left\_child(i) = i + 1$ 因為先走左子樹
- $right\_child(i) = i + \lfloor \frac{len}{2} \rfloor \times 2$
因為左子樹的區間長為 $\lfloor \frac{len}{2} \rfloor$，會用到 $\lfloor \frac{len}{2} \rfloor \times 2 - 1$ 個連續的編號，
下一個沒用到的編號是 $i + (\lfloor \frac{len}{2} \rfloor \times 2 - 1) + 1 = i + \lfloor \frac{len}{2} \rfloor \times 2$
- 比 heap indexing 更加 cache friendly (?

----

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 87;
typedef long long ll;
int n , v[ N ]; // assume already stored the input
// v is 0-indexed here
ll t[N * 2];
void pull(int o, int z)
{
    t[o] = t[o + 1] + t[z];
}
// \左閉右開/
void build(int o = 1, int l = 0, int r = n)
{
    if (r - l == 1) {
        t[o] = v[l];
        return;
    }
    int m = l + (r - l) / 2;
    int z = o + (r - l) / 2 * 2;
    build(o + 1, l, m);
    build(z, m, r);
    pull(o, z);
    return;
}
void modify(int i, int d, int o = 1, int l = 0, int r = n)
{
    if (r - l == 1) {
        assert( l == i );
        t[o] += d;
        return;
    }
    int m = l + (r - l) / 2;
    int z = o + (r - l) / 2 * 2;
    if (i < m)
        modify(i, d, o + 1, l, m);
    else
        modify(i, d, z, m, r);
    pull(o, z);
    return;
}
ll query(int ql, int qr, int o = 1, int l = 0, int r = n)
{
    if (ql >= r || qr <= l)
        return 0;
    if (ql <= l && r <= qr)
        return t[o];
    int m = l + (r - l) / 2;
    int z = o + (r - l) / 2 * 2;
    return query(ql, qr, o + 1, l, m) +
        query(ql, qr, z, m, r);
}

----

## 區間修改-懶標記(lazy propagation)
https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G

----

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
  ll val , tag;
  Node *lc , *rc;
  Node(){ tag = val = 0; lc = rc = NULL; }
  void pull(){
    val = lc->val + rc->val;
  }
};
const int N = 1e6 + 87;
int n , v[ N ]; // assume already stored the input
Node* build( int L , int R ){
  Node *node = new Node();
  if( L == R ){
    node->val = v[ L ];
    return node;
  }
  int mid = ( L + R ) >> 1;
  node->lc = build( L , mid );
  node->rc = build( mid + 1 , R );
  node->pull();
  return node;
}
void apply( Node * node , int L , int R , ll d ){
    node->tag += d;
    node->val += d * ( R - L + 1 );
}
void push( Node* node , int L , int R ){
  if( !node->tag ) return;
  int mid = ( L + R ) >> 1;
  apply( node->lc , L , mid , node->tag );
  apply( node->rc , mid + 1 , R , node->tag );
  node->tag = 0;
}
void modify( Node* node , int L , int R , int ql , int qr , ll d ){
  if( ql > R || qr < L ) return;
  if( ql <= L && R <= qr ){
    apply( node , L , R , d );
    return;
  }
  push( node , L , R );
  int mid = ( L + R ) >> 1;
  modify( node->lc , L , mid , ql , qr , d );
  modify( node->rc , mid + 1 , R , ql , qr , d );
  node->pull();
}
ll query( Node* node , int L , int R , int ql , int qr ){
  if( ql > R || qr < L ) return 0;
  if( ql <= L && R <= qr ) return node->val;
  push( node , L , R );
  int mid = ( L + R ) >> 1;
  return query( node->lc , L , mid , ql , qr ) +
    query( node->rc , mid + 1 , R , ql , qr );
}
void clear( Node * node )
{
  if ( !node )
    return;
  clear( node->lc );
  clear( node->rc );
  delete node;
}
int main(){
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &v[i]);
  Node* root = build( 1 , n ); 
  while (q--) {
    int ot, l, r, x;
    scanf("%d%d%d", &ot, &l, &r);
    if (ot == 1) {
      scanf("%d", &x);
      modify( root , 1 , n , l , r , x ); 
    } else {
      printf( "%lld\n" , query( root , 1 , n , l , r ) ); 
    }
  }
  clear(root);
}

----

打上標記函數：

void apply( Node * node , int L , int R , ll d ){
    node->tag += d;
    node->val += d * ( R - L + 1 );
}

push 函數：

void push( Node* node , int L , int R ){
  if( !node->tag ) return;
  int mid = ( L + R ) >> 1;
  apply( node->lc , L , mid , node->tag );
  apply( node->rc , mid + 1 , R , node->tag );
  node->tag = 0;
}

----

修改線段樹與懶標記六部曲：
- 區間沒有交集，即return
- $[L,R] \subseteq [ql,qr]$，修改資訊，打上標記，return
- push 懶標記
- 修改左子樹
- 修改右子樹
- pull
- $O(\lg n)$

----

void modify( Node* node , int L , int R , int ql , int qr , ll d ){
  if( ql > R || qr < L ) return;
  if( ql <= L && R <= qr ){
    apply( node , L , R , d );
    return;
  }
  push( node , L , R );
  int mid = ( L + R ) >> 1;
  modify( node->lc , L , mid , ql , qr , d );
  modify( node->rc , mid + 1 , R , ql , qr , d );
  node->pull();
}

----

查詢線段樹與懶標記六步驟：
- 區間不相交，回傳不影響答案之值
- $[L,R] \subseteq [ql,qr]$，回傳節點上的資訊
- push 懶標記
- 收集左子樹查詢之資訊
- 收集右子樹查詢之資訊
- 回傳兩子樹資訊結合後之結果
- $O(\lg n)$

----

ll query( Node* node , int L , int R , int ql , int qr ){
  if( ql > R || qr < L ) return 0;
  if( ql <= L && R <= qr ) return node->val;
  push( node , L , R );
  int mid = ( L + R ) >> 1;
  return query( node->lc , L , mid , ql , qr ) +
    query( node->rc , mid + 1 , R , ql , qr );
}

----

什麼都會了？！

// 查詢：區間乘法
void pull(){val = lc->val * rc->val;}
// 查詢：區間最小值
void pull(){val = min(lc->val, rc->val);}
// 查詢：區間 gcd
void pull(){val = gcd(lc->val, rc->val);}

要有結合律的運算才能用線段樹維護！

---

# Fenwick tree

- Binary Indexed Tree
- BIT

----

input = $a[1...n]$
$s[i] = \sum_{j=i−lowbit(i)+1}^{i}a[j]$
$sum(i) = a[1] + a[2] + \cdots + a[i]$
$= s[i] + sum(i - lowbit(i))$

$lowbit(x)$ 的值是 $x$ 寫成二進位時最小的一個 $1$-bit 的值，例如 $44$ 寫成二進位是 $101100$，那$lowbit(44) = 4$（因為是右邊數來第$3$個bit所以是$2^{3−1}= 4$），而$s[44]$存的就是$a[41...44]$的和。

----


----

int n , s[ 1000010 ];

int sum( int id ) {
  int res = 0;
  for( int i = id ; i > 0 ; i -= i&-i )
    res += s[ i ];
  return res;
}

----

更新時 $a[i]$ 時要找所有的 $j$ 滿足 $j - lowbit(j) < i \le j$。
把 $j$ 寫成一個遞增數列：$j_0 = i, j_{k+1} = j_k + lowbit(j_k)$

證明：
- $j > i$　表示 $i,j$ 寫成二進位後的共同前綴後面一個 bit $j$ 是 $1$, $i$ 是 $0$。
- 更右邊的 bit， $j$ 若有 $1$ 則 $j - lowbit(j) > i$ ，矛盾。
- 右邊都是 $0$ 這樣的 $j$ 滿足 $j - lowbit(j) < i$。
- $j = i$ 的某個 $0$-bit 翻成 $1$， 右邊全設 $0$

----

void upd( int id , int x ) {
  for( int i = id ; i <= n ; i += i&-i )
    s[ i ] += x;
}

----


----

#include <bits/stdc++.h>
using namespace std;
struct BIT {
  int sz;
  vector< int > dat;
  void init( int _sz ) {
    sz = _sz;
    dat.assign( sz + 1 , 0 );
  }
  void upd( int id , int x ) {
    for( int i = id ; i <= sz ; i += i&-i )
      dat[ i ] += x;
  }
  int sum( int id ) {
    int res = 0;
    for( int i = id ; i > 0 ; i -= i&-i )
      res += dat[ i ];
    return res;
  }
  int kth( int k ) { 
    int res = 0;
    for( int i = 1 << __lg( sz ) ; i > 0 ; i >>= 1 )
      if( res + i <= sz && dat[ res + i ] < k )
        k -= dat[ res += i ];
    return res + 1;
  }
};

const int MAXN = 1000010;

int n, a[ MAXN ];
BIT bit;

int main() {
  scanf( "%d" , &n );
  long long ans = 0;
  bit.init( MAXN );
  for( int i = 1 ; i <= n ; i++ ) {
    scanf( "%d" , a+i );
    ans += bit.sum( 1000000 ) - bit.sum( a[ i ] );
    bit.upd( a[ i ] , 1 );
  }
  printf( "%lld\n" , ans );
}

----

## order statistic data structure!

要怎麼用 BIT 維護整數的 multiset 呢？
可以把$a[i]$當作$i$在集合裡出現幾次，那$sum(i)$就是 $\le i$ 的元素有幾個

----

- 由於這邊的$sum(x)$是一個非遞減的函數，我們可以藉由二分搜$sum(x)$來求第$k$小元素
- 直接對$[1,n]$套用一般的二分搜方法，需要呼叫$O(\log n)$次的$sum(x)$，複雜度變成$O(\log^2 n)$
- BIT 儲存的資訊，讓它天生適用二進制分解、枚舉位元的二分搜，達到 $O(\log n)$ 的複雜度。

----

int kth( int k ) { 
  int res = 0, cur = 0;
  for( int i = 1 << __lg( n ) ; i > 0 ; i >>= 1 )
    if( res + i <= n && cur + s[ res + i ] < k )
      cur += s[ res += i ];
  return res + 1;
}

----

## 樹套樹


<del>根號是什麼鬼</del>

----

#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> set_t;
const int N = 2e5 + 87;
set_t f[N];
void add(int i, int j)
{
    for (; i < N; i += i & - i)
        f[i].insert(j);
}
void sub(int i, int j)
{
    for (; i < N; i += i & - i)
        f[i].erase(j);
}
int qry(int i, int l, int r) // [l, r]
{
    int ret = 0;
    for (; i > 0; i -= i & - i)
        ret += f[i].order_of_key(r + 1) - f[i].order_of_key(l);
    return ret;
}
int a[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        add(a[i] = i, i);
    long long ans = 0;
    while (q--) {
        int l, r;
        cin >> l >> r;
        if (l == r) {
            cout << ans << '\n';
            continue;
        }
        int lp = qry(a[l], l+1, r-1);
        int rp = qry(a[r], l+1, r-1);
        int w = r-1 - (l+1) + 1;
        ans += w - 2 * lp + 2 * rp - w;
        ans += (a[r] > a[l]) - (a[l] > a[r]);
        sub(a[l], l);   
        sub(a[r], r);   
        swap(a[l], a[r]);
        add(a[l], l);   
        add(a[r], r);   
        cout << ans << '\n';
    }
}

---

# Treap

----

樹堆，望名生義，便是結合兩種資料結構的綜合體：
- 二元搜尋**樹** (Binary Search Tree, BST)
- **堆**積 (Heap)
- Treap 名稱的由來，即是樹 (Tree)+堆 (Heap)。

----

二元搜尋樹，便是具有如下性質的二元樹：
- 左子樹上所有節點的值均小於等於根節點的值
- 右子樹上所有節點的值均大於等於根節點的值
- 左右子樹也皆爲二元搜尋樹

----

堆積，便是具有如下性質的二元樹：
- 左子樹上所有節點的值均小於等於根節點的值
- 右子樹上所有節點的值均小於等於根節點的值
- 左右子樹也皆爲堆積

----

爲了滿足二元搜尋樹以及最大堆的性質，在樹堆中的節點均帶有兩個值： pri （代表最大堆積中之值）、 key （代表二元搜尋樹中之值），也就是說對於樹堆中的節點均滿足以下條件：
- pri $\geq$ 左子節點的 pri
- pri $\geq$ 右子節點的 pri
- key $\geq$ 左子節點的 key
- key $\leq$ 右子節點的 key

以上前兩個條件稱爲**堆性質**，後兩個條件稱爲**樹性質**。
令 $P(N) = N$ 個點的 treap 的所有點的深度和的期望值，$P(N) = O(N \log N)$

----

struct Treap{
  Treap *l , *r;
  int pri , key , val;
  Treap( int _val , int _key ) :
    val( _val ) , key( _key ), l( NULL ), r( NULL ), pri( rand() ) {}
};

----

Treap* merge( Treap* a , Treap* b ){
  if( !a || !b ) return a ? a : b;
  if( a->pri > b->pri ){
    a->r = merge( a->r , b );
    return a;
  }else{
    b->l = merge( a , b->l );
    return b;
  }
}

----

void split( Treap* t , int k , Treap *&a , Treap *&b ){
  if( !t ) a = b = NULL;
  else if( t->key <= k ){
    a = t;
    split( t->r , k , a->r , b );
  }else{
    b = t;
    split( t->l , k , a , b->l );
  }
}

----

Treap* insert( Treap* t , int k ){
  Treap *tl , *tr;
  split( t , k , tl , tr );
  return merge( tl , merge( new Treap( k ) , tr ) );
}
Treap* remove( Treap* t , int k ){
  Treap *tl , *tr;
  split( t , k - 1 , tl , t );
  split( t , k , t , tr );
  return merge( tl , tr );
}

----


----

#include <cstdio>
#include <algorithm>
#include <stack>
#include <ctime>
#include <cstdlib>
#include <queue>
#define MAXN 800000
#define INF 2147483647
using namespace std;
struct treap
{
    int v;
    int sz;
    int p;
    int mn;
    int rev;
    int add;
    treap *l, *r;
    treap() {}
    treap(int k) : v(k), sz(1), p(rand()), mn(k), rev(0), add(0), l(NULL), r(NULL) {}
};

treap mempool[MAXN];
treap* ptr;
treap* gc; // use treap as linked list to garbage collect

inline void init() {
    ptr = mempool;
    gc = NULL;
}

inline void Del(treap* t) {
    t->l = gc;
    gc = t;
}

inline treap* New(int v) {
    if (gc == NULL) {
        *ptr = treap(v);
        return ptr++;
    } else {
        treap* t = gc;
        gc = gc->l;
        *t = treap(v);
        return t;
    }
}

inline int size(treap* t) {
    return t != NULL ? t->sz : 0;
}

inline int small(treap* t) {
    return t != NULL ? t->mn + t->add : INF;
}

inline void pull(treap* t) {
    if (t == NULL)
        return;
    t->sz = 1 + size(t->l) + size(t->r);
    t->mn = min(t->v, min(small(t->l), small(t->r)));
}

inline void reverse(treap* t) {
    if (t != NULL)
        t->rev ^= 1;
}

inline void addn(treap* t, int v) {
    if (t != NULL)
        t->add += v;
}

inline treap* push(treap* t) {
    if (t != NULL) {
        if (t->rev) {
            swap(t->l, t->r);
            reverse(t->l);
            reverse(t->r);
            t->rev = 0;
        }

        if (t->add) {
            t->v += t->add;
            t->mn += t->add;
            addn(t->l, t->add);
            addn(t->r, t->add);
            t->add = 0;
        }
    }
    return t;
}

void split(treap* t, int k, treap*& a, treap*& b) { // split first k nodes from t to a, others to b
    push(t);

    if (t == NULL) {
        a = b = NULL;
    } else if (size(t->l) + 1 <= k) {
        a = t;
        split(t->r, k - size(t->l) - 1, a->r, b);
        pull(a);
    } else {
        b = t;
        split(t->l, k, a, b->l);
        pull(b);
    }
}

treap* merge(treap* a, treap* b) {
    if (a == NULL)
        return push(b);
    else if (b == NULL)
        return push(a);
    if (a->p > b->p) {
        push(a);
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        push(b);
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

inline void slice(treap* t, int x, int y, treap*& l, treap*& m, treap*& r) {
    split(t, x - 1, l, r);
    split(r, y - x + 1, m, r);
}

treap* build(int n) {
    treap* r = NULL;
    int v;
    stack<treap*> rc;
    treap* nt;
    while (n--) {
        scanf("%d", &v);
        nt = New(v);
        r = NULL;
        while (!rc.empty() && rc.top()->p < nt->p) {
            pull(r = rc.top());
            rc.pop();
        }
        nt->l = r;
        if (!rc.empty())
            rc.top()->r = nt;
        rc.push(nt);
    }
    while (!rc.empty()) {
        pull(r = rc.top());
        rc.pop();
    }
    return r;
}

int main()
{
    srand(42);
    int n, q;
    char cmd[10];
    int x, y, v;
    treap *l, *m, *r;
    treap *ml, *mr;
    treap* root;

    while (scanf("%d", &n) == 1) {
        init();
        root = build(n);
        scanf("%d", &q);
        while (q--) {
            scanf("%s", cmd);
            switch (cmd[0]) {
            case 'A':
                scanf("%d%d%d", &x, &y, &v);
                slice(root, x, y, l, m, r);
                addn(m, v);
                root = merge(merge(l, m), r);
                break;
            case 'I':
                scanf("%d%d", &x, &v);
                split(root, x, l, r);
                root = merge(merge(l, New(v)), r);
                break;
            case 'D':
                scanf("%d", &x);
                slice(root, x, x, l, m, r);
                Del(m);
                root = merge(l, r);
                break;
            case 'M':
                scanf("%d%d", &x, &y);
                slice(root, x, y, l, m, r);
                printf("%d\n", m->mn);
                root = merge(merge(l, m), r);
                break;
            case 'R':
                scanf("%d%d", &x, &y);
                switch (cmd[3]) {
                case 'E':
                    slice(root, x, y, l, m, r);
                    reverse(m);
                    root = merge(merge(l, m), r);
                    break;
                case 'O':
                    scanf("%d", &v);
                    int len = (y-x+1);
                    v = (v % len + len) % len; // v could be negative?
                    if (v) {
                        slice(root, x, y, l, m, r);
                        split(m, len-v, ml, mr);
                        root = merge(merge(l, merge(mr, ml)), r);
                    }
                    break;
                }
                break;
            }
        }
    }
    return 0;
}

---

# 可持久化線段樹
https://oi-wiki.org/ds/persistent-seg/

----

- POJ 2104: 區間第 K 小

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 87;
struct seg
{
    int su, lc, rc;
} S[20 * N];
int ver[N], ptr;
void init() {ptr = 1;}
int newseg()
{
    memset(S + ptr, 0, sizeof(seg));
    return ptr++;
}
int newseg(seg t)
{
    S[ptr] = t;
    return ptr++;
}
void pull(int t) {S[t].su = S[S[t].lc].su + S[S[t].rc].su;}
int n, q, a[N], b[N], C;
int add(int t, int i, int v, int l = 0, int r = C)
{
    t = t ? newseg(S[t]) : newseg();
    if (r - l == 1) {
        S[t].su += v;
        return t;
    }
    int m = (l + r) / 2;
    if (i < m)
        S[t].lc = add(S[t].lc, i, v, l, m);
    else
        S[t].rc = add(S[t].rc, i, v, m, r);
    pull(t);
    return t;
}
int qry(int lt, int rt, int k, int l = 0, int r = C)
{
    if (r - l == 1)
        return l;
    int m = (l + r) / 2;
    int ls = S[S[rt].lc].su - S[S[lt].lc].su;
    if (ls >= k)
        return qry(S[lt].lc, S[rt].lc, k, l, m);
    else
        return qry(S[lt].rc, S[rt].rc, k - ls, m, r);
}
int main()
{
    init();
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    copy(a + 1, a + 1 + n, b);
    sort(b, b + n);
    C = unique(b, b + n) - b;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b, b + C, a[i]) - b;
        ver[i] = add(ver[i - 1], a[i], 1);
    }
    while (q--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", b[qry(ver[l - 1], ver[r], k)]);
    }
}

----

- TIOJ 1827: 區間 rank + 二分搜

#include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i = (a), __e = (b); i < __e; ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,s,e) for (int i = (s) - 1, __e = (e); i >= __e; --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) for (int i = (a), __e = (b); i <= __e; ++i)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,s,e) for (int i = (s), __e = (e); i >= __e; --i)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) REP(__i,0,n)
template<typename T>
void cmax(T & a, T b) {a = max(a, b);}
template<typename T>
void cmin(T & a, T b) {a = min(a, b);}

// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second

// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define CLR(a) a.clear()
#define BK(a) (a.back())
#define FT(a) (a.front())
#define DB(a) a.pop_back()
#define DF(a) a.pop_front()
#define PB push_back
#define EB emplace_back

/* Reading input is now 20% cooler! */
bool RD(void) {return true;}
template<typename T>
bool RD(T & a)
{
	int c;
	while (!isdigit(c = getchar()));
	a = c&15;
    while (isdigit(c = getchar()))
        a = 10 * a + (c & 15);
	return 1;
}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
template<typename T, typename ... TT>
bool RD(T & a, TT & ...  b) {return RD(a) && RD(b...);}

/* Do princesses dream of magic sheep? */
#define RI(a) int a; RD(a)
#define RII(a,b) RI(a); RI(b)
#define RIII(a,b,c) RI(a); RII(b,c)
#define RIIII(a,b,c,d) RI(a); RIII(b,c,d)

/* For it's time for you to fulfill your output. */
void PT(const char * a) {fputs(a, stdout);}
void PT(char * a) {fputs(a, stdout);}
template<typename T>
void PT(const T a)
{
	static const int maxd = 25;
	static char d[maxd];
	int i = maxd - 1;
	T t = a;
    do {
        d[--i] = (t % 10) | 48;
    } while (t /= 10);
	PT(d + i);
}
void PT(const double a) {printf("%.16f", a);}
void PT(const char a) {putchar(a);}

/* The line will last forever! */
void PL(void) {PT('\n');}
template<typename T, typename ... TT>
void PL(const T a, const TT ...  b) {PT(a); if (sizeof...(b)) PT(' '); PL(b...);}

/* Good Luck && Have Fun ! */
const int N = 1e5 + 87;
const int D = __lg(N)+1;
struct node
{
	int s;
	node*l,*r;
} mem[N*D*2];
node * rt[N],* ptr=mem;
node * add(node * t,int l,int r,int i)
{
	t=t?new(ptr++) node(*t):new(ptr++) node();
	++t->s;
	if (r-l==1)
		return t;
	int m=l+((r-l)>>1);
	if (i<m)
		t->l=add(t->l,l,m,i);
	else
		t->r=add(t->r,m,r,i);
	return t;
}
int qry(node*t,int l,int r,int i,int s=0)
{
	if (!t)
		return s;
	if (r==i+1)
		return s+t->s;
	int m=l+((r-l)>>1);
	if (i<m)
		return qry(t->l,l,m,i,s);
	return qry(t->r,m,r,i,(t->l?t->l->s:0) + s);
}
int main()
{
	RII(n,m);
	RP1(i,n) {
		RI(b);
		rt[i] = add(rt[i-1],1,n+1,b);
	}
	DO(m) {
		RII(p,k);
		++p;
		int lo = 1, hi = n;
		while (lo <= hi) {
			int mi=(lo+hi)>>1;
			if (qry(rt[min(p+mi,n)],1,n+1,mi) - qry(rt[max(p-mi-1,0)],1,n+1,mi) >= k)
				hi = mi - 1;
			else
				lo = mi + 1;
		}
		PL(lo);
	}
}

---

# 可持久化 Treap
https://oi-wiki.org/ds/persistent-balanced/
<del>懶的講</del>

---

# 時間線段樹 + 可回溯 DSU
- [tioj 1903](https://tioj.ck.tp.edu.tw/problems/1903)
- 給你一張 $N$ 點 $M$ 邊的無向圖，做 $Q$ 次修改，每次加一條邊或刪一條邊（可以有重邊但不會有自環），每次修改完輸出當前的連通塊數量

----

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first
#define S second
/* I DUCK HORSE */
const int N = 5e5 + 87;
struct hp
{
    size_t operator () (const pii & x) const
    {
        return hash<long long>()(((long long)x.F)<<20 | x.S);
    }
};
unordered_map<pii,pii,hp> la;
vector<pii> t[N*4];
int p[N],sz[N],cc,tp;
pair<int,int> h[N];

void jizz(int o,int l,int r,int i,int j, pii x)
{
    if (i <= l && r <= j) {
        t[o].push_back(x);
        return;
    }
    int m=(l+r)>>1;
    if (i < m)
        jizz(o+o+1,l,m,i,j,x);
    if (j > m)
        jizz(o+o+2,m,r,i,j,x);
}
int find(int x) {return x == p[x] ? x : find(p[x]);}
void gao(int o,int l,int r)
{
//cout<<'['<<l<<','<<r<<']'<<'\n';
    int otp = tp, occ = cc;
    for (const auto & x : t[o]) {
//cout<<x.F<<','<<x.S<<'\n';
        int a = find(x.F), b = find(x.S);
        if (a == b)
            continue;
        if (sz[a] > sz[b])
            swap(a,b);
        h[tp++] = {a,p[a]};
        p[a]=b;
        sz[b]+=sz[a];
        --cc;
    }
    t[o].clear();

    if (r-l == 1) {
        cout << cc << '\n';
    } else {
        int m=l+((r-l)>>1);
        gao(o+o+1,l,m);
        gao(o+o+2,m,r);
    }
    while (tp > otp) {
        --tp;
        int a = h[tp].F;
        sz[p[a]] -= sz[a];
        p[a] = h[tp].S;
    }
    cc = occ;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    for (int i = 0; i < N; ++i)
        p[i] = i;
    fill_n(sz,N,1);

    int T;
    cin>>T;
    while (T--) {
        la.clear();
        int n,m,q;
        cin>>n>>m>>q;
        cc = n;
        for (int i = 0; i < m; ++i) {
            int u,v;
            cin>>u>>v;
            if (u>v)
                swap(u,v);
            pii x(u,v);
            auto it = la.find(x);
            if (it == la.end() || it->F != x)
                la.insert({x,{0,1}});
            else
                it->S.S++;
        }
        for (int i = 0; i < q; ++i) {
            char c;
            int u,v;
            cin >> c >> u >> v;
            if (u>v)
                swap(u,v);
            pii x(u,v);
            auto it = la.find(x);
            if (c == 'N') {
                if (it == la.end() || it->F != x)
                    la.insert({x,{i,1}});
                else
                    it->S.S++;
            } else {
                if (!--it->S.S) {
                    jizz(0,0,q,it->S.F,i,x);
                    la.erase(it);
                }
            }
        }
        for (const auto & x : la)
            jizz(0,0,q,x.S.F,q,x.F);
        gao(0,0,q);
    }
}

---

### Thank you! :horse:

You can find me on

- Codeforces: https://codeforces.com/profile/pr3pony
- Facebook: https://www.facebook.com/prpr.py
- Twitter: https://twitter.com/pr3pony
- GitHub: https://github.com/prprprpony/
- or email me: [e-mail]