owned this note
owned this note
Published
Linked with GitHub
# Codebook
## DP
### LCS
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
string s1, s2;
int dp[505][505];
int main(){
IOS
cin >> s1 >> s2;
memset(dp, 0, sizeof(dp));
int l1 = s1.size(), l2 = s2.size();
for(int i = 1;i <= l1;i++){
for(int j = 1;j <= l2;j++){
if(s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[l1][l2] << '\n';
return 0;
}
```
### LIS
#### O(n^2)
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
int main(){
IOS
int arr[100];
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
int dp[100];
for(int i = 0;i < n;i++) dp[i] = 1;
for(int i = 0;i < n;i++){
for(int j = 0;j < i;j++){
if(arr[i] > arr[j])
dp[i] = max(dp[j] + 1, dp[i]);
}
}
int ans = 1;
for(int i = 0;i < n;i++) ans = max(ans, dp[i]);
cout << ans << '\n';
return 0;
}
```
#### O(nlogn)
```cpp=
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> v;
int n = nums.size();
for(int i = 0;i < n;i++){
int p = lower_bound(v.begin(), v.end(), nums[i]) - v.begin();
if(p == v.size()) v.push_back(nums[i]);
else v[p] = nums[i];
}
return v.size();
}
};
```
#### LIS 各元素的長度 (一樣 O(nlgN) 所以也可以平替上面的)
```cpp
for(int i=0;i<num.size();i++){
if(lis.empty()||lis.back()<num[i]){
lis.push_back(num[i]);
dp[i]=lis.size();
}
else{
auto iter=lower_bound(all(lis),num[i]);
dp[i]=iter-lis.begin()+1;
*iter=num[i];
}
}
int length=lis.size();
for(int i=num.size()-1;i>=0;i--){
if(dp[i]==length){
ans.push_back(num[i]);
length--;
}
}
```
## 質數篩
```py=
is_prime = n * [1]
is_prime[0] = is_prime[1] = 0
for i in range(2, n):
if is_prime[i]:
for j in range(2, n):
if i * j >= n:
break
is_prime[i * j] = 0
```
```cpp
bitset<MAXN> prime_bool;
vector<ll> prime;
void find_prime(){
prime_bool.set();
for(int i=2;i<MAXN;i++){
if(prime_bool[i]){
prime.push_back(i);
}
for(auto j:prime){
if(j*i>=MAXN)
break;
prime_bool[j*i]=0;
if(i%j==0)
break;
}
}
}
```
#### 單一質數
```cpp
bool prime(int n)
{
if(n<2) return false;
if(n<=3) return true;
if(!(n%2) || !(n%3)) return false;
for(int i=5;i*i<=n;i+=6)
if(!(n%i) || !(n%(i+2))) return false;
return true;
}
```
## egcd
```python=
def egcd(a: int, b: int) -> Tuple[int, int, int]:
"""return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
"""x % y"""
if a == 0:
return (b, 0, 1)
else:
b_div_a, b_mod_a = divmod(b, a)
g, x, y = egcd(b_mod_a, a)
return (g, y - b_div_a * x, x)
```
```cpp
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b,y,x);
y-=a/b*x;
return gcd;
}
```
## Graph
### Dijkstra
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 2147483647
using namespace std;
int n, m;
vector<pair<int, int>> adj[100005];
bool visited[100005] = {false};
priority_queue<pair<int, int>> pq;
int dis[100005], parent[100005];
void solve(){ // Dijkstra
dis[0] = 0;
for(int i = 1;i < n;i++) dis[i] = INF;
pq.push(make_pair(0, 0));
while(!pq.empty()){
auto node = pq.top();
pq.pop();
int v = node.second; // parent
if(visited[v]) continue;
visited[v] = true;
for(auto i : adj[v]){
int vertex = i.first, weight = i.second;
if(visited[vertex]) continue;
if(dis[v] + weight < dis[vertex]){
dis[vertex] = dis[v] + weight;
parent[vertex] = v;
pq.push(make_pair(-dis[vertex], vertex));
}
}
}
int maxd = -1, cnt = 0;
for(int i = 0;i < n;i++){
if(dis[i] < INF){
if(dis[i] > maxd) maxd = dis[i];
}
else cnt++;
}
cout << maxd << '\n' << cnt << '\n';
}
int main(){
IOS
cin >> n >> m;
for(int i = 0;i < m;i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
solve();
return 0;
}
```
### Second SP
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 1005;
vector<pii> adj[MAXN]; // adj[u] stores pairs {v, weight}
int dist[MAXN], sec_dist[MAXN]; // shortest and second shortest distances
void dijkstra(int s, int n){
// Min-heap to store {distance, node}
priority_queue<pii, vector<pii>, greater<pii>> pq;
fill(dist, dist + n + 1, INF);
fill(sec_dist, sec_dist + n + 1, INF);
dist[s] = 0;
pq.push({0, s});
while(!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// If we found a path longer than the second shortest, skip it
if (sec_dist[u] < d) continue;
for (auto &edge : adj[u]){
int v = edge.first;
int w = edge.second;
int new_dist = d + w;
// If this gives a new shortest path to v
if(new_dist < dist[v]){
sec_dist[v] = dist[v];
dist[v] = new_dist;
pq.push({dist[v], v});
pq.push({sec_dist[v], v});
}
// If this gives a new second shortest path to v
else if(new_dist > dist[v] && new_dist < sec_dist[v]){
sec_dist[v] = new_dist;
pq.push({sec_dist[v], v});
}
}
}
}
int main() {
IOS
int t;
cin >> t;
while(t--){
int n, m, s, d;
cin >> n >> m >> s >> d;
// Reset adjacency list
for(int i = 1; i <= n; i++) adj[i].clear();
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w}); // If the graph is undirected
}
dijkstra(s, n);
if(sec_dist[d] == INF) cout << -1 << '\n'; // No second shortest path
else cout << sec_dist[d] << '\n';
}
return 0;
}
```
### Bellman-Ford
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct Edge{
int x, y, t;
};
int dis[1005];
int main(){
IOS
int c;
cin >> c;
while(c--){
vector<Edge> edge;
int n, m;
cin >> n >> m;
for(int i = 0;i <= n;i++) dis[i] = INF;
dis[0] = 0;
for(int i = 0;i < m;i++){
int x, y, t;
cin >> x >> y >> t;
edge.push_back({x, y, t});
}
for(int i = 0;i < n - 1;i++){
for(int j = 0;j < m;j++){
if(dis[edge[j].x] + edge[j].t < dis[edge[j].y]){
dis[edge[j].y] = dis[edge[j].x] + edge[j].t;
}
}
}
bool judge = true;
for(auto e : edge){
if(dis[e.x] + e.t < dis[e.y]){
judge = false;
break;
}
}
cout << (judge ? "not possible" : "possible") << '\n';
}
return 0;
}
```
### SPFA
```cpp=
#define mem(x) memset(x, 0, sizeof(x))
struct road{
int r, val;
};
int main(){
int n, e, l, r, v;
cin >> n >> e;
vector<int> dp(n + 1, 1e9);
vector<road> rd[n + 1];
for(int i = 0; i < e; i++){
cin >> l >> r >> v;
rd[l].push_back({r, v});
rd[r].push_back({l, v});
}
cin >> l >> r;
dp[l] = 0;
queue<int> que;
que.push(l);
bool check[n + 1]; mem(check);
int cnt[n + 1]; mem(cnt);
while(!que.empty()){
int tmp = que.front(); que.pop();
check[tmp] = 0, cnt[tmp]++;
if(cnt[tmp] >= n) {cout << "neg cycle\n"; break;}
for(auto & i : rd[tmp]){
if(dp[i.r] > dp[tmp] + i.val){
dp[i.r] = dp[tmp] + i.val;
if(!check[i.r]) check[i.r] = 1, que.push(i.r);
}
}
}
for(auto & i : dp) cout << i << ' ';
return 0;
}
```
### Floyd-Warshall
```cpp=
int n, rd, l, r, v;
cin >> n >> rd;
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
for(int i = 0; i < rd; i++){
cin >> l >> r >> v;
dp[l][r] = dp[r][l] = v;
//每條路皆雙向
}
//以下即 Floyd-Warshall
for(int k = 1; i <= n; i++){
for(int i = 1; j <= n; j++){
for(int j = 1; k <= n; k++){
dp[i][j] = min(dp[i][k] + dp[k][j] , dp[i][j]);
//窮舉所有鬆弛可能
}
}
}
cin >> l >> r;
cout << dp[l][r];
```
### Prim's Algorithm
```cpp=
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n, m, dis[10005], parent[10005];
bool visited[10005] = {false};
vector<pair<int, int> > adj[100005];
int main(){
IOS
// freopen("input.in", "r", stdin);
cin >> n >> m;
memset(dis, 0x3f3f3f3f, sizeof(dis));
memset(parent, -1, sizeof(parent));
for(int i = 0;i < m;i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int start = 0;
dis[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push({dis[start], start});
while(!pq.empty()){
pair<int, int> cur = pq.top();
pq.pop();
if(visited[cur.second]) continue;
visited[cur.second] = true;
for(auto i : adj[cur.second]){
if(visited[i.first]) continue;
if(dis[i.first] > i.second){
dis[i.first] = i.second;
parent[i.first] = cur.second;
pq.push({dis[i.first], i.first});
}
}
}
int cost = 0, err = 0;
for(int i = 0;i < n;i++){
if(dis[i] < 0x3f3f3f3f) cost += dis[i];
else err++;
}
cout << (err ? -1 : cost) << "\n";
// for(int i = 0;i < n;i++) cout << dis[i] << ' ';
return 0;
}
```
### Kruskal's Algorithm
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int parent[10005];
struct Edge{
int u, v, w;
bool operator < (Edge &b){
return w < b.w;
}
};
int query(int a){
if(parent[a] == -1) return a;
return parent[a] = query(parent[a]);
}
bool merge(int a, int b){
int r1 = query(a);
int r2 = query(b);
if(r1 == r2) return false;
if(parent[r1] < parent[r2]) parent[r2] = r1;
else parent[r1] = r2;
return true;
}
int main(){
IOS
int n, m;
memset(parent, -1, sizeof(parent));
cin >> n >> m;
vector<Edge> adj;
for(int i = 0;i < m;i++){
int u, v, w;
cin >> u >> v >> w;
adj.push_back({u, v, w});
}
sort(adj.begin(), adj.end());
// for(int i = 0;i < m;i++) cout << adj[i].w << ' ';
int cost = 0, n_edge = 0;
for(Edge e : adj){
if(merge(e.u, e.v)){
cost += e.w;
n_edge++;
}
}
if(n_edge == n - 1) cout << cost << '\n';
else cout << -1 << '\n';
return 0;
}
```
### Second MST
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int anc[105], sz[105];
struct Edge{
int a, b, c;
};
int Find(int a){
return (anc[a] == a ? a : anc[a] = Find(anc[a]));
}
bool merge(int a, int b){
a = Find(a);
b = Find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
return true;
}
int main(){
IOS
int t;
cin >> t;
while(t--){
int n, m;
vector<Edge> edge;
cin >> n >> m;
vector<pair<int, int> > vec[105];
for(int i = 0;i < m;i++){
int a, b, c;
cin >> a >> b >> c;
edge.push_back({a, b, c});
}
for(int i = 1;i <= n;i++){
sz[i] = 0;
anc[i] = i;
}
sort(edge.begin(), edge.end(), [&](Edge &u, Edge &v){return u.c < v.c;});
int cost1 = 0, cnt = 0;
vector<int> mst;
for(int i = 0;i < edge.size();i++){
if(merge(edge[i].a, edge[i].b)){
cost1 += edge[i].c;
mst.push_back(i);
if(++cnt == n - 1) break;
}
}
int cost2 = INF;
for(int i = 0;i < mst.size();i++){
cnt = 0;
int res = 0;
for(int i = 1;i <= n;i++) anc[i] = i;
for(int j = 0;j < edge.size();j++){
if(mst[i] == j) continue;
if(merge(edge[j].a, edge[j].b)){
res += edge[j].c;
if(++cnt == n - 1){
cost2 = min(cost2, res);
break;
}
}
}
}
cout << cost1 << ' ' << cost2 << '\n';
}
return 0;
}
```
### 樹直徑
```cpp=
#include <cstdio>
#include <vector>
using namespace std;
constexpr int N = 100000 + 10;
int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa) {
for (int v : E[u]) {
if (v == fa) continue;
d[v] = d[u] + 1;
if (d[v] > d[c]) c = v;
dfs(v, u);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
E[u].push_back(v), E[v].push_back(u);
}
dfs(1, 0);
d[c] = 0, dfs(c, 0);
printf("%d\n", d[c]);
return 0;
}
```
### LCA
https://hackmd.io/@LittlePants/SkuHoX2DO
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n, q;
vector<int> vec[N];
int p[20][N], in[N], out[N];
bool valid(int a, int b){
return (in[a] <= in[b] && out[b] <= out[a]);
}
void dfs(int cur, int par){
static int t = 0;
p[0][cur] = par;
in[cur] = t++;
for(auto e : vec[cur]){
dfs(e, cur);
}
out[cur] = t++;
}
int lca(int a, int b){
if(valid(a, b)) return a;
for(int i = 19;i >= 0;i--){
if(!valid(p[i][a], b)) a = p[i][a];
}
return p[0][a];
}
int main(){
IOS
cin >> n >> q;
for(int i = 2;i <= n;i++){
int e;
cin >> e;
vec[e].push_back(i);
}
dfs(1, 1);
for(int i = 1;i < 20;i++){
for(int j = 1;j <= n;j++){
p[i][j] = p[i - 1][p[i - 1][j]];
}
}
while(q--){
int u, v;
cin >> u >> v;
cout << lca(u, v) << '\n';
}
return 0;
}
```
### Topological sort
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
vector<int> vec[200005];
int ind[100005];
int main(){
IOS
int n, m;
cin >> n >> m;
memset(ind, 0, sizeof(ind));
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b;
ind[b]++;
vec[a].push_back(b);
}
queue<int> q;
for(int i = 1;i <= n;i++){
if(ind[i] == 0) q.push(i);
}
vector<int> top;
while(!q.empty()){
int cur = q.front();
q.pop();
top.push_back(cur);
for(auto e : vec[cur]){
ind[e]--;
if(ind[e] == 0){
q.push(e);
}
}
}
if(top.size() == n){
for(auto i : top) cout << i << ' ';
cout << '\n';
}
else cout << "IMPOSSIBLE" << '\n';
return 0;
}
```
### SCC
### Maximum flow
## RMQ
### Segment Tree v1
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define L(x) (x << 1)
#define R(x) ((x << 1) | 1)
using namespace std;
typedef long long ll;
ll seg[500005 << 2], lazy[500005 << 2];
int n, q;
void init(){
memset(seg, 0, sizeof(seg));
memset(lazy, 0, sizeof(lazy));
}
void build(int x, int l, int r){
if(l == r){
cin >> seg[x];
return;
}
int mid = (l + r) >> 1;
build(L(x), l, mid);
build(R(x), mid + 1, r);
seg[x] = seg[L(x)] + seg[R(x)];
}
void push(int pos, int size){
lazy[L(pos)] += lazy[pos];
lazy[R(pos)] += lazy[pos];
seg[pos] = seg[pos] + lazy[pos] * size;
lazy[pos] = 0;
}
void modify(int x, int l, int r, int ql, int qr, int val){
if(lazy[x]) push(x, (r - l) + 1);
// seg[x] = seg[L(x)] + (mid - l) * lazy[L(x)] + seg[R(x)] + (r - mid) * lazy[R(x)];
seg[x] += val * (qr - ql + 1);
if(ql <= l && qr >= r){
lazy[x] += val;
return;
}
int mid = (l + r) >> 1;
if(qr <= mid) modify(L(x), l, mid, ql, qr, val);
else if(ql > mid) modify(R(x), mid + 1, r, ql, qr, val);
else{
modify(L(x), l, mid, ql, mid, val);
modify(R(x), mid + 1, r, mid + 1, qr, val);
}
}
ll query(int x, int l, int r, int ql, int qr){
if(ql <= l && qr >= r) return seg[x] + lazy[x] * (r - l);
if(lazy[x]) push(x, (r - l) + 1);
int mid = (l + r) >> 1;
if(qr <= mid) return query(L(x), l, mid, ql, qr);
else if(ql > mid) return query(R(x), mid + 1, r, ql, qr);
else return query(L(x), l, mid, ql, mid) + query(R(x), mid + 1, r, mid + 1, qr);
}
int main(){
IOS
init();
cin >> n;
build(1, 1, n);
cin >> q;
while(q--){
int v, x, y, k;
cin >> v;
if(v == 1){
cin >> x >> y >> k;
modify(1, 1, n, x, y, k);
}
else{
cin >> x >> y;
ll ans = query(1, 1, n, x, y);
cout << ans << '\n';
}
}
return 0;
}
```
### Segment Tree v2
```cpp=
struct Node{
int left; // 左邊邊界
int right; //右邊邊界
int value; //儲存的值
int z; //區間修改用，如果沒有區間修改就不需要
}node[4 * N ];
#define Lson(x) (x << 1) //左子樹
#define Rson(x) ((x << 1) +1) //右子樹
void question(){
for(int i = 1; i <= 10; i++) num[i] = i * 123 % 5;
// num 為題目產生的一段數列
// hash 函數，讓 num 的 i 被隨機打亂
}
void build(int left , int right , int x = 1 ){
// left 為題目最大左邊界，right 為題目最大右邊界，圖片最上面的 root 為第一個節點
node[x].left = left ; //給 x 節點左右邊界
node[x].right = right ;
if(left == right){ //如果左右邊界節點相同，表示這裡是葉節點
node[x].value = num[left] ; //把 num 值給 node[x]
//這裡的 num 值表示，我們要在 value 要放的值
return ; //向前返回
}
int mid = (left + right ) / 2 ; //切半，產生二元樹
//debug
//cout << mid << '\n' ;
//cout << x << ' ' << node[x].left << ' ' << node[x].right << ' ' << '\n' ;
build(left , mid , Lson(x)) ; //將區間改為 [left, mid] 然後帶給左子樹
build(mid + 1 , right , Rson(x)) ; //將區間改為 [mid+1, right] 然後帶給右子樹
node[x].value = min(node[Lson(x)].value , node[Rson(x)].value ) ;
//查詢左右子樹哪個數值最小，並讓左右子樹最小值表示此區間最小數值。
}
void modify(int position , int value , int x = 1 ){ //修改數字
if(node[x].left == position && node[x].right == position ){ //找到葉節點
node[x].value = value ; //修改
return ; //傳回
}
int mid = (node[x].left + node[x].right ) / 2 ; //切半，向下修改
if(position <= mid ) //如果要修改的點在左邊，就往左下角追蹤
modify(position , value , Lson(x) );
if(mid < position ) //如果要修改的點在右邊，就往右下角追蹤
modify(position , value , Rson(x)) ;
node[x].value = min(node[Lson(x)].value , node[Rson(x)].value );
//比較左右子樹哪個值比較小，較小值為此節點的 value
}
void push_down(int x, int add){ //將懶人標記往下推，讓下一層子樹進行區間修改
int lson = Lson(x), rson = Rson(x);
node[lson].z += add; //給予懶人標記，表示子樹如果要給子樹的子樹區間修改時，
node[rson].z += add; //數值要是多少，左右子樹都需要做
node[lson].v += add; //更新左右子樹的值
node[rson].v += add;
}
void update(int a, int b, int cmd, int x = 1){
//a, b 為區間修改的 left and right, cmd 為要增加的數值
if(a <= node[x].l && b >= node[x].r){
//如果節點的 left and right，跟 a, b 區間是相等，或更小就，只要在這邊修改 cmd，
//就可以讓 node[x].v 的值直接變為區間修改後的數值，
//之後如果要讓這查詢向子樹進行區間修改，就用 push_down，
//我們這邊的懶人標記就會告訴左右子樹要修改的值為多少
node[x].v += cmd; //區間修改後的 v
node[x].z = cmd; //區間修改是要增加多少數值
return;
}
push_down(x);//先將之前的區間查詢修改值，往下給子樹以避免上次的查詢值被忽略
//假如當前的 node[x].z 原本是 3，如果沒有 push_down(x)，那下面的子樹都沒有被 +3，
//導致答案不正確。
int mid = (node[x].l+node[x].r) / 2; //切半，向下修改
if(a <= mid) update(a, b, cmd, Lson(x)); //如果要修改的點在左邊，就往左下角追蹤
if(b > mid) update(a, b, cmd, Rson(x)); //如果要修改的點在右邊，就往右下角追蹤
node[x].v = node[Lson(x)].v + node[Rson(x)].v;
//比較左右子樹哪個值比較小，較小值為此節點的 value
}
#define INF 0x3f3f3f
int query(int left , int right , int x = 1 ){
if(node[x].left >= left && node[x].right <= right)
return node[x].Min_Value ;
//如果我們要查詢的區間比當前節點的區間大，那我們不需再向下查詢直接輸出此答案就好。
// 例如我們要查詢 [2, 8]，我們只需要查詢 [3, 4]，不須查詢 [3, 3]、[4, 4]，
// [3, 4] 已經做到最小值查詢
push_down(x);//有區間修改時才需要寫
int mid = (node[x].left + node[x].right ) / 2 ; //切半，向下修改
int ans = INF ; //一開始先假設答案為最大值
if( left <= mid ) //如果切半後，我們要查詢的區間有在左子樹就向下查詢
ans = min(ans , query(left , right , Lson(x))) ; //更新答案，比較誰比較小
if(mid < right ) //如果切半後，我們要查詢的區間有在右子樹就向下查詢
ans = min(ans , query(left , right , Rson(x))) ; //更新答案，比較誰比較小
return ans ; //回傳答案
}
```
### BIT
```cpp=
// BIT
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/detail/standard_policies.hpp>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
#define lowbit(x) x&(-x)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 2e5 + 5;
ll bit[N], n, q;
ll query(int idx){
ll sum = 0;
for(int i = idx;i > 0;i -= lowbit(i))
sum += bit[i];
return sum;
}
void update(ll val, int idx){
for(int i = idx;i <= n;i += lowbit(i))
bit[i] += val;
}
int main(){
IOS
cin >> n >> q;
for(int i = 1;i <= n;i++){ // 1-based
ll in;
cin >> in;
update(in, i);
}
while(q--){
ll o, a, b;
cin >> o >> a >> b;
if(o == 1){
ll u = query(a) - query(a - 1);
update(b - u, a);
}
else{
cout << query(b) - query(a - 1) << '\n';
}
}
return 0;
}
```
### Sparse Table
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, m, arr[N], dp[35][N];
void sparse_table(int n){
for(int i = 1;i <= 31;i++){
for(int j = 0;(j + (1LL << (i - 1))) < n;j++){
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + (1LL << (i - 1))]);
}
}
}
int query(int l, int r){
int idx = __lg(r - l + 1);
return max(dp[idx][l], dp[idx][r - (1LL << idx) + 1]);
}
int main(){
IOS
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i];
cin >> m;
for(int i = 0;i < n;i++) dp[0][i] = arr[i];
sparse_table(n);
while(m--){
int l, r;
cin >> l >> r;
if(l > r) swap(l, r);
l--, r--;
cout << query(l, r) << '\n';
}
return 0;
}
```
## Others
### 快速冪
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
ll mod = 1000000007;
ll fast_pow(int base, int exp){
ll res = 1;
while(exp > 0){
if(exp & 1) res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
int main(){
IOS
int base = 3, exp = 15;
cout << fast_pow(base, exp) << '\n';
return 0;
}
```
### 矩陣快速冪
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll mod = 1000000007;
struct Matrix{
ll mat[2][2] = {{0}};
Matrix operator * (Matrix &inp){
Matrix tmp;
for(int i = 0;i < 2;i++){
for(int j = 0;j < 2;j++){
for(int k = 0;k < 2;k++){
tmp.mat[i][j] = ((tmp.mat[i][j] + (mat[i][k] % mod) * (inp.mat[k][j] % mod)) % mod) % mod;
}
}
}
return tmp;
}
};
Matrix base;
Matrix fast_pow(int exp){
if(exp == 1) return base;
if(exp % 2 == 0){
Matrix res = fast_pow(exp >> 1);
return res * res;
}
Matrix res = fast_pow(exp >> 1);
return base * res * res;
}
int main(){
IOS
base.mat[0][0] = 1;
base.mat[0][1] = 4;
base.mat[1][0] = 2;
base.mat[1][1] = 3;
Matrix output = fast_pow(10);
for(int i = 0;i < 2;i++){
for(int j = 0;j < 2;j++){
cout << output.mat[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
```
### 快速計算費氏數列
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll mod = 1000000007;
struct Matrix{
ll mat[2][2] = {{0}};
Matrix operator * (Matrix &inp){
Matrix tmp;
for(int i = 0;i < 2;i++){
for(int j = 0;j < 2;j++){
for(int k = 0;k < 2;k++){
tmp.mat[i][j] = ((tmp.mat[i][j] + (mat[i][k] % mod) * (inp.mat[k][j] % mod)) % mod) % mod;
}
}
}
return tmp;
}
};
Matrix base;
Matrix fast_pow(int n){
if(n == 1) return base;
if(n % 2 == 0){
Matrix res = fast_pow(n >> 1);
return res * res;
}
Matrix res = fast_pow(n >> 1);
return base * res * res;
}
int main(){
IOS
base.mat[0][0] = 1;
base.mat[0][1] = 1;
base.mat[1][0] = 1;
base.mat[1][1] = 0;
Matrix output = fast_pow(20);
cout << output.mat[0][0] << '\n';
return 0;
}
```
### Disjoint Set
```cpp=
int n=1000; //假設共有n個點
int dsu[1000]; //建一個紀錄集合編號的陣列，若dsu[n]==n，代表為根
///初始化集合
void initt(){
for(int i=0;i<=n;i++){
//初始每個集合只有自己
dsu[i]=i;
}
}
///查詢
//傳入要找尋的目標
int findd(int x){
if(x!=dsu[x]){
//往上尋找祖先，再遞迴更新路上遇到的節點
dsu[x]=Find(dsu[x]);
}
return dsu[x];
}
///合併
void unionn(int x,int y){
int a=findd(x);
int b=findd(y);
//若集合編號不相同，則進行合併，
if(a!=b){
dsu[a]=b;
}
}
```
## 常用小扣
```cpp
while(getline(ss,str,'m'))//以m分割
cout << str << endl;
int a,b; char c;
while(ss>>a>>c>>b)//處理像是-2/9+9/7
cout<<a<<" "<<c<<" "<<b<<endl;
//輸出 -2 / 9 endl 9 / 7
```
```cpp
// 01 backpack
for(int i=1;i<=n;i++){
for(int j=x;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
```
```cpp
//無限背包
for(int i=1;i<=W;i++){ // 從小到大遍歷重量
for(int j=1;j<=n;j++){ // 遍歷每個物品
if(i>=w[j]) dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
}
}
```
```cpp
//拓鋪
int N, M, u, v, deg[MAXN]; // deg[i] 紀錄點 i 被連入邊數
vector<int> edge[MAXN];
/*------ 1. 計算 indegree ------*/
cin >> N >> M;
while(M--)
{
cin >> u >> v;
edge[u].push_back(v);
++deg[v];
}
/*------ 2. 將 indegree 為 0 的點放入 queue 中 ------*/
queue<int> q; // 紀錄待拔點
for(int i = 0; i < N; ++i)
if(deg[i] == 0)
q.push(i);
/*------ 3. 重複拔點，直到 queue 清空 ------*/
while(!q.empty())
{
int cur = q.front(); q.pop();
cout << cur << "\n";
for(int i: edge[cur])
{
--deg[i]; // 3-1. 相連點 indgree 減一
if(deg[i] == 0) q.push(i); // 3-2. 若該點 indgree 減至 0，則放入 queue 中
}
}
```
## 小技巧
### 求根號 和解決 pow 精度問題
```cpp
// when the number is too large, use powl instead of pow
// will provide you more accuracy.
powl(a,b)
(int)round(p,(1.0/n)) //nth root of p
```
### 查找和 二分搜
```cpp
// will return address of iterator, call result as *iterator;
iterator find(iterator first, iterator last, const T&value);
bool binary_search(iterator first, iterator last, const T &value);
```
```cpp
// a^b mod p
long powmod(long base, long exp , long modulus){
base %= modulus;
long result = 1;
while(exp > 0){
if(exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >> 1;
}
return result;
}
```
```cpp
// n! mod p
int factmod(int n,int p){
long long res = 1;
while(n > 1){
res = (res % powmod(p-1 , n/p , p)) %p;
for(int i=2;i<=n%p;i++)
res = (res * i) % p;
n /= p;
}
}
```
### 從 1 ~ n 選 M 個數字
```cpp
// n >=m choose m number from 1 ~ n
void combination(int n, int m){
if (n<m) return;
int a[50] = {0};
int k = 0;
for(int i=1;i<=m;i++) a[i] = i;
while(1){
for(int i=1;i<=m;i++)
cout << a[i] << " ";
cout << endl;
k = m;
while((k>0) && (n-a[k] == m-k)) k --;
if(k == 0) break;
a[k] ++;
for(int i=k+1;i<=m;i++){
a[i] = a[i-1] + 1;
}
}
}
```
### m-ary to 10-ary 進制轉換
```cpp
string num = "0123456789ABCDE";
int mToTen(string n, int m){
int multi = 1;
int result = 0;
for(int i = n.size() - 1;i >= 0;i--){
result += num.find(n[i]) * multi;
multi *= m;
}
return result;
}
```
### 二項式係數 Binomial Coefficient (也可以用在 C 幾取幾)
```cpp=
#define MAXN 100 // largest n or m
long binomial_coefficient(n, m) // compute n choose m
int n, m;
{
int i, j;
long bc[MAXN][MAXN];
for(i = 0;i <= n;i++) bc[i][0] = 1;
for(j = 0;j <= n;j++) bc[j][j] = 1;
for(i = 1;i <= n;i++)
for(j = 1;j < i;j++)
bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j];
reutrn bc[n][m];
}
```
### LICS
```cpp=
int a[100] = {0};
int b[100] = {0};
int f[100] = {0};
int n = 0, m = 0;
int main(void){
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
cin >> m;
for(int i = 1;i <= m;i++) cin >> b[i];
for(int i = 1;i <= n;i++){
int k = 0;
for(int j = 1;j <= m;j++){
if(a[i] > b[j] && f[j] > k) k = f[j];
else if(a[i] == b[j] && k + 1 > f[j]) f[j] = k + 1;
}
}
}
```
## Math
### ModInverse
```cpp=
// 求 a 在模 m 下的模反元素，m 必須是質數
ll modInverse(ll a, ll m) {
ll res = 1, exp = m - 2;
while (exp > 0) {
if (exp % 2 == 1) res = (res * a) % m;
a = (a * a) % m;
exp /= 2;
}
return res;
}
```
### CRT
```cpp=
ll extendedGCD(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll x1, y1;
ll g = extendedGCD(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
ll chineseRemainder(vector<ll> &n, vector<ll> &a) {
ll prod = 1;
for (ll num : n) prod *= num; // Calculate the product of all moduli
ll result = 0;
for (int i = 0; i < n.size(); i++) {
ll p = prod / n[i]; // Product divided by current modulus
ll x, y;
extendedGCD(p, n[i], x, y); // Solve p * x ≡ 1 (mod n[i])
result = (result + a[i] * x * p) % prod; // Add current term to result
}
return (result + prod) % prod; // Return the result modulo the product
}
```
### LinearCongruence
```cpp=
ll solveLinearCongruence(ll a, ll b, ll m) {
ll x, y;
ll g = extendedGCD(a, m, x, y); // Solve a * x + m * y = gcd(a, m)
if (b % g != 0) return -1; // No solution if gcd(a, m) does not divide b
x = (x * (b / g)) % m;
if (x < 0) x += m; // Ensure the result is positive
return x;
}
```
## 臨時加的
### Disjoint set v1
```cpp=
int n=1000; //假設共有n個點
int dsu[1000]; //建一個紀錄集合編號的陣列，若dsu[n]==n，代表為根
///初始化集合
void initt(){
for(int i=0;i<=n;i++){
//初始每個集合只有自己
dsu[i]=i;
}
}
///查詢
//傳入要找尋的目標
int findd(int x){
if(x!=dsu[x]){
//往上尋找祖先，再遞迴更新路上遇到的節點
dsu[x]=Find(dsu[x]);
}
return dsu[x];
}
///合併
void unionn(int x,int y){
int a=findd(x);
int b=findd(y);
//若集合編號不相同，則進行合併，
if(a!=b){
dsu[a]=b;
}
}
```
### Disjoint set v2
```cpp=
int Find(int a){
return (anc[a] == a ? a : anc[a] = Find(anc[a]));
}
bool merge(int a, int b){
a = Find(a);
b = Find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
anc[b] = a;
sz[a] += sz[b];
return true;
}
```
### 樹 DP
```cpp=
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int dp[205][2];
bool uni[205][2];
void dfs(vector<int> vec[205], int u){
dp[u][0] = 0;
dp[u][1] = 1;
uni[u][0] = 1;
uni[u][1] = 1;
for(auto v : vec[u]){
dfs(vec, v);
dp[u][1] += dp[v][0];
dp[u][0] += max(dp[v][0], dp[v][1]);
if(dp[v][0] > dp[v][1]){
if(!uni[v][0]) uni[u][0] = 0;
}
else if(dp[v][1] > dp[v][0]){
if(!uni[v][1]) uni[u][0] = 0;
}
if(dp[v][0] == dp[v][1]) uni[u][0] = 0;
if(!uni[v][0]) uni[u][1] = 0;
}
}
int main(){
IOS
int n;
while(cin >> n && n){
unordered_map<string, int> un;
vector<int> vec[205];
string boss;
cin >> boss;
int idx = 0;
un[boss] = idx++;
memset(uni, 1, sizeof(uni));
memset(dp, 0, sizeof(dp));
for(int i = 0;i < n - 1;i++){
string str1, str2;
cin >> str1 >> str2;
if(!un[str1]) un[str1] = idx++;
if(!un[str2]) un[str2] = idx++;
vec[un[str2]].push_back(un[str1]);
}
dfs(vec, un[boss]);
cout << max(dp[un[boss]][0], dp[un[boss]][1]) << ' ';
if(dp[un[boss]][0] == dp[un[boss]][1]){
cout << "No" << '\n';
}
else if(dp[un[boss]][0] > dp[un[boss]][1]){
cout << (uni[un[boss]][0] ? "Yes" : "No") << '\n';
}
else if(dp[un[boss]][1] > dp[un[boss]][0]){
cout << (uni[un[boss]][1] ? "Yes" : "No") << '\n';
}
}
return 0;
}
```
## Prime
### LPF
### Sieve of Eratosthenes
https://hackmd.io/@LeeShoWhaodian/R#/3
```cpp
//n為會跑到的最大值
bool isprime[1000005]; //紀錄每個數字是否是質數
vector<int> prime; // 儲存範圍內所有的質數
isprime[1]=1; // 1 代表此數字不是質數，否則為 0
//先將所有大於1數字設為質數(0)
for(int i=2;i<=n;i++){
if(!isprime[i]){ //如果為質數
prime.push_back(i);
for(long long j=2;i*j<=n;j++){ //記得容易會爆int的話要設long long
//所有質數的倍數設成非質數
isprime[i*j] = 1;
}
}
}
```
## 如果全體腦袋當機用
## 雜項
### SPF and maximum factor
```cpp
#include <iostream>
#include <cstring>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int spf[1000005], ans[1000005];
void sieve(){
memset(spf, 0, sizeof(spf));
for (int i = 0; i <= 1000000; i++) ans[i] = 1;
spf[1] = 1;
for(long long i = 2;i <= 1000000;i++){
if(!spf[i]){
spf[i] = i;
for(long long j = i * i;j <= 1000000;j+=i){
if(!spf[j]){
spf[j] = i;
}
}
}
}
for(long long i = 2;i <= 1000000;i++){
int tmp = i;
while(tmp != 1){
int cnt = 0, f = spf[tmp];
while(tmp % f == 0){
tmp /= spf[tmp];
cnt++;
}
ans[i] *= (cnt + 1);
}
}
int maxn = 2, maxans = ans[2];
for(long long i = 2;i <= 1000000;i++){
if(ans[i] >= maxans){
maxans = ans[i];
maxn = i;
}
ans[i] = maxn;
}
}
int main(){
IOS
int t;
sieve();
cin >> t;
while(t--){
int n;
cin >> n;
cout << ans[n] << '\n';
}
return 0;
}
```
### Tarjan's SCC Algorithm
```c
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
map<string, vector<string>> G;
map<string, int> dfn, low;
vector<string> V;
int dep;
void dfs(string u)
{
low[u] = dfn[u] = ++dep;
V.emplace_back(u);
for (auto& v : G[u])
if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
else if (count(V.begin(), V.end(), v)) low[u] = min(low[u], dfn[v]);
if (dfn[u] == low[u])
{
string temp;
while (1)
{
temp = V[V.size() - 1];
V.pop_back();
cout << temp;
if (temp != u) cout << ", ";
else break;
}
cout << "\n";
}
}
int main()
{
// fast io
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m, cases = 0;
while (cin >> n >> m, n && m)
{
// init
G.clear(), dfn.clear(), low.clear(), V.clear();
dep = 0;
// store data
while (m--)
{
string name, to;
cin >> name >> to;
G[name].emplace_back(to);
}
// find scc
if (cases) cout << "\n";
cout << "Calling circles for data set " << ++cases << ":\n";
for (auto& [i, j] : G) if (!dfn[i]) dfs(i);
}
return 0;
}
```
### Kosaraju's Algorithm
```cpp
#define MAXN 100005
stack<int> stk; //stack
vector<int> Graph[MAXN]; //graph
vector<int> Rev_Graph[MAXN]; //reverse graph
bool vis[MAXN]; //is visited
int scc[MAXN]; //i's scc
int sccid; //scc number
void dfs1(int now){
vis[now]=true;
for(auto i:Graph[now]){
if(!vis[i]) dfs1(i);
}
stk.push(now); //push now in stack before return
}
void dfs2(int now){
vis[now]=true;
scc[now]=sccid; //conbine to scc
for(auto i:Rev_Graph[now]){
if(!vis[i]) dfs2(i);
}
}
int main(){
int n,m;
cin >> n >> m;
for(int i=0;i<m;i++){
int u,v;
cin >> u >> v;
Graph[u].push_back(v);
Rev_Graph[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!vis[i]) dfs1(i); //do dfs1 of all elements
}
memset(vis,0,sizeof(vis)); //reset vis array
while(!stk.empty()){ //iterate all elements of stack
int x=stk.top();stk.pop();
if(vis[x]) continue; //skip node which has been combined to another scc
sccid++;
dfs2(x);
}
}
```
### Articulation points
給一個點皆連通的無向圖
求 割點(Articulation Points 的數量
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector< vector<int> > edge;
vector<int> dfn, low;
int result, dep;
void dfs(int cur, int par)
{
bool cut = false;
int child = 0;
dfn[cur] = low[cur] = ++dep;
for (auto& i : edge[cur]) {
if (!dfn[i]) {
++child;
dfs(i, cur);
low[cur] = min(low[cur], low[i]);
if (low[i] >= dfn[cur]) cut = true;
}
else if (i != par) low[cur] = min(low[cur], dfn[i]);
}
if ((child >= 2 || par != -1) && cut) ++result;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
while (cin >> N && N) {
cin.ignore();
result = 0, dep = 0;
edge.assign(N + 1, vector<int>());
dfn.assign(N + 1, 0);
low.assign(N + 1, 0);
string str;
while (getline(cin, str)) {
stringstream ss(str);
int u, v;
ss >> u;
if (!u) break;
while (ss >> v) edge[v].emplace_back(u), edge[u].emplace_back(v);
}
dfs(1, -1);
cout << result << "\n";
}
return 0;
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
