tags: Competitive Programming

Codebook

Author: Gino
Credit: WiwiHorz

初始模板

模板

Template

//#define BlackMagic
#ifdef BlackMagic
#include <bits/extc++.h>
using namespace __gnu_pbds;
#endif

#include <bits/stdc++.h>

/* ----------------------------------------------- */

#define elpsycongroo ios_base::sync_with_stdio(false); cin.tie(0);

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b, c) for (int i = a; i < b; i += c)
#define Each(i, v) for (auto& i : v)

#define ariter(_a, _n) _a, _a+_n
#define iter(a) a.begin(), a.end()

#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)

#define dbg(a, b) cout << "var " << a << " -> " << b << '\n';
#define dbg_itv(l, r, val) cout << "### (" << l << ", " << r << ") -> " << val << '\n';
#define flag(_a) cout << "Still alive at flag " << _a << '\n';
#define printv(_a) for (auto& _i : _a) cout << _i << ' '; cout << '\n';
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 1;
const int INF = 2147483647;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

ll len(ll L, ll R) {
    return R-L+1;
}

/* ------------------------------------------- */


int main() {
    elpsycongroo

    //
    
    return 0;
}

/* test case




*/

PBDS

Tree

// map
tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update> tr;
tr.order_of_key(123);
tr.find_by_order(123);

// set
tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> tr;
tr.order_of_key(123);
tr.find_by_order(123);

Priority Queue

__gnu_pbds::priority_queue<int, less<int> > big_q;  // Big First
__gnu_pbds::priority_queue<int, greater<int> > small_q;  // Small First
q1.join(q2);  // join

計算幾何

基本運算

Operators

pll operator+(pll a, pll b) {
    return mp(a.F + b.F, a.S + b.S);
}
pll operator-(pll a, pll b) {
    return mp(a.F - b.F, a.S - b.S);
}
pll mul(pll a, ll b) {
    return mp(a.F * b, a.S * b);
}
ll operator*(pll a, pll b) {
    return a.F * b.F + a.S * b.S;
}
ll operator^(pll a, pll b) {
    return a.F * b.S - a.S * b.F;
}
ll dis(pll a, pll b) {
    ll dx = abs(a.F-b.F), dy = abs(a.S-b.S);
    return dx * dx + dy * dy;
}
ll EulerDis(pll a, pll b) {
    return abs(a.F-b.F) + abs(a.S-b.S);
}

Quadrant of a point

int quad(pll a) {
    // origin : 1st
    // x+ : 1st
    // y+ : 2nd
    // x- : 3rd
    // y- : 4th
    int x = a.F, y = a.S;
    if (x == 0 && y == 0) return 1;
    if (x == 0) return (y > 0 ? 2 : 4);
    if (y == 0) return (x > 0 ? 1 : 3);
    if (y > 0) return (x > 0 ? 1 : 2);
    else return (x > 0 ? 4 : 3);
}

極角排序

Code

vector<pll> E;
bool CmpByAngle(pll a, pll b) {
    int qa = quad(a), qb = quad(b);
    if (qa == qb) {
        ll crs = a^b;
        if (crs == 0) return EulerDis(a, mp(0, 0)) < EulerDis(b, mp(0, 0));
        return crs > 0;
    }
    return qa < qb;
}
sort(iter(E), CmpByAngle);

方向與線段相交

Code

int ori(ll cross) {
    // vector a x b
    // 1:  a to b = counterclockwise
    // 0:  a & b in the same direction
    // -1: a to b = clockwise
    return (cross > 0) - (cross < 0);
}
int in_segment(pll a1, pll a2, pll b) {
    return (((a1-b)^(a2-b)) == 0 && (a1-b)*(a2-b)<=0);
}
int banana(pll p1, pll p2, pll q1, pll q2) {
    if (in_segment(p1, p2, q1) || in_segment(p1, p2, q2) ||
        in_segment(q1, q2, p1) || in_segment(q1, q2, p2)) {
        return 1;
    }
    return (ori((p2-q1) ^ (p1-q1)) * ori((p2-q2) ^ (p1-q2)) == -1 &&
            ori((q2-p1) ^ (q1-p1)) * ori((q2-p2) ^ (q1-p2)) == -1);
}

凸多邊形包含檢查

Code

int inPolygon(vector<pll>& E , pll p){
    for(int i = 0; i < E.size(); i++) {
        if(((p-E[i])^(E[posmd(i-1, E.size())]-E[i])) * ((p-E[i])^(E[posmd(i+1, E.size())]-E[i])) > 0)
        return false;
    }
    return true;
}

凸包

Code

vector<pll> getConvexHull(vector<pll>& E) {
    int n = E.size();
    sort(iter(E));

    vector<pll> hull;
    hull.reserve(n);

    for(int i = 0; i < 2; i++) {
        int t = hull.size();
        for(auto& pnt : E){
            while(hull.size() - t >= 2 && 
                  (back - hull[hull.size()-2])^(pnt - hull[hull.size()-2]) <= 0) {
                // <= 0: not include the node on hull's edge
                // < 0: included
                hull.pop_back();
            }
            hull.pb(pnt);
        }
        hull.pop_back();
        reverse(iter(E));
    }

    return hull;
}

凸多邊形面積

Code

ll area(vector<pll>& p){
    T ans = 0;
    for(int i = 0; i < p.size(); i++) {
        ans += p[i] ^ [(i + 1) % p.size()];
    }
    return ans / 2;
}

最近點對

Code

#define x first
#define y second

inline ll dis(pll& a, pll& b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return dx * dx + dy * dy;
}


int N;
ll ans = LLINF;
vector<pll> p, tmp;

void init() {
    cin >> N;
    p.resize(N);
}


void dfs(int l, int r) {
    int n = len(l, r);

    // small case
    if (n <= 20) {
        FOR(i, l, r, 1) {
            FOR(j, i+1, r+1, 1) {
                ans = min(ans, dis(p[i], p[j]));
            }
        }
        return;
    }

    // divide (using x coordinate of median point)
    int mid = (l+r) / 2;
    int ml = mid, mr = mid;
    ll midx = p[mid].x;
    while (l <= ml && p[ml].x == midx) ml--;
    while (mr <= r && p[mr].x == midx) mr++;
    if (l <= ml) dfs(l, ml);
    if (mr <= r) dfs(mr, r);

    // conquer
    ll d = sqrt(ans)+1;
    tmp.clear();
    for (int i = mid; i >= l; i--) {
        if (abs(p[i].x - midx) <= d) tmp.eb(p[i]);
        else break;
    }
    for (int i = mid+1; i <= r; i++) {
        if (abs(p[i].x - midx) <= d) tmp.eb(p[i]);
        else break;
    }

    sort(iter(tmp), [&](pll& a, pll& b) {
        return a.y < b.y;
    });

    int nt = (int)tmp.size();
    REP(i, nt) {
        // considering next 3 points is enough
        for (int j = i+1, cnt = 0; j < nt && cnt < 3; j++, cnt++) {
            ans = min(ans, dis(tmp[i], tmp[j]));
        }
    }

    return;
}


int main() {
    WiwiHorz
    init();

    Each(i, p) cin >> i.x >> i.y;
    sort(iter(p));

    dfs(0, N-1);

    cout << ans << endl;


    return 0;
}

數論

GCD

Code

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

__gcd(a, b);

貝祖定理 + 模逆元

Important Concept

1. $(ax+by=c)$ has integer solution
   $⟺gcd(a,b)|c$
2. $(a^{-1}\mathrm{mod}p)$ exists
   $⟺(p\ne 1)\wedge gcd(a,p)=1$

Code

ll GCD;
pll extgcd(ll a, ll b) {
    if (b == 0) {
        GCD = a;
        return pll{1, 0};
    }
    pll ans = extgcd(b, a % b);
    return pll{ans.S, ans.F - a/b * ans.S};
}

pll bezout(ll a, ll b, ll c) {
    bool negx = (a < 0), negy = (b < 0);
    pll ans = extgcd(abs(a), abs(b));
    if (c % GCD != 0) return pll{-LLINF, -LLINF};
    return pll{ans.F * c/GCD * (negx ? -1 : 1),
               ans.S * c/GCD * (negy ? -1 : 1)};
}

ll inv(ll a, ll p) {
    if (p == 1) return -1;
    pll ans = bezout(a % p, -p, 1);
    if (ans == pll{-LLINF, -LLINF}) return -1;
    return (ans.F % p + p) % p;
}

質數線性篩

Code

vector <int> lpf;
vector <int> prime;

void seive(int n) {
    lpf.resize(n+1, 1)
    prime.clear();
    
    for(int i = 2; i <= n; i++){
        if(lpf[i] == 1){
            lpf[i] = i;
            prime.emplace_back(i);
        }
        for(int j : prime){
            if(i * j > n) break;
            lpf[i * j] = j;
            if(j == lpf[i]) break;
        }
    }
}

質因數分解

Code

vector<pii> pf;

void decompose(ll x) {
    while(x > 1){
        int d = lpf[x];
        pf.emplace_back(mp(d, 0));
        while(x % d == 0){
            pf.back().S++;
            x /= d;
        }
    }
}

圖論

最短路徑

Dijkstra

void dijk(int s) {
    priority_queue<pll, vector<pll>, greater<pll> > pq;
    fill(ariter(dis, maxn), INF);
    dis[s] = 0;
    pq.push(mp(0, s));

    while (!pq.empty()) {
        pll u = pq.top();
        pq.pop();
        if (dis[u.S] != u.F) continue;
        for (auto& e : G[u.S]) {
            if (dis[e.S] > dis[u.S] + e.F) {
                dis[e.S] = dis[u.S] + e.F;
                pq.push(mp(dis[e.S], e.S));
            }
        }
    }
}

並查集 & 最小生成樹

Code

int n, m, p[maxn], rk[maxn];
vector<pil> E; // u, v, w

bool cmp(pil a, pil b) {
    return a.S < b.S;
}

int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

void Union(int x, int y) {
    int bx = find(x), by = find(y);
    if (rk[bx] < rk[by]) {
        p[bx] = by;
    } else {
        p[by] = bx;
        if (rk[bx] == rk[by])
            rk[bx]++;
    }
}

int main() {
    Optimize
    
    // n: |V|, m: |E|
    cin >> n >> m;
    while (m--) {
        int u, v; ll w;
        cin >> u >> v >> w;
        E.emplace_back(mp(mp(u, v), w));
    }
    for (int i = 0; i <= n; i++) {
        rk[i] = 1;
        p[i] = i;
    }

    ll ans = 0;
    sort(E.begin(), E.end(), cmp);
    for (auto& i : E) {
        if (find(i.F.F) != find(i.F.S)) {
            ans += i.S;
            Union(i.F.F, i.F.S);
        }
    }

    cout << ans << '\n';
    return 0;
}

資料結構

BIT

Code

int n;  // sizeof BIT
ll bit[maxn];
ll lb(ll x) {return x & (-x);}

void modify(int x, ll val) {
    for (; x <= n; x += lb(x)) {
        bit[x] += val;
    }
}

ll qry(int x) {
    ll sum = 0;
    for (;x; x -= lb(x)) {
        sum += bit[x];
    }
    return sum;
}

稀疏表

Code

vector<int> arr;
int spt[maxn][20];
int n, q;

void build() {
    REP(i, n) spt[i][0] = arr[i];
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i+(1<<j)-1 < n; i++) {
            spt[i][j] = max(spt[i][j-1], spt[i+(1<<(j-1))][j-1]);
        }
    }
}

int hb(int x) {
    for (int j = 19; j >= 0; j--) {
        if (x & (1<<j)) return j;
    }
}

int qry(int l, int r) {
    int b = hb(len(l, r));
    return max(spt[l][b], spt[r-(1<<b)+1][b]);
}

線段樹 - 帶修改與加值懶標

Method

struct node {
    // define your value and tag here
}

void pull(int cl, int cr, int idx) {
    // Update the answer
    // No other tricks, its easy
}

void push(int l, int r, int idx, int cl, int cr, int mid) {
    /* Important Concept:
         * Every tag records their CHILDREN need to be modify
         * EXCLUDING ITSELF!!!
         * Self has already been modified when assigned tag!
     * 
     * Special Case: Leaf Node (no children)
     * Change first, Addition second
     * 
     * 1. Update children's value
     * 2. Assign the same tag to children
     * 3. Reset self's tag
     */
}

void build(int l, int r, int idx) {
    /* Special Case: Leaf Node
     * Build LEFT
     * Build RIGHT
     * if (NOT LEAF) pull()  // Because pull() needs parameters of children
     */
}

void modify(int ql, int qr, int val, int l, int r, int idx) {
    /* if (current itv not in query) return;
     * if (current itv all in query) {
         * Update value
         * Put tag
         * return;
     * }
     * PUSH()
     * Modify LEFT
     * Modify RIGHT
     * if (NOT LEAF) pull()
     */
}

int query(int ql, int qr, int val, int l, int r, int idx) {
    /* if (current itv not in query) return an unimportant value
     * if (current itv all in query) return self's value
     * PUSH()
     * Ask LEFT
     * Ask RIGHT
     * Decide which to return
     */
}

Code

struct node {
    ll mx, sum;
    ll add, mod;
    node(): mx(0), sum(0), add(0), mod(0) {}
};
typedef struct node node;

node st[maxn*4];
vector<ll> arr;

void pull(int cl, int cr, int idx) {
    st[idx].mx = max(st[cl].mx, st[cr].mx);
    st[idx].sum = st[cl].sum + st[cr].sum;
}

void push(int l, int r, int idx, int cl, int cr, int mid) {
    if (l == r) {
        st[idx].mod = 0;
        st[idx].add = 0;
        return;
    }
    ll md = st[idx].mod, ad = st[idx].add;
    if (md) {
        st[cl].sum = md * len(l, mid);
        st[cr].sum = md * len(mid+1, r);
        st[cl].mx = st[cr].mx = md;
        st[cl].mod = st[cr].mod = md;
        st[cl].add = st[cr].add = 0;
        st[idx].mod = 0;
    }
    if (ad) {
        st[cl].sum += ad * len(l, mid);
        st[cr].sum += ad * len(mid+1, r);
        st[cl].mx += ad;
        st[cr].mx += ad;
        st[cl].add += ad;
        st[cr].add += ad;
        st[idx].add = 0;
    }
}

void build(int l, int r, int idx) {
    if (l == r) {
        st[idx].sum = arr[l];
        st[idx].mx = arr[l];
        return;
    }
    int mid = (l+r) >> 1, cl = (idx<<1), cr = (idx<<1) + 1;
    build(l, mid, cl);
    build(mid+1, r, cr);
    if (l != r) pull(cl, cr, idx);
}

void addval(int ql, int qr, ll val, int l, int r, int idx) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        st[idx].mx += val;
        st[idx].sum += val * len(l, r);
        st[idx].add += val;
        return;
    }
    int mid = (l+r)>>1, cl = (idx<<1), cr = (idx<<1) + 1;
    push(l, r, idx, cl, cr, mid);
    addval(ql, qr, val, l, mid, cl);
    addval(ql, qr, val, mid+1, r, cr);
    if (l != r) pull(cl, cr, idx);
}

void modify(int ql, int qr, ll val, int l, int r, int idx) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        st[idx].mx = val;
        st[idx].sum = val * len(l, r);
        st[idx].add = 0;
        st[idx].mod = val;
        return;
    }
    int mid = (l+r)>>1, cl = (idx<<1), cr = (idx<<1) + 1;
    push(l, r, idx, cl, cr, mid);
    modify(ql, qr, val, l, mid, cl);
    modify(ql, qr, val, mid+1, r, cr);
    if (l != r) pull(cl, cr, idx);
}

ll query(int ql, int qr, int type, int l, int r, int idx) {
    /* type:
     * 3 = sum
     * 4 = max
     */
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) {
        return (type == 3 ? st[idx].sum : st[idx].mx);
    }
    int mid = (l+r)>>1, cl = (idx<<1), cr = (idx<<1) + 1;
    push(l, r, idx, cl, cr, mid);

    if (type == 3) {
        return (query(ql, qr, type, l, mid, cl) +
                query(ql, qr, type, mid+1, r, cr));
    } else {
        return max(query(ql, qr, type, l, mid, cl),
                   query(ql, qr, type, mid+1, r, cr));
    }
}

隨機

Code

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dis(1, 100);
cout << dis(rnd) << "\n";

字串

Suffix & LCP Array

Method

/* Steps to build suffix array
 * 1. Base Case: One letter
 *    Do AnySort() -> store in buc[0]
 *    Fill SA and Rank
 *
 * 2. Repeat O(log(n)) times
 *    Fill buc[0] with last result
 *    Do RadixSort()
 *    Fill SA and Rank
 *
 *    Conditions for ending in advance:
 *        if every element is distinct (Rank[i] all diff)
 *        // just end process
 *
 * Tip: Radix Sort
 *    Repeat twice
 *        Count
 *        Reset bucket (build pos array)
 *        Fill element into new bucket
 */

Code

// For Building Suffix Array and LCP Array
int n;
string s;
vector<int> suf, lcp, rk;

// For Radix Sort
vector<int> cnt, pos;
vector<pair<pii, int> > buc[2];  // 0: result, 1: temp


void init() {
    n = (int)s.size();
    suf.resize(n);
    rk.resize(n);
    cnt.resize(n);
    pos.resize(n);
    Each(i, buc) i.resize(n);
}

void radix_sort() {
    REP(t, 2) {
        fill(iter(cnt), 0);
        Each(i, buc[t]) cnt[ (t ? i.F.F : i.F.S) ]++;
        REP(i, n) {
            pos[i] = (!i ? 0 : pos[i-1] + cnt[i-1]);
        }
        Each(i, buc[t]) {
            buc[t^1][pos[ (t ? i.F.F : i.F.S) ]++] = i;
        }
    }
}

bool fill_suf() {
    bool end = true;
    REP(i, n) suf[i] = buc[0][i].S;
    rk[suf[0]] = 0;
    FOR(i, 1, n, 1) {
        int dif = (buc[0][i].F != buc[0][i-1].F);
        end &= dif;
        rk[suf[i]] = rk[suf[i-1]] + dif;
    }
    return end;
}

void sa() {
    s += (char)30;
    init();

    REP(i, n) buc[0][i] = mp(mp(s[i], s[i]), i);
    sort(iter(buc[0]));
    if (fill_suf()) return;

    for (int k = 0; (1<<k) < n; k++) {
        REP(i, n) {
            buc[0][i] = mp(mp(rk[i], rk[(i + (1<<k)) % n]), i);
        }
        radix_sort();
        if (fill_suf()) return;
    }
}

// lcp[i] = lcp(rank_i, rank_(i-1))
// lcp[0] = 0
void LCP() {
    int k = 0;
    REP(i, n-1) {
        int pi = rk[i];
        int j = suf[pi-1];
        while (s[i+k] == s[j+k]) k++;
        lcp[pi] = k;
        k = max(k-1, 0);
    }
}

int main() {
    elpsycongroo

    cin >> s;

    sa();

    REP(i, n) cout << suf[i] << ' ';
    cout << '\n';
    REP(i, n) cout << lcp[i] << ' ';
    cout << '\n';

    return 0;
}