(업데이트 중)

알고리즘/자료구조 복붙용 라이브러리

코드에 오류가 있을 가능성 아주 높습니다

수정 및 추가 제안, 오류 제보 환영합니다

wookje.happy@gmail.com 또는 개인적으로 연락 주세요

include 인클루드

// http://wookje.dance/library/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define y1 fuckfuckfuck
#define fst first
#define snd second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v)) (v).begin(), (v).end()
#define PQ priority_queue
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {if(!a||!b)return 0;return a*(b/gcd(a,b));}
pll ext_gcd(ll a, ll b){
    if (b == 0) return { 1,0 };
    auto t = ext_gcd(b, a%b);
    return { t.second,t.first-(a/b)*t.second };
}
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct point {
    int x, y;
    bool operator <(point a)const {
        return x == a.x ? y < a.y : x < a.x;
    }
};

const int powmod = 1e9+7;
ll fast_pow(ll base, ll exp) {
    if (base == 1) return 1;
    ll ans = 1;
    while (exp) {
        if (exp & 1) {
            ans = (ans * base)%powmod;
        }
        base = (base*base)%powmod;
        exp >>= 1;
    }
    return ans;
}


int main() {
    //cin.tie(0); ios_base::sync_with_stdio(0);



    return 0;
}

Tree 트리

Fenwick Tree 펜윅 트리

point update, range query

qry(h): 1~h까지의 합
upd(h, v): h에 v만큼 더함

typedef long long ll;
const int MAXN = 1e6 + 1;

int n;
ll tree[MAXN];

inline void upd(int h, ll v) {
    for (int i = h; i <= n; i += i&-i) tree[i] += v;
}

ll qry(int h) {
    ll ret = 0;
    for (int i = h; i; i -= i&-i) ret += tree[i];
    return ret;
}

range update, point query

qry(h): h의 누적합
upd(s, e, x): [s, e]에 x만큼 더함

typedef long long ll;
const int MAXN = 1e6 + 1;

int n;
ll tree[MAXN];

inline void upd(int s, int e, ll x) {
    if (s <= e) {
        for (int i = s; i <= n; i += i&-i) tree[i] += x;
        for (int i = e+1; i <= n; i += i&-i) tree[i] -= x;
    }
    else {
        for (int i = 1; i <= n; i += i&-i) tree[i] += x;
        for (int i = s+1; i <= n; i += i&-i) tree[i] -= x;
        for (int i = e; i <= n; i += i&-i) tree[i] += x;
    }
}

ll qry(int h) {
    ll ret = 0;
    for (int i = h; i; i -= i&-i) ret += bit[i];
    return ret;
}

Non Recursive Segment Tree 비재귀 세그먼트 트리

sum, point update, range query

typedef long long ll;

const int MAXN = (1 << 20);
ll tree[MAXN*2+10];

void update(int i, ll v) {
    i += MAXN;
    while (i) {
        tree[i] += v;
        i /= 2;
    }
}

ll query(int s, int e) {
    ll sum = 0;
    s += MAXN; e += MAXN;
    while (s <= e) {
        if (s % 2 == 1) sum += tree[s];
        if (e % 2 == 0) sum += tree[e];
        s = (s + 1) / 2;
        e = (e - 1) / 2;
    }
    return sum;
}

min(max), point update, range query

TODO

Lazy Propagation 레이지

TODO

Merge Sort Tree 머지 소트 트리

TODO

PST Persistent Segment Tree 피에스티

const int MAXN = 1<<17;
int root[MAXN];
struct PST {
    int cnt = 1, v[MAXN*17], l[MAXN*17], r[MAXN*17];
    // init(s,e) : 다음 트리들을 만드는 데 베이스가 될 트리를 만든다. 이 트리의 모든 노드에는 0이 들어가 있다. [s,e]는 앞으로의 질의들이 들어갈 닫힌 범위이다.
    int init(int s, int e) {
        int idx = cnt++;
        if (s < e) {
            int m = (s+e)>>1;
            l[idx] = init(s, m);
            r[idx] = init(m+1, e);
        }
        return idx;
    }
    // update(root,s,e,pos,val) : root가 루트인 트리를 기반으로 pos 위치에 val만을 업데이트(덧셈)한 트리를 만들어, 그 루트를 반환해 준다.
    int update(int root, int s, int e, int pos, int val) {
        if (pos < s || e < pos) return root;
        int idx = cnt++;
        if (s == e) {
            v[idx] = v[root] + val;
        }
        else {
            int m = (s+e)>>1;
            l[idx] = update(l[root], s, m, pos, val);
            r[idx] = update(r[root], m+1, e, pos, val);
            v[idx] = v[l[idx]] + v[r[idx]];
        } return idx;
    }
    // query(idx,s,e,l,r) : idx를 루트로 한 트리에서 [l,r] 구간의 값의 합을 반환해 준다.
    int query(int idx, int s, int e, int x, int y) {
        if (x <= s && e <= y) return v[idx];
        else if (e < x || y < s) return 0;
        else {
            int m = (s+e)>>1;
            return query(l[idx], s, m, x, y) + query(r[idx], m+1, e, x, y);
        }
    }
} pst;

Li Chao 리차오

TODO

Flow 플로우

Dinic 디닉

O(V^2E)

#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 3333; // !!! enough MAXN required: src=MAXN-4, snk=MAXN-3 !!!
struct dinic {
    int n, src, snk;
    int lr_src, lr_snk, lr_lsum; // !!! use this IFF use L-R flow !!!
    int cur[MAXN], lvl[MAXN];
    struct edg { int idx, cap, rev; };
    vector<edg> gph[MAXN];
    void add_edge(int u, int v, int k) {
        gph[u].push_back({ v,k,(int)gph[v].size() });
        gph[v].push_back({ u,0,(int)gph[u].size()-1 });
    }
    // !!! use this IFF use L-R flow !!!
    void add_lr_edge(int u, int v, int l, int r) {
        add_edge(lr_src, v, l);
        add_edge(u, lr_snk, l);
        add_edge(u, v, r-l);
        lr_lsum += l;
    }
    void init() {
        memset(cur, 0, sizeof(cur));
        memset(lvl, 0, sizeof(lvl));
        for (int i = 0; i < MAXN; i++) gph[i].clear();
        src = MAXN-4;
        snk = MAXN-3;
        lr_src = MAXN-2;
        lr_snk = MAXN-1;
        //add_edge(snk, src, 2e9); // !!! use this IFF use L-R flow !!!
    }
    dinic() {
        init();
    }
    bool bfs(int src, int snk) {
        queue<int> que;
        memset(lvl, -1, sizeof(lvl));
        lvl[src] = 0;
        que.push(src);
        while (!que.empty()) {
            int now = que.front(); que.pop();
            for (edg nxt : gph[now]) {
                if (nxt.cap > 0 && lvl[nxt.idx] == -1) {
                    lvl[nxt.idx] = lvl[now]+1;
                    que.push(nxt.idx);
                }
            }
        }
        return lvl[snk] != -1;
    }
    ll dfs(int now, int snk, int flw) {
        if (now == snk) return flw;
        for (int &i = cur[now]; i < gph[now].size(); i++) {
            edg &nxt = gph[now][i];
            if (nxt.cap > 0 && lvl[nxt.idx] == lvl[now]+1) {
                ll ret = dfs(nxt.idx, snk, min(nxt.cap, flw));
                if (ret > 0) {
                    nxt.cap -= ret;
                    gph[nxt.idx][nxt.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    ll match() {
        ll dap = 0;
        while (bfs(src, snk)) {
            memset(cur, 0, sizeof(cur));
            ll ret;
            while (ret = dfs(src, snk, 2e9)) {
                dap += ret;
            }
        }
        return dap;
    }
    // !!! use this IFF use L-R flow !!!
    bool lr_match() {
        ll dap = 0;
        while (bfs(lr_src, lr_snk)) {
            memset(cur, 0, sizeof(cur));
            ll ret;
            while (ret = dfs(lr_src, lr_snk, 2e9)) {
                dap += ret;
            }
        }
        return (dap == lr_lsum); // true == L-R feasible
    }
} flow;

LR Flow 엘알플로우

정점 A에서 정점 B로, 하한 L, 상한 R인 간선이 있을 때 풀이법

(1) [ A→B 유량 L, 비용 -1인 간선 ], [ A→B 유량 R-L, 비용 0인 간선 ] 이후 mincost-maxflow

void add_edge(int u, int v, int l, int r) {
    addEdge(u, v, l, -1);
    addEdge(u, v, r - l, 0);
}

(2) [ 새로운 source → B, 유량 L ], [ A → 새로운 sink, 유량 L ], [ A → B, 유량 R-L ], [ 기존 sink → 기존 source, 유량 무한 ] 이후, [ 새로운 source → 새로운 sink ]의 최대 유량이 L의 합이 되는지 확인

디닉 코드 참조

MCMF 엠씨엠에프 (spfa)

O((V+E)f)

#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1111;
struct mcmf {
    int src, snk;
    int prv_v[MAXN], prv_e[MAXN], dst[MAXN], inq[MAXN];
    struct edg { int idx, cap, cst, rev; };
    vector<edg> gph[MAXN];
    void add_edge(int u, int v, int f, int c) {
        gph[u].push_back({v, f, c, gph[v].size()});
        gph[v].push_back({u, 0, -c, gph[u].size() - 1});
    }
    void init() {
        memset(prv_v, 0, sizeof(prv_v));
        memset(prv_e, 0, sizeof(prv_e));
        for (int i = 0; i < MAXN; i++) gph[i].clear();
        src = MAXN-2;
        snk = MAXN-1;
    }
    mcmf() {
        init();
    }
    bool spfa() {
        memset(dst, 0x3f, sizeof(dst));
        memset(inq, 0, sizeof(inq));
        queue<int> que;
        que.push(src);
        inq[src] = 1;
        dst[src] = 0;
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            inq[now] = 0;
            for (int i = 0; i < gph[now].size(); i++) {
                edg &nxt = gph[now][i];
                if (nxt.cap > 0 && dst[nxt.idx] > dst[now] + nxt.cst) {
                    dst[nxt.idx] = dst[now] + nxt.cst;
                    prv_v[nxt.idx] = now;
                    prv_e[nxt.idx] = i;
                    if (!inq[nxt.idx])
                        que.push(nxt.idx), inq[nxt.idx] = 1;
                }
            }
        }
        return dst[snk] != 0x3f3f3f3f;
    }
    pair<int, int> match() {
        int dap_cst = 0, dap_flw = 0;
        while (spfa()) {
            int mn_flw = 2e9;
            for (int now = snk; now != src; now = prv_v[now]) {
                int prv = prv_v[now], idx = prv_e[now];
                mn_flw = min(mn_flw, gph[prv][idx].cap);
            }
            for (int now = snk; now != src; now = prv_v[now]) {
                int prv = prv_v[now], idx = prv_e[now];
                gph[prv][idx].cap -= mn_flw;
                gph[now][gph[prv][idx].rev].cap += mn_flw;
                dap_cst += mn_flw * gph[prv][idx].cst;
            }
            dap_flw += mn_flw;
        }
        return make_pair(dap_flw, dap_cst);
    }
};

그래프 및 트리 Graph and Tree

LCA 최소 공통 조상

#include <algorithm>
#include <vector>
using namespace std;
const int n_ = 1e5 + 5;
const int d_ = 17; // 2^d > n
int n, m, d;
int dph[n_], par[n_][d_];
vector<int> gph[n_];
void setLCA(int now, int cnt) {
    dph[now] = cnt++;
    for (int i = 1; i <= d; i++)
        par[now][i] = par[par[now][i - 1]][i - 1];
    for (auto nxt : gph[now]) if (!dph[nxt])
        par[nxt][0] = now, setLCA(nxt, cnt);
}
int getLCA(int a, int b) {
    if (dph[a] < dph[b]) swap(a, b);
    for (int i = d; i >= 0; i--) if (dph[b] <= dph[par[a][i]])
        a = par[a][i];
    if (a == b) return a;
    for (int i = d; i >= 0; i--) if (par[a][i] != par[b][i])
        a = par[a][i], b = par[b][i];
    return par[a][0];
}
int main() {
    for (d = 1; (1 << d) <= n; d++); d--;
    setLCA(1, 1);
}

LCA 트리에서 두 노드 사이의 거리

#include <algorithm>
#include <vector>
using namespace std;
const int n_ = 1e5 + 5;
const int d_ = 17; // 2^d > n
int n, m, d;
int dph[n_], par[n_][d_];
vector<int> gph[n_];
void setLCA(int now, int cnt) {
    dph[now] = cnt++;
    for (int i = 1; i <= d; i++)
        par[now][i] = par[par[now][i - 1]][i - 1];
    for (auto nxt : gph[now]) if (!dph[nxt])
        par[nxt][0] = now, setLCA(nxt, cnt);
}
int dst(int a, int b) {
    int ret = 0;
    if (dph[a] < dph[b]) swap(a, b);
    for (int i = d; i >= 0; i--) if (dph[b] <= dph[par[a][i]]) {
        a = par[a][i];
        ret += (1<<i);
    }
    if (a == b) return ret;
    for (int i = d; i >= 0; i--) if (par[a][i] != par[b][i]) {
        a = par[a][i], b = par[b][i];
        ret += (1<<i)*2;
    }
    return ret+2;
}
int main() {
    for (d = 1; (1 << d) <= n; d++); d--;
    setLCA(1, 1);
}

Cut Node 단절점

#include <algorithm>
#include <vector>
using namespace std;

int cnt, chk[10001], isCutNode[10001];
vector<int> gph[10001];

void findCutNode(int now, int isRoot) {
    int vcnt = 0, vmin = n;
    chk[now] = ++cnt;
    for (int nxt : gph[now]) {
        if (!chk[nxt]) {
            findCutNode(nxt, 0);
            if (chk[nxt] == chk[now]) isCutNode[now] = 1;
            vcnt++;
        }
        vmin = min(vmin, chk[nxt]);
    }
    chk[now] = vmin;
    if (isRoot) isCutNode[now] = vcnt >= 2;
}

int main() {
    for (int i = 1; i <= n; i++) {
        if (!chk[i]) findCutNode(i, 1);
    }
}

Cut Edge 단절선

#include <vector>
#include <algorithm>
using namespace std;

int cnt, chk[100001];
vector<int> gph[100001];
vector<pair<int, int> > cutEdge;

int findCutEdge(int now, int par) {
    int ret = chk[now] = ++cnt;
    for (int nxt : gph[now]) {
        if (par == nxt) continue;
        if (!chk[nxt]) {
            int low = findCutEdge(nxt, now);
            if (low > chk[now]) {
                cutEdge.push_back({ min(now,nxt),max(now,nxt) });
            }
            ret = min(ret, low);
        }
        else {
            ret = min(ret, chk[nxt]);
        }
    }
    return ret;
}

int main() {
    findCutEdge(1, -1);
}

DP Dynamic Programming 디피 동적계획법

Convex Hull Trick CHT 컨벡스 헐 트릭

TODO

Math 수학

Eratos Get Prime 에라토스테네스의 체 소수

// [s, e] 구간의 소수들을 오름차순으로 리턴함
bool chkP[10000001]; // 배열 크기 주의
vector<ll> getPrimes(ll s, ll e) {
    vector<ll> ret;
    for (ll i = 2; i*i <= e; i++) if (!chkP[i])
        for (ll j = i*i; j <= e; j+=i) chkP[j] = 1;
    for (ll i = 2; i <= e; i++) if (!chkP[i] && s <= i && i <= e)
        ret.push_back(i);
    return ret;
}

Prime Factorization Soinsu 소인수 분해

// 밑만 리턴함, 중복 없음
vector<ll> getSoinsu(ll x) {
    ll y = x;
    vector<ll> ret;
    for (ll i = 2; i*i <= x; i++) {
        if (y%i == 0) {
            ret.push_back(i);
            while (y%i == 0) y /= i;
        }
    }
    if (y != 1) ret.push_back(y);
    return ret;
}
// (밑, 지수) 쌍들을 리턴함, 밑에 대해서 오름차순으로 리턴함
vector<pair<ll, int> > getSoinsu(ll x) {
    ll y = x;
    vector<pair<ll, int> > ret;
    for (ll i = 2; i*i <= x; i++) {
        if (y%i == 0) {
            int cnt = 0;
            while (y%i == 0) y /= i, cnt++;
            ret.push_back({ i,cnt });
        }
    }
    if (y != 1) ret.push_back({ y,1 });
    return ret;
}

GCD 최대공약수

int gcd(int a, int b){ return b?gcd(b,a%b):a; }

LCM 최소공배수

int gcd(int a, int b){ return b?gcd(b,a%b):a; }
int lcm(int a, int b) {if(!a||!b)return a+b;return a*(b/gcd(a,b));}

Extended GCD 확장 유클리드

ax+by = gcd(a, b)가 되는 정수쌍 (x, y)를 찾는다.

pair<int,int> ext_gcd(int a, int b){
    if (b == 0) return { 1,0 };
    auto t = ext_gcd(b, a%b);
    return { t.second,t.first-(a/b)*t.second };
}

Modular Inverse 모듈러 인버스

ax mod M = 1x를 찾는다.

int mod_inv(int a, int M){
    return (ext_gcd(a, M).first + M) % M;
}

Kitamasa 키타마사

선형점화식에서, O(K^3logN)의 행렬곱을 O(K^2logN)으로 떨군다.

typedef long long lint;
const int mod = 1000000007;
int k, a[1004], w[1004];
 
int add(int x, int y) { return (x+y) % mod; }
int mul(int x, int y) { return (x*(lint)y) % mod; }
 
int kitamasa(lint n) {
    vector<int> c(k+1, 0); c[1] = 1;
 
    // n = 1 만들기
    int b = 62;
    while ((n>>b)%2==0) b--;
 
    for (b--; ~b; b--) {
        // c(n) -> c(2n)
        vector<int> d(2*k+1, 0);
        for (int i=1; i<=k; i++) for (int j=1; j<=k; j++) d[i+j] = add(d[i+j], mul(c[i], c[j]));
        for (int i=2*k; i>k; i--) for (int j=1; j<=k; j++) d[i-j] = add(d[i-j], mul(d[i], w[j]));
        d.resize(k+1);
        c = d;
        // c(n) -> c(n+1)
        if ((n>>b)&1) {
            vector<int> d(k+1, 0);
            d[1] = mul(c[k], w[k]);
            for (int i=2; i<=k; i++) d[i] = c[i-1] + mul(c[k], w[k+1-i]);
            c = d;
        }
    }
 
    int ans = 0;
    for (int i=1; i<=k; i++) ans = add(ans, mul(a[i], c[i]));
    return ans;
}
 
int main() {
    lint n;
    cin >> n >> k;
    for (int i=1; i<=k; i++) cin >> a[i]; // 첫 k개의 항
    for (int i=1; i<=k; i++) cin >> w[i]; // 점화식의 계수
 
    cout << kitamasa(n);
}

FFT 빠른 푸리에 변환

O(NlogN), res[i] = for(j=0~i) a[j]*b[i-j],

#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <complex>
#include <vector>
#include <algorithm>
using namespace std;
typedef complex<double> base;
void fft(vector<base> &a, bool invert) {
    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 len=2;len<=n;len<<=1){
        double ang = 2*M_PI/len*(invert?-1:1);
        base wlen(cos(ang),sin(ang));
        for (int i=0;i<n;i+=len){
            base w(1);
            for (int j=0;j<len/2;j++){
                base u = a[i+j], v = a[i+j+len/2]*w;
                a[i+j] = u+v;
                a[i+j+len/2] = u-v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (int i=0;i<n;i++) a[i] /= n;
    }
}
vector<int> multiply(const vector<int> &a,const vector<int> &b) {
    vector <base> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < max(a.size(),b.size())) n <<= 1;
    fa.resize(n); fb.resize(n);
    fft(fa,false); fft(fb,false);
    for (int i=0;i<n;i++) fa[i] *= fb[i];
    fft(fa,true);
    vector<int> res;
    res.resize(n);
    for (int i=0;i<n;i++) res[i] = int(fa[i].real()+(fa[i].real()>0?0.5:-0.5));
    return res;
}
int main() {
    int n;                     // Rotating Multiply Example
    vector<int> a, b, res;
    scanf("%d", &n);
    a.resize(n*2); b.resize(n);
    for (int i=0;i<n;i++) {
        scanf("%d", &a[i]);
        a[i+n] = a[i];
    }
    for (int i=0;i<n;i++) {
        scanf("%d", &b[n-i-1]);
    }
    multiply(a, b, res);
    int ans = 0;
    for (int i=n;i<n*2;i++) {
        ans = max(ans, res[i]);
    }
    printf("%d", ans);
    return 0;
}

String 문자열

KMP 크누스 모리스 프랫

#include <vector>
#include <string>
using namespace std;

vector<int> search(string str, string pattern) {
    vector<int> f;
    f.push_back(0);
    for (int i = 1, k = 0; i < pattern.size(); i++) {
        while (k != 0 && pattern[k] != pattern[i]) {
            k = f[k - 1];
        }
        if (pattern[k] == pattern[i]) {
            f.push_back(++k);
        }
        else {
            f.push_back(0);
        }
    }
    int j = 0;
    vector<int> matches;
    for (int i = 0; i < str.size(); i++) {
        while (j != 0 && pattern[j] != str[i]) {
            j = f[j - 1];
        }
        if (pattern[j] == str[i]) {
            if (j + 1 == pattern.size()) {
                matches.push_back(i - (int) pattern.size() + 2);
                j = f[j];
            }
            else {
                j++;
            }
        }
    }
    return matches;
}

Suffix Array 서픽스 어레이 접미사 배열

  • sa[n] = beginning index of N-th suffix (ordered, 1-indexed), O(NlogN)
  • lcp[n] = length of common prefix between sa[n-1] and sa[n], O(N)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
vi SuffixArray(string &S) {
    int i,j,k;
    int m = 26; // 처음 알파벳 개수
    int N = S.length();
    vi SA(N+1,0), cnt(max(N,m)+1,0), x(N+1,0), y(N+1,0);
    for (i=1;i<=N;i++) cnt[x[i] = S[i]-'a'+1]++;
    for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
    for (i=N;i;i--) SA[cnt[x[i]]--] = i;
    for (int len=1,p=1;p<N;len<<=1,m=p){
        for (p=0,i=N-len;++i<=N;) y[++p] = i;
        for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
        for (i=0;i<=m;i++) cnt[i] = 0;
        for (i=1;i<=N;i++) cnt[x[y[i]]]++;
        for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
        for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i];
        swap(x,y); p = 1; x[SA[1]] = 1;
        for (i=1;i<N;i++)
            x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
    }
    return SA;
}
vi GetLcp(string &S, vi &SA) {
    int i,j,k=0;
    int N = SA.size()-1;
    vi rank(N+1,0), lcp(N+1, 0);
    for (i=1;i<=N;i++) rank[SA[i]] = i;
    for (i=1;i<=N;lcp[rank[i++]]=k)
        for (k?k--:0,j=SA[rank[i]-1];S[i+k]==S[j+k];k++);
    return lcp;
}
int main() {
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int n;
    string str;
    cin >> n >> str;
    str = '$' + str;
    vi sa = SuffixArray(str);
    vi lcp = GetLcp(str, sa);
    cout << *max_element(lcp.begin()+1, lcp.end());
    return 0;
}

Manacher 매내쳐

p[i] = i-k, ..., i, ..., i+k까지 팰린드롬인 가장 큰 k
O(N)

// 답이 long long 범위를 벗어나지 않는지 유의할 것,
// manacher를 사용하는 경우, 대체로 제한이 크기 때문에 int 범위를 벗어나는 경우가 많음
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 2000000 + 2;
int p[MAXN * 2 + 1];
char t[MAXN + 1], s[MAXN * 2 + 1];

void manacher(int n) {
    for (int i = 0; i < n; i++) {
        s[i * 2] = t[i];
        if (i != n - 1) s[i * 2 + 1] = '$';
    }
    n = n * 2 - 1;
    int r = -1, k = -1;
    for (int i = 0; i < n; i++) {
        if (i <= r) p[i] = min(r - i, p[2 * k - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && s[i - p[i] - 1] == s[i + p[i] + 1])
            p[i]++;
        if (r < i + p[i]) r = i + p[i], k = i;
    }
}

int main() {
    scanf("%s", t);
    int n = strlen(t), dap = 0;
    manacher(n);
    for (int i = 0; i < n * 2; i++) {
        if (i % 2) dap += (p[i] + 1) / 2;
        else dap += p[i] / 2;
    }
    printf("%d\n", dap + n);
    return 0;
}

Geometry 기하

Convex Hull 컨벡스헐

#include<cstdio>
#include<algorithm>
#include<tuple>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct POINT{
    int x, y;
    bool operator <(POINT a)const {
        return x == a.x ? y < a.y : x < a.x;
    }
    POINT operator -(POINT a)const {
        return { x-a.x,y-a.y };
    }
};
int N;
ll sq(int x){
    return (ll)x*x;
}
ll dst(POINT A, POINT B) {
    return sq(A.x-B.x)+sq(A.y-B.y);
}
int ccw(POINT A, POINT B, POINT C){
    ll r = A.x*B.y + B.x*C.y + C.x*A.y;
    r -= A.y*B.x + B.y*C.x + C.y*A.x;
    if (r > 0) return 1;
    if (r < 0) return -1;
    return 0;
}

vector<POINT> GetConvexHull(vector<POINT> &p) {
    swap(p[0], *min_element(p.begin(), p.end()));
    sort(p.begin()+1, p.end(), [&](const POINT &A, const POINT &B){
        if(ccw(p[0], A, B) != 0){
            return ccw(p[0], A, B) < 0;
        }
        return dst(A, p[0]) < dst(B, p[0]);
    });
    vector<POINT> hull;
    hull.push_back(p[0]);
    for(int i = 1; i < N; i++){
        while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), p[i]) >= 0){
            hull.pop_back();
        }
        hull.push_back(p[i]);
    }
    return hull;
}

pii FarthestPair(vector<POINT> &hull) {
    pii ret;
    ll mx = -1;
    for (int i = 0, j = 0; i < hull.size(); i++) {
        while (j+1 < hull.size() && ccw({ 0,0 }, hull[i+1]-hull[i], hull[j+1]-hull[j]) <= 0) {
            if (mx < dst(hull[i], hull[j])) {
                mx = dst(hull[i], hull[j]);
                ret = { i,j };
            }
            j++;
        }
        if (mx < dst(hull[i], hull[j])) {
            mx = dst(hull[i], hull[j]);
            ret = { i,j };
        }
    }
    return ret;
}

int main(){
    scanf("%d", &N);
    vector<POINT> p(N);
    for (int i = 0; i < N; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }

    vector<POINT> hull = GetConvexHull(p);
    int a, b; tie(a, b) = FarthestPair(hull);
    printf("%.8lf", sqrt(dst(hull[a], hull[b])));

    return 0;
}

Point in Polygon

#include <vector>
using namespace std;
struct point { int x, y; };
typedef vector<point> polygon;
bool isInside(point B, vector<point> &p) {
   int cross = 0;
   for (int i = 0; i < p.size(); i++){
       int j = (i+1) % p.size();
       if ((p[i].y > B.y) != (p[j].y > B.y)) {
           double atX = (p[j].x-p[i].x)*(B.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
           if (B.x < atX) cross++;
       }
   }
   return cross % 2 > 0;
}

line intersect cross 선분 교차

int ccw(point a, point b, point c) {
    // r 오버플로우 주의
    ll r = a.x * b.y + b.x * c.y + c.x * a.y;
    r -= a.y * b.x + b.y * c.x + c.y * a.x;
    if (r > 0) return 1;
    if (r < 0) return -1;
    return 0;
}

int isCross(point a, point b, point c, point d) {
    int ab = ccw(a, b, c)*ccw(a, b, d);
    int cd = ccw(c, d, a)*ccw(c, d, b);
    if (ab == 0 && cd == 0) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return c <= b && a <= d;
    }
    return ab <= 0 && cd <= 0;
}

Magic 흑마법

pbds BST

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int main(){
    ordered_set X;
    X.insert(4);
    cout << *X.find_by_order(4) << endl;
    cout << X.order_of_key(3) << endl;
}

2D arrary rotation 배열 돌리기

// Rotate n * m array A by clockwise and save in B (A: n * m, B: m * n)
void rotate90(int **A, int **B, int n, int m) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            B[i][j] = A[n - j - 1][i];
}