# 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 大法
```cpp=
#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 大法
```bash=
$ g++ a.cpp -fsanitize=address -fsanitize=undefined -g
```
題外話： -Wall -Wextra -Wconversion -Wshadow
```cpp=
#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$
```cpp=
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
----
## 單一指標的二分搜
```cpp=
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
```cpp=
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
```cpp
#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
```cpp
#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
```cpp
#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
- 括號匹配
----
## 例題
----
```cpp
#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
----
## 例題
----
```cpp
#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/)
----
```cpp
#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 表格。
----
```cpp
#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
----
----
```cpp
#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;
}
```
----
## 酷炫實做
```cpp
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
----
```cpp=
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})$
----
```cpp=
#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)$
----
```cpp=
#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
```cpp
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
```cpp
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
```cpp
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
```cpp
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$ 一定安全！
----
```cpp
#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 (?
----
```cpp
#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
----
```cpp
#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);
}
```
----
打上標記函數：
```cpp
void apply( Node * node , int L , int R , ll d ){
node->tag += d;
node->val += d * ( R - L + 1 );
}
```
push 函數：
```cpp
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)$
----
```cpp
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)$
----
```cpp
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 );
}
```
----
什麼都會了？！
```cpp
// 查詢：區間乘法
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]$的和。
----
----
```cpp
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$
----
```cpp
void upd( int id , int x ) {
for( int i = id ; i <= n ; i += i&-i )
s[ i ] += x;
}
```
----
----
```cpp
#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)$ 的複雜度。
----
```cpp
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>
----
```cpp
#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)$
----
```cpp
struct Treap{
Treap *l , *r;
int pri , key , val;
Treap( int _val , int _key ) :
val( _val ) , key( _key ), l( NULL ), r( NULL ), pri( rand() ) {}
};
```
----
```cpp
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;
}
}
```
----
```cpp
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 );
}
}
```
----
```cpp
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 );
}
```
----
----
```cpp
#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 小
```cpp=
#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 + 二分搜
```cpp=
#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$ 次修改，每次加一條邊或刪一條邊（可以有重邊但不會有自環），每次修改完輸出當前的連通塊數量
----
```cpp=
#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: b06902052@ntu.edu.tw