본문 바로가기

PS/기본구현5

FFT 코드 [ Code ] using cpx = complex; using vec = vector; const double PI = acos(-1); void FFT(vec& f, bool inv) { int n = f.size(); for (int i = 1, j = 0; i > 1; while (!((j ^= bit) & bit)) bit >>= 1; if (i < j) swap(f[i], f[j]); } for (int i = 1; i < n; i 2022. 8. 23.
플로우 - Dinic, Edmonds-Karp 알고리즘 1. [ Dinic ] const int MAX = 808; vectorg[MAX]; int work[MAX], lv[MAX], cap[MAX][MAX], flow[MAX][MAX]; struct Dinic { void add(int u, int v, int c) { g[u].push_back(v); g[v].push_back(u); cap[u][v] += c; } bool bfs(int S, int T) { memset(lv, -1, sizeof(lv)); queueq; lv[S] = 0; q.push(S); while (q.size()) { int cur = q.front(); q.pop(); for (int nxt : g[cur]) { if (lv[nxt] == -1 && cap[cur][nxt] .. 2022. 8. 8.
레이지 프로퍼게이션 코드 주석부분만 적절히 변경해주면 구간 최대,최소, 합 레이지 세그를 짤 수 있다. [ Code ] using ll = long long; const int MAX = 100001; struct segment_tree { ll lazy[4 * MAX], tree[4 * MAX]; void propa(int node, int s, int e) { if (lazy[node]) { // tree[node] += (e - s + 1) * lazy[node]; if (s != e) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } } void upd(int node, int s, int e, int qs, int q.. 2022. 8. 7.
세그먼트 트리 코드 아래 코드에서 적절히 트리의 식만 변형해주면 구간 최대,최소,합,곱 세그트리를 만들어줄 수 있다. 세그트리는 복붙보단 매번 직접 짜는걸 추천한다. [ Code ] const int MAX = 100001; struct segment_tree { int tree[4 * MAX]; void upd(int node, int s, int e, int idx, int v) { if (idxe) return; if (s == e) { tree[node] = v; return; } int m = (s + e) / 2; upd(2 * node, s, m, idx, v); upd(2 * node + 1, m + 1, e, idx, v); tree[node] = tree[2 * node] + tree[2 * node + .. 2022. 8. 7.

티스토리툴바