본문 바로가기

Algorithm/Tip

알고리즘 미니 노트

대회 중 코딩 시간과 실수를 줄이기 위해 자주 쓰이는 알고리즘을 기존의 템플릿을 베이스로 템플릿화한다.

시시때때로 바뀌는 코딩 스타일에 맞춰 템플릿도 변화할 예정. 순서는 내 체감 난이도순이다.

오류, 오타 지적 감사합니다.

 

 

1. 분할 정복을 이용한 거듭제곱 exponentiation by squaring, fast power

 

ll _pow(ll x, ll y) {
	ll ret = 1;
	while(y) {
		if(y & 1) ret = ret * x % mod;
		x = x * x % mod, y >>= 1;
	}
	return ret;
}

 

 

2. 선형 시간 조합 계산 calculate combination in O(n) time, nCr

 

const int X = N << 1;

ll fac[X], inv[X];

void C_init() {
	fac[0] = inv[0] = 1;
	for(int i = 1; i < X; i++) fac[i] = fac[i - 1] * i % mod;
	inv[X - 1] = _pow(fac[X - 1], mod - 2);
	for(int i = X - 2; i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(int n, int r) {
	if(n < r) return 0;
	return fac[n] * inv[r] % mod * inv[n - r] % mod;
}
ll H(int n, int r) {
	return C(n + r - 1, r);
}

 

 

3. 분리 집합 disjoint set, union find, uf

 

int par[N], sz[N];

void init(int n) {
	iota(par, par + n + 1, 0);
	fill(sz + 1, sz + n + 1, 1);
}
int fnd(int v) {
	if(par[v] == v) return v;
	return par[v] = fnd(par[v]);
}
/*
void uni(int u, int v) {
	u = fnd(u), v = fnd(v);
	if(u == v) return;
	if(sz[u] < sz[v]) swap(u, v);
	par[v] = u, sz[u] += sz[v];
}
*/
bool uni(int u, int v) {
	u = fnd(u), v = fnd(v);
	if(u == v) return 0;
	if(sz[u] < sz[v]) swap(u, v);
	par[v] = u, sz[u] += sz[v];
	return 1;
}
bool same(int u, int v) {
	return fnd(u) == fnd(v);
}

 

struct Union_Find {

	int par[N], sz[N];

	void init(int n) {
		iota(par, par + n + 1, 0);
		fill(sz + 1, sz + n + 1, 1);
	}
	int fnd(int v) {
		if(par[v] == v) return v;
		return par[v] = fnd(par[v]);
	}
	/*
	void uni(int u, int v) {
		u = fnd(u), v = fnd(v);
		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);
		par[v] = u, sz[u] += sz[v];
	}
	*/
	bool uni(int u, int v) {
		u = fnd(u), v = fnd(v);
		if(u == v) return 0;
		if(sz[u] < sz[v]) swap(u, v);
		par[v] = u, sz[u] += sz[v];
		return 1;
	}
	bool same(int u, int v) {
		return fnd(u) == fnd(v);
	}

};

 

 

4. 다익스트라 dijkstra's algorithm

 

vector<pli> ad[N];
ll dist[N];

void init(int n) {
	for(int i = 1; i <= n; i++) ad[i].clear(), dist[i] = LINF;
}
void add_edge(int u, int v, ll val) {
	ad[u].push_back({val, v});
	// ad[v].push_back({val, u});
}
void get_dist(int st) {
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	pq.push({0LL, st}); dist[st] = 0;
	while(!pq.empty()) {
		auto [dst, u] = pq.top(); pq.pop();
		if(dst ^ dist[u]) continue;
		for(const auto &[val, v] : ad[u]) {
			if(dist[v] <= dst + val) continue;
			dist[v] = dst + val, pq.push({dist[v], v});
		}
	}
}

 

struct Dijkstra {

	vector<pli> ad[N];
	ll dist[N];

	void init(int n) {
		for(int i = 1; i <= n; i++) ad[i].clear(), dist[i] = LINF;
	}
	void add_edge(int u, int v, ll val) {
		ad[u].push_back({val, v});
		// ad[v].push_back({val, u});
	}
	void get_dist(int st) {
		priority_queue<pli, vector<pli>, greater<pli>> pq;
		pq.push({0LL, st}); dist[st] = 0;
		while(!pq.empty()) {
			auto [dst, u] = pq.top(); pq.pop();
			if(dst ^ dist[u]) continue;
			for(const auto &[val, v] : ad[u]) {
				if(dist[v] <= dst + val) continue;
				dist[v] = dst + val, pq.push({dist[v], v});
			}
		}
	}

};

 

 

5. 최소 스패닝 트리 minimum spannig tree, kruskal's algorithm, mst

 

// after union-find

vector<pair<ll, pii>> e;

void add_edge(int u, int v, ll val) {
	e.push_back({val, {u, v}});
}
ll get_ans() {
	sort(all(e));
	ll ret = 0;
	for(const auto &[val, uv] : e) {
		if(uni(uv.fi, uv.se)) ret += val;
	}
	return ret;
}

 

struct Kruskal {

	Union_Find uf;
	vector<pair<ll, pii>> e;

	void init(int n) {
		uf.init(n);
	}
	void add_edge(int u, int v, ll val) {
		e.push_back({val, {u, v}});
	}
	ll get_ans() {
		sort(all(e));
		ll ret = 0;
		for(const auto &[val, uv] : e) {
			if(uf.uni(uv.fi, uv.se)) ret += val;
		}
		return ret;
	}

};

 

 

6. 위상 정렬 topological sort

 

vector<int> ad[N];
int id[N];

void init(int n) {
	for(int i = 1; i <= n; i++) ad[i].clear(), id[i] = 0;
}
void add_edge(int u, int v) {
	ad[u].push_back(v);
	id[v]++;
}
vector<int> get_ans(int n) {
	vector<int> ret;
	queue<int> q;
	for(int i = 1; i <= n; i++) if(!id[i]) q.push(i);
	while(n--) {
		int u = q.front(); q.pop();
		ret.push_back(u);
		for(const auto &v : ad[u]) if(!--id[v]) q.push(v);
	}
	return ret;
}

 

struct Topological_sort {

	vector<int> ad[N];
	int id[N];

	void init(int n) {
		for(int i = 1; i <= n; i++) ad[i].clear(), id[i] = 0;
	}
	void add_edge(int u, int v) {
		ad[u].push_back(v);
		id[v]++;
	}
	vector<int> get_ans(int n) {
		vector<int> ret;
		queue<int> q;
		for(int i = 1; i <= n; i++) if(!id[i]) q.push(i);
		while(n--) {
			int u = q.front(); q.pop();
			ret.push_back(u);
			for(const auto &v : ad[u]) if(!--id[v]) q.push(v);
		}
		return ret;
	}

};

 

 

7. 볼록 껍질 convex hull

 

vector<pii> p, ch;

int ccw(pii a, pii b, pii c) {
	ll ret = (ll)(b.fi - a.fi) * (c.se - a.se) - (ll)(b.se - a.se) * (c.fi - a.fi);
	return ret > 0 ? 1 : ret < 0 ? -1 : 0;
}
void add_point(int x, int y) {
	p.push_back({x, y});
	if(p[0] > p.back()) swap(p[0], p.back());
}
void make_ch() {
	sort(p.begin() + 1, p.end(), [&](pii a, pii b){
		int t = ccw(p[0], a, b); return t ? t > 0 : a < b;
	});
	ch.push_back(p[0]), ch.push_back(p[1]);
	for(int i = 2; i < p.size(); i++) {
		while(ch.size() > 1) {
			pii p2 = ch.back(); ch.pop_back();
			const pii &p1 = ch.back();
			if(ccw(p1, p2, p[i]) > 0) {
				ch.push_back(p2);
				break;
			}
		}
		ch.push_back(p[i]);
	}
}

 

struct Convex_Hull {

	vector<pii> p, ch;

	int ccw(pii a, pii b, pii c) {
		ll ret = (ll)(b.fi - a.fi) * (c.se - a.se) - (ll)(b.se - a.se) * (c.fi - a.fi);
		return ret > 0 ? 1 : ret < 0 ? -1 : 0;
	}
	void add_point(int x, int y) {
		p.push_back({x, y});
		if(p[0] > p.back()) swap(p[0], p.back());
	}
	void make_ch() {
		sort(p.begin() + 1, p.end(), [&](pii a, pii b){
			int t = ccw(p[0], a, b); return t ? t > 0 : a < b;
		});
		ch.push_back(p[0]), ch.push_back(p[1]);
		for(int i = 2; i < p.size(); i++) {
			while(ch.size() > 1) {
				pii p2 = ch.back(); ch.pop_back();
				const pii &p1 = ch.back();
				if(ccw(p1, p2, p[i]) > 0) {
					ch.push_back(p2);
					break;
				}
			}
			ch.push_back(p[i]);
		}
	}

};

 

 

8. 최소 공통 조상 lowest common ancestor, lca

 

vector<int> ad[N];
int par[N][18], dep[N]; // 2 ^ k > N 인 최소 k

void add_edge(int u, int v) {
	ad[u].push_back(v);
	ad[v].push_back(u);
}
void dfs(int u, int p) {
	for(const auto &v : ad[u]) if(p ^ v) {
		par[v][0] = u, dep[v] = dep[u] + 1, dfs(v, u);
	}
}
void init(int n) {
	dfs(1, 0);
	for(int j = 1; j < 18; j++) for(int i = 1; i <= n; i++)
		par[i][j] = par[par[i][j - 1]][j - 1];
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	int gap = dep[u] - dep[v];
	for(int i = 0; i < 18; i++) if(gap & (1 << i)) u = par[u][i];
	if(u == v) return u;
	for(int i = 17; i >= 0; i--) if(par[u][i] ^ par[v][i]) {
		u = par[u][i], v = par[v][i];
	}
	return par[u][0];
}

 

struct LCA {

	vector<int> ad[N];
	int par[N][18], dep[N]; // 2 ^ k > N 인 최소 k

	void add_edge(int u, int v) {
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	void dfs(int u, int p) {
		for(const auto &v : ad[u]) if(p ^ v) {
			par[v][0] = u, dep[v] = dep[u] + 1, dfs(v, u);
		}
	}
	void init(int n) {
		dfs(1, 0);
		for(int j = 1; j < 18; j++) for(int i = 1; i <= n; i++)
			par[i][j] = par[par[i][j - 1]][j - 1];
	}
	int lca(int u, int v) {
		if(dep[u] < dep[v]) swap(u, v);
		int gap = dep[u] - dep[v];
		for(int i = 0; i < 18; i++) if(gap & (1 << i)) u = par[u][i];
		if(u == v) return u;
		for(int i = 17; i >= 0; i--) if(par[u][i] ^ par[v][i]) {
			u = par[u][i], v = par[v][i];
		}
		return par[u][0];
	}

};

 

 

9. 세그먼트 트리 segment tree

 

int n, a[N];
ll tree[N << 2];

void init(int nl = 1, int nr = n, int i = 1) {
	if(nl == nr) return tree[i] = a[nl], void();
	init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void update(int x, ll v, int nl = 1, int nr = n, int i = 1) {
	if(nl == nr) return tree[i] += v, void();
	if(x <= nm) update(x, v, nl, nm, i << 1);
	else update(x, v, nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
ll query(int l, int r, int nl = 1, int nr = n, int i = 1) {
	if(r < nl || nr < l) return 0; // 연산의 항등원
	if(l <= nl && nr <= r) return tree[i];
	return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
}

 

int n, a[N];

struct Segment_Tree {

	ll tree[N << 2]; // n과 a[N]은 전역 변수

	void init(int nl = 1, int nr = n, int i = 1) {
		if(nl == nr) return tree[i] = a[nl], void();
		init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	void update(int x, ll v, int nl = 1, int nr = n, int i = 1) {
		if(nl == nr) return tree[i] += v, void();
		if(x <= nm) update(x, v, nl, nm, i << 1);
		else update(x, v, nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	ll query(int l, int r, int nl = 1, int nr = n, int i = 1) {
		if(r < nl || nr < l) return 0; // 연산의 항등원
		if(l <= nl && nr <= r) return tree[i];
		return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
	}

};

 

 

9.5. 세그먼트 트리 추상화 segment tree generalization

 

int n, a[N];

struct node {
	ll v;
	node() : v(0) {}
	node(ll v) : v(v) {}
	node operator + (const node &o) const {
		return {v + o.v};
	}
} tree[N << 2];

void init(int nl = 1, int nr = n, int i = 1) {
	if(nl == nr) return tree[i] = node(a[nl]), void();
	init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void update(int x, int v, int nl = 1, int nr = n, int i = 1) {
	if(nl == nr) return tree[i] = node(v), void();
	if(x <= nm) update(x, v, nl, nm, i << 1);
	else update(x, v, nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
node query(int l, int r, int nl = 1, int nr = n, int i = 1) {
	if(r < nl || nr < l) return node();
	if(l <= nl && nr <= r) return tree[i];
	return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
}

 

int n, a[N];

struct Segment_Tree {
	struct node {
		ll v;
		node() : v(0) {}
		node(ll v) : v(v) {}
		node operator + (const node &o) const {
			return {v + o.v};
		}
	} tree[N << 2];
	
	void init(int nl = 1, int nr = n, int i = 1) {
		if(nl == nr) return tree[i] = node(a[nl]), void();
		init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	void update(int x, int v, int nl = 1, int nr = n, int i = 1) {
		if(nl == nr) return tree[i] = node(v), void();
		if(x <= nm) update(x, v, nl, nm, i << 1);
		else update(x, v, nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	node query(int l, int r, int nl = 1, int nr = n, int i = 1) {
		if(r < nl || nr < l) return node();
		if(l <= nl && nr <= r) return tree[i];
		return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
	}
};

 

 

10. 세그먼트 트리 구간 업데이트 segment tree and lazy propagation

 

int n, a[N];
ll tree[N << 2], lazy[N << 2];

void init(int nl = 1, int nr = n, int i = 1) {
	if(nl == nr) return tree[i] = a[nl], void();
	init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void set_lazy() {
	fill(lazy, lazy + (N << 2), 0); // 항등원으로 초기화
}
void prop(int nl, int nr, int i) { // 항등원 주의
	if(!lazy[i]) return;
	tree[i] += lazy[i] * (nr - nl + 1); // lazy 반영 개수
	if(nl ^ nr) {
		lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
		// for(int j : {i << 1, i << 1 | 1}) lazy[j] += lazy[i];
	}
	lazy[i] = 0;
}
void update(int l, int r, ll v, int nl = 1, int nr = n, int i = 1) {
	prop(nl, nr, i);
	if(r < nl || nr < l) return;
	if(l <= nl && nr <= r) return lazy[i] = v, prop(nl, nr, i), void();
	update(l, r, v, nl, nm, i << 1);
	update(l, r, v, nm + 1, nr, i << 1 | 1);
	tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
ll query(int l, int r, int nl = 1, int nr = n, int i = 1) {
	prop(nl, nr, i);
	if(r < nl || nr < l) return 0; // 연산의 항등원
	if(l <= nl && nr <= r) return tree[i];
	return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
}

 

int n, a[N];

struct Segment_Tree_Lazy {

	ll tree[N << 2], lazy[N << 2]; // n과 a[N]은 전역 변수

	void init(int nl = 1, int nr = n, int i = 1) {
		if(nl == nr) return tree[i] = a[nl], void();
		init(nl, nm, i << 1); init(nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	void set_lazy() {
		fill(lazy, lazy + (N << 2), 0); // 항등원으로 초기화
	}
	void prop(int nl, int nr, int i) { // 항등원 주의
		if(!lazy[i]) return;
		tree[i] += lazy[i] * (nr - nl + 1); // lazy 반영 개수
		if(nl ^ nr) {
			lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
			// for(int j : {i << 1, i << 1 | 1}) lazy[j] += lazy[i];
		}
		lazy[i] = 0;
	}
	void update(int l, int r, ll v, int nl = 1, int nr = n, int i = 1) {
		prop(nl, nr, i);
		if(r < nl || nr < l) return;
		if(l <= nl && nr <= r) return lazy[i] = v, prop(nl, nr, i), void();
		update(l, r, v, nl, nm, i << 1);
		update(l, r, v, nm + 1, nr, i << 1 | 1);
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
	ll query(int l, int r, int nl = 1, int nr = n, int i = 1) {
		prop(nl, nr, i);
		if(r < nl || nr < l) return 0; // 연산의 항등원
		if(l <= nl && nr <= r) return tree[i];
		return query(l, r, nl, nm, i << 1) + query(l, r, nm + 1, nr, i << 1 | 1);
	}

};

 

 

11. 펜윅 트리 fenwick tree

 

int n, a[N];
ll tree[N];

void init() {
	for(int i = 1; i <= n; i++) {
    	tree[i] += a[i];
		int j = i + (i & -i);
		if(j <= n) tree[j] += tree[i];
	}
}
void update(int x, ll v) {
	for(; x <= n; x += x & -x) tree[x] += v;
}
ll query(int x) {
	ll ret = 0;
	for(; x; x -= x & -x) ret += tree[x];
	return ret;
}
ll query(int l, int r) {
	return query(r) - query(l - 1);
}
ll get(int x) {
	return query(x) - query(x - 1);
}
int kth(int k) {
	int x = 0, i = 1;
    while(i << 1 <= n) i <<= 1;
    for(; i; i >>= 1) if(x + i <= n && tree[x + i] < k) {
    	k -= tree[x += i];
    }
    return x + 1;
}

 

int n, a[N];

struct Fenwick_Tree {

	ll tree[N]; // n과 a[N]은 전역 변수

	void init() {
		for(int i = 1; i <= n; i++) {
			tree[i] += a[i];
			int j = i + (i & -i);
			if(j <= n) tree[j] += tree[i];
		}
	}
	void update(int x, ll v) {
		for(; x <= n; x += x & -x) tree[x] += v;
	}
	ll query(int x) {
		ll ret = 0;
		for(; x; x -= x & -x) ret += tree[x];
		return ret;
	}
	ll query(int l, int r) {
		return query(r) - query(l - 1);
	}
	ll get(int x) {
		return query(x) - query(x - 1);
	}
	int kth(int k) {
		int x = 0, i = 1;
		while(i << 1 <= n) i <<= 1;
		for(; i; i >>= 1) if(x + i <= n && tree[x + i] < k) {
			k -= tree[x += i];
		}
		return x + 1;
	}

};

 

 

12. 강한 결합 요소 strongly connected component, tarjan's algorithm, scc

 

vector<int> ad[N];
int scc[N], vt[N], scnt, vcnt;
stack<int> st;

void add_edge(int u, int v) {
	ad[u].push_back(v);
}
int SCC(int u) {
	int ret = vt[u] = ++vcnt;
	st.push(u);
	for(const auto &v : ad[u]) {
		if(!vt[v]) ret = min(ret, SCC(v));
		else if(!scc[v]) ret = min(ret, vt[v]);
	}
	if(ret == vt[u]) {
		for(scnt++; st.size(); ) {
			int t = st.top(); st.pop();
			scc[t] = scnt;
			if(t == u) break;
		}
	}
	return ret;
}
void get_scc(int n) {
	for(int i = 1; i <= n; i++) if(!vt[i]) SCC(i);
	vector<vector<int>> ans(scnt + 1);
	for(int i = 1; i <= n; i++) ans[scc[i]].push_back(i);
}

 

struct SCC {

	vector<int> ad[N];
	int scc[N], vt[N], scnt, vcnt;
	stack<int> st;

	void add_edge(int u, int v) {
		ad[u].push_back(v);
	}
	int SCC(int u) {
		int ret = vt[u] = ++vcnt;
		st.push(u);
		for(const auto &v : ad[u]) {
			if(!vt[v]) ret = min(ret, SCC(v));
			else if(!scc[v]) ret = min(ret, vt[v]);
		}
		if(ret == vt[u]) {
			for(scnt++; st.size(); ) {
				int t = st.top(); st.pop();
				scc[t] = scnt;
				if(t == u) break;
			}
		}
		return ret;
	}
	void get_scc(int n) {
		for(int i = 1; i <= n; i++) if(!vt[i]) SCC(i);
		vector<vector<int>> ans(scnt + 1);
		for(int i = 1; i <= n; i++) ans[scc[i]].push_back(i);
	}

};

 

 

13. 디닉 dinic's algorithm

비용 부여와 간선 삽입은 분단의 슬픔 코드 참고. (정점 분할은 마피아)

 

const int V = 505;
int s = 0, t = 501;
ll c[V][V], f[V][V];
vector<int> ad[V];
int lev[V], work[V];
bool chk[V];

void add_edge(int u, int v) {
	ad[u].push_back(v);
	ad[v].push_back(u);
}
bool bfs() {
	memset(lev, -1, sizeof lev);
	queue<int> q; q.push(s);
	lev[s] = 0;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(const auto &v : ad[u]) {
			if(!~lev[v] && c[u][v] > f[u][v]) {
				lev[v] = lev[u] + 1;
				q.push(v);
			}
		}
	}
	return ~lev[t];
}
ll dfs(int u, ll tot) {
	if(u == t) return tot;
	for(auto &i = work[u]; i < ad[u].size(); i++){
		int v = ad[u][i];
		if(lev[v] == lev[u] + 1 && c[u][v] > f[u][v]) {
			int flow = dfs(v, min(tot, c[u][v] - f[u][v]));
			if(flow > 0) {
				f[u][v] += flow;
				f[v][u] -= flow;
				return flow;
			}
		}
	}
	return 0;
}
ll max_flow() {
	ll ret = 0;
	while(bfs()) {
		memset(work, 0, sizeof work);
		while(1) {
			ll flow = dfs(s,INF);
			if(!flow) break;
			ret += flow;
		}
	}
	return ret;
}
void decom() {
	queue<ll> q; q.push(s); chk[s] = 1;
	while(!q.empty()) {
		ll u = q.front(); q.pop();
		for(const auto &v : ad[u]){
			if(!chk[v] && c[u][v] > f[u][v]) {
				chk[v] = 1;
				q.push(v);
			}
		}
	}
}

 

struct Dinic {

	const int V = 505;
	int s = 0, t = 501;
	ll c[V][V], f[V][V];
	vector<int> ad[V];
	int lev[V], work[V];
	bool chk[V];
	
	void add_edge(int u, int v) {
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	bool bfs() {
		memset(lev, -1, sizeof lev);
		queue<int> q; q.push(s);
		lev[s] = 0;
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for(const auto &v : ad[u]) {
				if(!~lev[v] && c[u][v] > f[u][v]) {
					lev[v] = lev[u] + 1;
					q.push(v);
				}
			}
		}
		return ~lev[t];
	}
	ll dfs(int u, ll tot) {
		if(u == t) return tot;
		for(auto &i = work[u]; i < ad[u].size(); i++){
			int v = ad[u][i];
			if(lev[v] == lev[u] + 1 && c[u][v] > f[u][v]) {
				int flow = dfs(v, min(tot, c[u][v] - f[u][v]));
				if(flow > 0) {
					f[u][v] += flow;
					f[v][u] -= flow;
					return flow;
				}
			}
		}
		return 0;
	}
	ll max_flow() {
		ll ret = 0;
		while(bfs()) {
			memset(work, 0, sizeof work);
			while(1) {
				ll flow = dfs(s,INF);
				if(!flow) break;
				ret += flow;
			}
		}
		return ret;
	}
	void decom() {
		queue<ll> q; q.push(s); chk[s] = 1;
		while(!q.empty()) {
			ll u = q.front(); q.pop();
			for(const auto &v : ad[u]){
				if(!chk[v] && c[u][v] > f[u][v]) {
					chk[v] = 1;
					q.push(v);
				}
			}
		}
	}

};

 

 

14. 고속 푸리에 변환 fast fourier transform, fft

 

typedef complex<double> cpx;

void fft(vector<cpx> &a, bool inv) {
	int n = a.size();
	for(int i = 1, j = 0; i < n; i++) {
		int bit = n >> 1;
		for(; j >= bit; bit >>= 1) j -= bit;
		j += bit;
		if(i < j) swap(a[i], a[j]);
	}
	for(int i = 2; i <= n; i <<= 1) {
		double ang = 2 * PI / i * (inv ? -1 : 1);
		cpx wi(cos(ang), sin(ang));
		for(int j = 0; j < n; j += i) {
			cpx w(1);
			for(int k = 0; k < i >> 1; k++) {
				cpx u = a[j | k], v = a[j | k | i >> 1] * w;
				a[j | k] = u + v;
				a[j | k | i >> 1] = u - v;
				w *= wi;
			}
		}
	}
	if(inv) for(int i = 0; i < n; i++) a[i] /= n;
}

vector<ll> multiply(vector<ll> &a, vector<ll> &b) {
	vector<cpx> fa(all(a)), fb(all(b));
	int n = 1; while(n < a.size() + b.size()) n <<= 1;
	fa.resize(n); fb.resize(n);
	fft(fa, 0); fft(fb, 0);
	for(int i = 0; i < n; i++) fa[i] *= fb[i];
	fft(fa, 1);
	vector<ll> ret(n);
	for(int i = 0; i < n; i++) ret[i] = round(fa[i].real());
	return ret;
}

 

typedef complex<double> cpx;

void fft(vector<cpx> &a, bool inv) {
	int n = a.size();
	vector<cpx> root(n >> 1);
	for(int i = 1, j = 0; i < n; i++) {
		int bit = n >> 1;
		for(; j >= bit; bit >>= 1) j -= bit;
		j += bit;
		if(i < j) swap(a[i], a[j]);
	}
	double ang = 2 * PI / n * (inv ? -1 : 1);
	for(int i = 0; i < n >> 1; i++) root[i] = cpx(cos(ang * i), sin(ang * i));
	for(int i = 2; i <= n; i <<= 1) {
		int step = n / i;
		for(int j = 0; j < n; j += i) for(int k = 0; k < i >> 1; k++) {
			cpx u = a[j | k], v = a[j | k | i >> 1] * root[step * k];
			a[j | k] = u + v; a[j | k | i >> 1] = u - v;
		}
	}
	if(inv) for(int i = 0; i < n; i++) a[i] /= n;
}

vector<ll> multiply(vector<ll> &a, vector<ll> &b) {
	vector<cpx> fa(all(a)), fb(all(b));
	int n = 1; while(n < a.size() + b.size()) n <<= 1;
	fa.resize(n), fb.resize(n);
	fft(fa, 0); fft(fb, 0);
	for(int i = 0; i < n; i++) fa[i] *= fb[i];
	fft(fa, 1);
	vector<ll> ret(n);
	for(int i = 0; i < n; i++) ret[i] = round(fa[i].real());
	return ret;
}

 

 

14. 리차오 트리 li chao tree

 

struct Line {
	ll a, b;
	ll f(ll x) { return a * x + b; }
	Line() : a(0), b(-LINF) {}
	Line(ll a, ll b) : a(a), b(b) {}
};

struct Node {
	ll xl, xr; int l = -1, r = -1;
	Line ln = Line();
};

vector<Node> tree;

void init(ll xmin, ll xmax) {
	tree.push_back({xmin, xmax});
}
void update(Line L, int i = 0) {
	ll xl = tree[i].xl, xr = tree[i].xr;
	Line low = tree[i].ln, high = L;
	if(low.f(xl) > high.f(xl)) swap(low, high);
	if(low.f(xr) <= high.f(xr)) return tree[i].ln = high, void();
	if(low.f(xm) <= high.f(xm)) {
		tree[i].ln = high;
		if(tree[i].r == -1) {
			tree[i].r = tree.size();
			tree.push_back({xm + 1, xr});
		}
		update(low, tree[i].r);
	}
	else {
		tree[i].ln = low;
		if(tree[i].l == -1) {
			tree[i].l = tree.size();
			tree.push_back({xl, xm});
		}
		update(high, tree[i].l);
	}
}
ll query(ll x, int i = 0) {
	if(i == -1) return -LINF;
	ll xl = tree[i].xl, xr = tree[i].xr;
	if(x <= xm) return max(tree[i].ln.f(x), query(x, tree[i].l));
	else return max(tree[i].ln.f(x), query(x, tree[i].r));
}

 

struct Line {
	ll a, b;
	ll f(ll x) { return a * x + b; }
	Line() : a(0), b(LINF) {}
	Line(ll a, ll b) : a(a), b(b) {}
};

struct Node {
	ll xl, xr; int l = -1, r = -1;
	Line ln = Line();
};

vector<Node> tree;

void init(ll xmin, ll xmax) {
	tree.push_back({xmin, xmax});
}
void update(Line L, int i = 0) {
	ll xl = tree[i].xl, xr = tree[i].xr;
	Line low = tree[i].ln, high = L;
	if(low.f(xl) > high.f(xl)) swap(low, high);
	if(low.f(xr) <= high.f(xr)) return tree[i].ln = low, void();
	if(low.f(xm) <= high.f(xm)) {
		tree[i].ln = low;
		if(tree[i].r == -1) {
			tree[i].r = tree.size();
			tree.push_back({xm + 1, xr});
		}
		update(high, tree[i].r);
	}
	else {
		tree[i].ln = high;
		if(tree[i].l == -1) {
			tree[i].l = tree.size();
			tree.push_back({xl, xm});
		}
		update(low, tree[i].l);
	}
}
ll query(ll x, int i = 0) {
	if(i == -1) return LINF;
	ll xl = tree[i].xl, xr = tree[i].xr;
	if(x <= xm) return min(tree[i].ln.f(x), query(x, tree[i].l));
	else return min(tree[i].ln.f(x), query(x, tree[i].r));
}

 

 

번외. 랜덤 random

 

struct Random {
	mt19937 rd;
	Random() : rd((unsigned)chrono::steady_clock::now().time_since_epoch().count()) {}
	Random(int seed) : rd(seed) {}
	template<typename T = int> T GetInt(T l = 0, T r = 32767) {
		return uniform_int_distribution<T>(l, r)(rd);
	}
	template<typename T = double> T GetDouble(T l = 0, T r = 1) {
		return uniform_real_distribution<T>(l, r)(rd);
	}
} Rand;

// Ref: https://blog.naver.com/jinhan814/222723278297

 

 

- 변수명이 겹칠 위험이 있으면 클래스를 사용하자.

- 블랙박스가 힘들어 보이면 과감하게 새로 짜도록 하자.

 

'Algorithm > Tip' 카테고리의 다른 글

Heewon's Template  (0) 2021.01.17