본문 바로가기
Algorithm/Tip

알고리즘 미니 노트

Jeuti 2022. 2. 24. 11:17

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

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

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

 

 

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

 

ll _pow(ll x, ll y) {
	ll ret = 1;
	for (; y; y >>= 1) {
        if (y & 1) ret = ret * x % mod;
        x = x * x % mod;
    }
	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, ll 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, ll 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. 최소 비용 최대 유량 min cost max flow, mcmf

 

const int N = 405, INF = 1e9;

int cap[N][N], flow[N][N], cost[N][N];
vector<int> ad[N];
int prv[N], dist[N]; bool inq[N];

void add_edge(int u, int v, int cp, int cs) {
	ad[u].push_back(v), ad[v].push_back(u);
	cap[u][v] = cp;
	cost[u][v] = cs, cost[v][u] = -cs;
}
pair<int, int> mcmf(int so, int si) {
	int flw = 0, cst = 0;
	while (1) {
		fill(prv, prv + si + 1, 0);
		fill(dist, dist + si + 1, INF);
		fill(inq, inq + si + 1, 0);
		
		dist[so] = 0;
		queue<int> q;
		q.push(so), inq[so] = 1;

		while (q.size()) {
			int u = q.front(); q.pop(), inq[u] = 0;
			for (auto &v : ad[u]) {
				if (cap[u][v] > flow[u][v] && dist[v] > dist[u] + cost[u][v]) {
					dist[v] = dist[u] + cost[u][v];
					prv[v] = u;
					if (!inq[v]) q.push(v), inq[v] = 1;
				}
			}
		}
		if (!prv[si]) break;

		int val = INF;
		for (int i = si; i ^ so; i = prv[i]) {
			val = min(val, cap[prv[i]][i] - flow[prv[i]][i]);
		}
		flw += val;
		cst += val * dist[si];
		for (int i = si; i ^ so; i = prv[i]) {
			flow[prv[i]][i] += val;
			flow[i][prv[i]] -= val;
		}
	}
	return {flw, cst};
}

 

 

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, ntt

 

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 * acos(-1) / 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(a.begin(), a.end()), fb(b.begin(), b.end());
	int n = 1, s = a.size() + b.size() - 1; while (n <= s) 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.begin(), ret.begin() + s};
}

 

typedef complex<long 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]);
	}
	log double ang = 2 * acos(-1) / 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(a.begin(), a.end()), fb(b.begin(), b.end());
	int n = 1, s = a.size() + b.size() - 1; while (n <= s) 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.begin(), ret.begin() + s};
}

 

const ll mod = (119 << 23) + 1, root = 3;

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

void ntt(vector<ll> &a) {
	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]);
	}
	static vector<ll> rt(2, 1); rt.resize(n);
	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
		ll z[] = {1, _pow(root, mod >> s)};
		for (int i = k; i < 2 * k; i++) rt[i] = rt[i / 2] * z[i & 1] % mod;
	}
	for (int k = 1; k < n; k <<= 1) {
		for (int i = 0; i < n; i += k << 1) {
			for (int j = 0; j < k; j++) {
				ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
				a[i + j + k] = ai - z + (z > ai ? mod : 0);
				ai += (ai + z >= mod ? z - mod : z);
			}
		}
	}
}

vector<ll> multiply(vector<ll> &a, vector<ll> &b) {
	int n = 1, s = a.size() + b.size() - 1; while (n <= s) n <<= 1;
    vector<ll> fa(a), fb(b), ret(n);
	fa.resize(n); fb.resize(n);
	ntt(fa); ntt(fb);
	int inv = _pow(n, mod - 2);
	for (int i = 0; i < n; i++) ret[-i & (n - 1)] = fa[i] * fb[i] % mod * inv % mod;
	ntt(ret);
	return {ret.begin(), ret.begin() + s};
}

 

 

15. 리차오 트리 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

'Algorithm/Tip' Related Articles

티스토리툴바