芋艿酱的自用板子

文件模板 1

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define R(i, a, b) for (int i = (a); i <= (b); ++i)
#define P(i, a, b) for (int i = (b); i >= (a); --i)
#define F(v, x...) for (auto x : v)
#define G(x, head, e) for (int i = head[x]; i; i = e[i].ne)
#define Gt(x, tn, head, e) for (int i = head[x], tn = e[i].to; i; i = e[i].ne, tn = e[i].to)
#define Gw(x, tn, w, head, e) for (int i = head[x], tn = e[i].to, w = e[i].w; i; i = e[i].ne, tn = e[i].to, w = e[i].w)
#define lb(a) for (; a; a -= (a & -a))
#define lc(x, a) for (; x <= a; x += (x & -x))

#define debug(msg...) fprintf(stderr, ##msg)

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) putchar(x)
#define Yes() putc('Y'), putc('e'), putc('s'), putc('\n')
#define YES() putc('Y'), putc('E'), putc('S'), putc('\n')
#define No() putc('N'), putc('o'), putc('\n')
#define NO() putc('N'), putc('O'), putc('\n')
inline ll read() {
    ll x = 0, sgn = 0; char s = getc();
    while(!isdigit(s)) sgn |= s == '-', s = getc();
    while(isdigit(s)) x = x * 10 + s - '0', s = getc();
    return sgn ? -x : x;
}
inline void print(ll x) { if (x < 0) { putc('-'), print(-x); return; } if(x >= 10) print(x / 10); putc(x % 10 + '0'); }

bool Mbe;

void solve() {
    
}

bool Med;

int main() {
    // int t = 1;
    int t = read();
    while (t--) solve();    
    
    fprintf(stderr, "\n%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
    return 0;
}

文件模板 2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) putchar(x)
inline ll read() {
    ll x = 0, sgn = 0; char s = getc();
    while(!isdigit(s)) sgn |= s == '-', s = getc();
    while(isdigit(s)) x = x * 10 + s - '0', s = getc();
    return sgn ? -x : x;
}
inline void print(ll x) { if (x < 0) { putc('-'), print(-x); return; } if(x >= 10) print(x / 10); putc(x % 10 + '0'); }

int main() {
    

    return 0;
}

快读

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (b); i >= (a); --i)
#define go(x) for (int i = head[x], tn = e[i].to; i; i = e[i].ne, tn = e[i].to)

using ll = long long;

inline ll read(ll& x) {
    x = 0;
    int f = 0, c = getchar();
    for (; c < 48 || c > 57; c = getchar()) f |= c == 45;
    for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + c - 48;
    return x;
}

inline int read() {
    int x = 0, f = 0, c = getchar();
    for (; c < 48 || c > 57; c = getchar()) f |= c == 45;
    for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + c - 48;
    return x;
}

Pollard-Rho 快速分解素因数

namespace prime_fac {

    const int S = 8;

    long long mult_mod(long long a, long long b, long long c) {
        a %= c, b %= c;
        long long ret = 0;
        long long tmp = a;
        while (b) {
            if (b & 1) {
                ret += tmp;
                if (ret > c) ret -= c;
            }
            tmp <<= 1;
            if (tmp > c) tmp -= c;
            b >>= 1;
        }
        return ret;
    }

    long long qow_mod(long long a, long long n, long long _mod) {
        long long ret = 1;
        long long temp = a % _mod;
        while (n) {
            if (n & 1) ret = mult_mod(ret, temp, _mod);
            temp = mult_mod(temp, temp, _mod);
            n >>= 1;
        }
        return ret;
    }

    bool check(long long a, long long n, long long x, long long t) {
        long long ret = qow_mod(a, x, n);
        long long last = ret;
        for (int i = 1; i <= t; i++) {
            ret = mult_mod(ret, ret, n);
            if (ret == 1 && last != 1 && last != n - 1) return true;
            last = ret;
        }
        if (ret != 1) return true;
        return false;
    }

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    bool Miller_Rabin(long long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if ((n & 1) == 0) return false;
        long long x = n - 1;
        long long t = 0;
        while ((x & 1) == 0) { x >>= 1; t++; }

        for (int i = 0; i < S; i++) {
            long long a = rng() % (n - 1) + 1;
            if (check(a, n, x, t))
                return false;
        }

        return true;
    }

    long long factor[100];
    int tol;

    long long gcd(long long a, long long b) {
        long long t;
        while (b) {
            t = a;
            a = b;
            b = t % b;
        }
        if (a >= 0) return a;
        return -a;
    }

    long long pollard_rho(long long x, long long c) {
        long long i = 1, k = 2;
        long long x0 = rng() % (x - 1) + 1;
        long long y = x0;
        while (1) {
            i++;
            x0 = (mult_mod(x0, x0, x) + c) % x;
            long long d = gcd(y - x0, x);
            if (d != 1 && d != x) return d;
            if (y == x0) return x;
            if (i == k) { y = x0; k += k; }
        }
    }
    void findfac(long long n, int k) {
        if (n == 1) return;
        if (Miller_Rabin(n)) {
            factor[tol++] = n;
            return;
        }
        long long p = n;
        int c = k;
        while (p >= n) p = pollard_rho(p, c--);
        findfac(p, k);
        findfac(n / p, k);
    }
    vector<int> fac(long long n) {
        tol = 0;
        vector<int>ret;
        findfac(n, 107);
        for (int i = 0; i < tol; i++) ret.push_back(factor[i]);
        return ret;
    }
}

function递归

std::function<void(int)> dfs = [&](int x) {
    if (x) printf("%d ", x), dfs(t[x][0]), dfs(t[x][1]);
};

图结构类

struct graph {
    graph(int n) : head(n + 1, 0) {}

    std::vector<std::array<int, 3>> e = {{0, 0}};
    int cnt = 0;
    std::vector<int> head;
    void add(int x, int y) {
        e.push_back({y, head[x]}), head[x] = ++cnt;
    };
};

fenwick

ll c[2][N], sum[N];

void add(int k, int p, ll x) { for (; p <= n; p += (p & -p)) c[k][p] += x; }
ll ask(int k, int p) {
    ll ans = 0;
    for (; p; p -= (p & -p)) ans += c[k][p];
    return ans;
}

整体二分

P7424

给定 n 条线段，每次询问给出一个位置，求该位置被多少条线段覆盖，并阶段它们。

int n, m;

struct que {
    int l, r, k, typ, id;
} q[N], q1[N], q2[N];

int c[N], ans[N];

void add(int p, int x) { for (; p <= 2e5; p += p & -p) c[p] += x; }
int ask(int p) { int res = 0; for (; p; p -= p & -p) res += c[p]; return res; }

void solve(int l, int r, int L, int R) {
    if (l > r) return;
    if (L == R) {
        for (int i = l; i <= r; ++i) if (q[i].typ) ++ans[L];
        return;
    }
    int mid = L + R >> 1, p1 = 0, p2 = 0;
    for (int i = l; i <= r; ++i) {
        if (q[i].typ) {
            int sum = ask(q[i].r) - ask(q[i].l - 1);
            if (sum >= q[i].k) q1[++p1] = q[i];
            else q[i].k -= sum, q2[++p2] = q[i];
        } else {
            if (q[i].id <= mid) add(q[i].l, 1), q1[++p1] = q[i];
            else q2[++p2] = q[i];
        }
    }
    for (int i = 1; i <= p1; ++i) if (!q1[i].typ) add(q1[i].l, -1);
    for (int i = 1; i <= p1; ++i) q[l + i - 1] = q1[i];
    for (int i = 1; i <= p2; ++i) q[l + p1 + i - 1] = q2[i];
    solve(l, l + p1 - 1, L, mid);
    solve(l + p1, l + p1 + p2 - 1, mid + 1, R);
}

int main() {
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        int l, r, v;
        read(l, r, v);
        q[m + i] = {l, r, v, 1, i};
    }
    for (int i = 1; i <= m; ++i) {
        int x = read();
        q[i] = {x, 0, 0, 0, i};
    }
    
    solve(1, m + n, 1, m + 1);
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);

    return 0;
}

三维偏序

给定 ${a_n}$，${b_n}$，${c_n}$，求 $f_i$ 的值，其中 $f_i$ 表示满足 $a_j \leq a_i$，$b_j \leq b_i$，$c_j \leq c_i$ 的 j 的数量。

CDQ 分治

int n, k;

struct ele {
    int a, b, c, d, res;
    bool operator<(ele x) const {
        return a != x.a ? a < x.a : (b != x.b ? b < x.b : c < x.c);
    }
    bool operator==(ele x) const {
        return a == x.a && b == x.b && c == x.c;
    }
} _[N], e[N];

int cnt[N], c[N];
void add(int p, int x) { for (; p <= k; p += p & -p) c[p] += x; }
int ask(int p) { int res = 0; for (; p; p -= p & -p) res += c[p]; return res; }

void cdq(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    auto func = [&](auto x, auto y) { return x.b != y.b ? x.b < y.b : x.c < y.c; };
    sort(e + l, e + mid + 1, func);
    sort(e + mid + 1, e + r + 1, func);
    int j = l, k = mid + 1;
    for (; k <= r; ++k) {
        for (; j <= mid && e[j].b <= e[k].b; ++j)
            add(e[j].c, e[j].d);
        e[k].res += ask(e[k].c);
    }
    for (int i = l; i < j; ++i) add(e[i].c, -e[i].d);
}

int main() {
    read(n, k);
    for (int i = 1; i <= n; ++i) read(_[i].a, _[i].b, _[i].c);
    sort(_ + 1, _ + n + 1);
    int sum = 1, tot = 0;
    for (int i = 1; i <= n; ++i) {
        if (_[i + 1] == _[i]) {
            ++sum;
            continue;
        }
        e[++tot] = _[i], e[tot].d = sum;
        sum = 1;
    }
    cdq(1, tot);
    for (int i = 1; i <= tot; ++i) cnt[e[i].d + e[i].res - 1] += e[i].d;
    for (int i = 0; i < n; ++i) printf("%d\n", cnt[i]);

    return 0;
}

树套树

#define R(i, a, b) for (int i = (a); i <= (b); ++i)
#define lb(a) for (; a; a -= (a & -a))
#define lc(x, a) for (; x <= a; x += (x & -x))

int n, k;

struct ele {
    int a, b, c;
    bool operator<(ele x) const {
        return a != x.a ? a < x.a : (b != x.b ? b < x.b : c < x.c);
    }
    bool operator==(ele x) const {
        return a == x.a && b == x.b && c == x.c;
    }
} e[100007];

struct node {
    int l, r;
    int val;
    #define l(p) tr[p].l
    #define r(p) tr[p].r
    #define val(p) tr[p].val
} tr[200007 * 80];

int tot, root[200007];

int modify(int now, int x, int v, int l, int r) {
    int p = ++tot;
    tr[p] = tr[now];
    if (l == r) {
        val(p) += v;
        return p;
    }
    int mid = l + r >> 1;
    if (x <= mid) l(p) = modify(l(now), x, v, l, mid);
    else r(p) = modify(r(now), x, v, mid + 1, r);
    val(p) = val(l(p)) + val(r(p));
    return p; 
}

int query(int now, int l, int r, int L, int R) {
    if (l <= L && r >= R) return val(now);
    int mid = L + R >> 1, ans = 0;
    if (l <= mid) ans += query(l(now), l, r, L, mid);
    if (r > mid) ans += query(r(now), l, r, mid + 1, R);
    return ans;
}

void update(int x, int y, int v) {
    lc(x, k) root[x] = modify(root[x], y, v, 1, k);
}

int ask(int x, int y) {
    int ans = 0;
    lb(x) ans += query(root[x], 1, y, 1, k);
    return ans;
}

int cnt[100007];

int main() {
    n = read(), k = read();
    R(i, 1, n) e[i].a = read(), e[i].b = read(), e[i].c = read();
    sort(e + 1, e + n + 1);
    int sum = 1;
    R(i, 1, n) {
        if (e[i + 1] == e[i]) {
            ++sum;
            continue;
        }
        update(e[i].b, e[i].c, sum);
        cnt[ask(e[i].b, e[i].c)] += sum;
        sum = 1;
    }
    R(i, 1, n) print(cnt[i]), putc('\n');
    return 0;
}

线段树合并

给定一棵树，有 m 次询问。每次询问给出一条路径，路径上所有的点上存下一个给定的数字。求每个节点上出现频率最多的数字是什么。

struct node {
    int l, r;
    int val, id;

    #define l(p) tr[p].l
    #define r(p) tr[p].r
    #define val(p) tr[p].val
    #define id(p) tr[p].id
} tr[100007 * 300];

int n, m, tot, root[100007];

int insert(int now, int x, int v, int l = 1, int r = 1e5) {
    int p = ++tot;
    tr[p] = tr[now];
    if (l == r) {
        val(p) += v;
        id(p) = l;
        return p;
    }
    int mid = l + r >> 1;
    if (x <= mid) l(p) = insert(l(now), x, v, l, mid);
    else r(p) = insert(r(now), x, v, mid + 1, r);
    if (val(l(p)) >= val(r(p))) val(p) = val(l(p)), id(p) = id(l(p));
    else val(p) = val(r(p)), id(p) = id(r(p));
    return p;
}

int merge(int a, int b, int l = 1, int r = 1e5) {
    if (!a) return b;
    if (!b) return a;
    if (l == r) {
        val(a) += val(b);
        id(a) = l;
        return a;
    }
    int mid = l + r >> 1;
    l(a) = merge(l(a), l(b), l, mid);
    r(a) = merge(r(a), r(b), mid + 1, r);
    if (val(l(a)) >= val(r(a))) val(a) = val(l(a)), id(a) = id(l(a));
    else val(a) = val(r(a)), id(a) = id(r(a));
    return a;
}

struct edge {
    int to, ne;
} e[100007 * 2];

int cnt, dfn, eul[100007 * 2], loc[100007], f[100007], dep[100007], head[100007];

void preDfs(int x, int fa) {
    eul[++dfn] = x, loc[x] = dfn, f[x] = fa, dep[x] = dep[fa] + 1;
    for (int i = head[x]; i; i = e[i].ne) {
        int tn = e[i].to;
        if (tn == fa) continue;
        preDfs(tn, x);
        eul[++dfn] = x;
    }
}

int mn[100007 * 8];

void build(int p, int l, int r) {
    if (l == r) {
        mn[p] = eul[l];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    mn[p] = dep[mn[p << 1]] < dep[mn[p << 1 | 1]] ? mn[p << 1] : mn[p << 1 | 1];
}

int ask(int l, int r, int p = 1, int L = 1, int R = dfn) {
    if (L > r || R < l) return -1;
    if (L >= l && R <= r) return mn[p];
    int mid = L + R >> 1;
    int lans = ask(l, r, p << 1, L, mid);
    int rans = ask(l, r, p << 1 | 1, mid + 1, R);
    if (lans == -1 || rans == -1) return lans + rans + 1;
    return dep[lans] < dep[rans] ? lans : rans;
}

int lca(int x, int y) {
    int l = loc[x], r = loc[y];
    if (l > r) swap(l, r);
    return ask(l, r);
}

int ans[100007];

void dfs(int x, int fa) {
    for (int i = head[x]; i; i = e[i].ne) {
        int tn = e[i].to;
        if (tn == fa || dep[tn] <= dep[x]) continue;
        dfs(tn, x);
        root[x] = merge(root[x], root[tn]);
    }
    if (val(root[x])) ans[x] = id(root[x]);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d %d", &x, &y);
        e[++cnt] = {y, head[x]}, head[x] = cnt;
        e[++cnt] = {x, head[y]}, head[y] = cnt;
    }

    preDfs(1, 0);
    build(1, 1, dfn);

    for (int i = 1, x, y, z; i <= m; ++i) {
        scanf("%d %d %d", &x, &y, &z);
        int lc = lca(x, y);
        root[x] = insert(root[x], z, 1), root[y] = insert(root[y], z, 1);
        root[lc] = insert(root[lc], z, -1);
        if (f[lc]) root[f[lc]] = insert(root[f[lc]], z, -1);
    }

    dfs(1, 0);
    for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);

    return 0;
}

普通莫队

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, B, res, col[50007], cnt[50007];

struct Q {
    int id, l, r;
    bool operator<(Q x) const {
        return l / B == x.l / B ? (r == x.r ? 0 : ((l / B) & 1) ^ (r < x.r)) : l < x.l;
    }
} que[50007];

struct A {
    ll p, q;
    string k;
} ans[50007];

void move(int val, int sign) {
    sign ? res += cnt[val]++ : res -= --cnt[val];
}

int main() {
    scanf("%d %d", &n, &m);
    B = sqrt(m);
    for (int i = 1; i <= n; ++i) scanf("%d", &col[i]);
    for (int i = 1; i <= m; ++i) {
        int& l = que[i].l;
        int& r = que[i].r;
        int& id = que[i].id;
        scanf("%d %d", &l, &r);
        id = i;
    }

    sort(que + 1, que + m + 1);
    for (int i = 1, l = 1, r = 0; i <= m; ++i) {
        int L = que[i].l, R = que[i].r;
        if (L == R) {
            ans[que[i].id] = {0, 1};
            continue;
        }
        while (l > L) move(col[--l], 1);
        while (r < R) move(col[++r], 1);
        while (l < L) move(col[l++], 0);
        while (r > R) move(col[r--], 0);
        ans[que[i].id] = {res, 1ll * (r - l + 1) * (r - l) / 2};
    }

    for (int i = 1; i <= m; ++i) {
        ll tmpP = ans[que[i].id].p, tmpQ = ans[que[i].id].q;

        if (!tmpP) {
            ans[que[i].id].k = "0/1";
            continue;
        }

        ll g = __gcd(tmpP, tmpQ);
        tmpP /= g, tmpQ /= g;
        ans[que[i].id].k = to_string(tmpP) + "/" + to_string(tmpQ);
    }

    for (int i = 1; i <= m; ++i) printf("%s\n", &ans[i].k[0]);

    return 0;
}

集合哈希

struct randomhash {
     static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;  
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

class SetHasher {
    unordered_map<int, ull, randomhash> elemHash;
    mt19937_64 rng;
    public:
        SetHasher():rng(chrono::steady_clock::now().time_since_epoch().count()) {}
        ull getelemhash(const int &elem){
            if (!elemHash.count(elem)){
                elemHash[elem] = rng();
            }
            return elemHash[elem];
        }
        ull computexorhash(const vector<int> &elem){
            ull x = 0;
            for (const auto &e: elem){
                x ^= getelemhash(e);
            }
            return x;
        }
        ull add(ull curhash, const int &elem) {
            return curhash ^ getelemhash(elem);
        }
};

void solve(){
    SetHasher sh;
    int n; cin>>n;
    vector<int> a(n + 1, 0), b(n + 1, 0),c(n + 1,0);
    vector<int> ma, mb, mc;
    ma.reserve(n);
    mb.reserve(n);
    mc.reserve(n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    int cnt=0;
    ull ha = 0, hb = 0, hc = 0;
    for (int i = 1; i <= n; i++){
        ha = sh.add(ha, a[i]);
        hb = sh.add(hb, b[i]);
        hc = sh.add(hc, c[i]);
        if(ha == hb || ha == hc || hb == hc){
            cnt++;
        }
    }
    cout << cnt << '\n';
}