Skip to content

ahacad-bots/algo-templates

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

119 Commits
.gitignore
.gitignore
 
 
README.md
README.md
 
 
geometry.md
geometry.md
 
 
graph.md
graph.md
 
 

Repository files navigation

常用头部处理

直接上 Template

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

#define rep(i, x, y) for (auto i = (x); i <= (y); i++)
#define dep(i, x, y) for (auto i = (x); i >= (y); i--)
#define DEBUG false
#define ____ puts("\n_______________\n") 
#define debug(x)  if (DEBUG) cout<< #x << " => " << (x) << endl

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

void init() {
    //
}
void clear() {
    //
}
void solve() {
    //
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    rep(t, 1, T) {
        init();
        solve();
        clear();
    }
    
    return 0;
}

defines

#define rep(i, x, y) for (auto i = (x); i <= (y); i++)
#define dep(i, x, y) for (auto i = (x); i >= (y); i--)

typedef long long ll;

Debug 专用

#define ____ puts("\n_______________\n") 
#define debug(x) ____; cout<< #x << " => " << (x) << endl

快速输入输出

template <typename T>
inline T read() {
    char ch = getchar();
    T x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
template <class T>
inline void write(T x) {
    if (x < 0) x = -x, putchar('-');  // 负数输出
    static T sta[35];
    T top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + '0');
}

树

树上欧拉序

dfs 时候进栈出栈都记录一次，得到欧拉序列。

$O(1)$判祖孙关系

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

#define rep(i, x, y) for (auto i = (x); i <= (y); i++)
#define dep(i, x, y) for (auto i = (x); i >= (y); i--)
#define DEBUG false
#define ____ puts("\n_______________\n")
#define debug(x) \
    if (DEBUG) cout << #x << " => " << (x) << endl

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

const int N = 1e5 + 10;
int n, m;
int head[N], to[N], nxt[N], cnt;
int root;
void add(int x, int y) {  //链式前向星
    to[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}
int ein[N], eout[N], tot;
void dfs(int x) {
    ein[x] = ++tot;
    for (int i = head[x]; i; i = nxt[i]) {  // 遍历
        int y = to[i];
        if (!ein[y]) dfs(y);
    }
    eout[x] = ++tot;
}
void init() {
    //
}
void clear() {
    //
}
void solve() {
    //
}
bool up(int x, int y) { return (ein[x] <= ein[y] && eout[x] >= eout[y]); }
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    int x, y;
    rep(i, 1, n) {
        cin >> x >> y;
        if (y != -1) {
            add(x, y), add(y, x);
        } else {
            root = x;
        }
    }
    dfs(root);
    cin >> m;
    while (m--) {
        cin >> x >> y;
        if (up(x, y)) {
            cout << 1 << endl;
        } else if (up(y, x)) {
            cout << 2 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

线段树 (segment tree)

数组区间和

struct sgt {
    ll ans[MAXN << 2], lazy[MAXN << 2], a[MAXN];
    inline ll ls(ll x) { return x << 1; }
    inline ll rs(ll x) { return x << 1 | 1; }

    inline void push_up(ll u) { ans[u] = ans[ls(u)] + ans[rs(u)]; }
    void build(ll u, ll l, ll r) {
        lazy[u] = 0;
        if (l == r) {
            ans[u] = a[l];
            return;
        }
        ll mid = (l + r) >> 1;
        build(ls(u), l, mid);
        build(rs(u), mid + 1, r);
        push_up(u);
    }
    inline void f(ll u, ll l, ll r, ll k) {
        lazy[u] = lazy[u] + k;
        ans[u] = ans[u] + k * (r - l + 1);
    }
    inline void push_down(ll u, ll l, ll r) {
        ll mid = (l + r) >> 1;
        f(ls(u), l, mid, lazy[u]);
        f(rs(u), mid + 1, r, lazy[u]);
        lazy[u] = 0;
    }
    inline void update(ll nl, ll nr, ll l, ll r, ll u, ll k) {
        if (nl <= l && r <= nr) {
            ans[u] += k * (r - l + 1);
            lazy[u] += k;
            return;
        }
        push_down(u, l, r);
        ll mid = (l + r) >> 1;
        if (nl <= mid) update(nl, nr, l, mid, ls(u), k);
        if (nr > mid) update(nl, nr, mid + 1, r, rs(u), k);
        push_up(u);
    }
    ll query(ll q_x, ll q_y, ll l, ll r, ll u) {
        ll res = 0;
        if (q_x <= l && r <= q_y) return ans[u];
        ll mid = (l + r) >> 1;
        push_down(u, l, r);
        if (q_x <= mid) res += query(q_x, q_y, l, mid, ls(u));
        if (q_y > mid) res += query(q_x, q_y, mid + 1, r, rs(u));
        return res;
    }
} sg;

数组区间最大值

const ll maxn = 3e5; // TODO: change maxn
const ll inf = 1e20;  
ll  la[maxn];        // 用来初始化的数组
ll max1[maxn * 4];
void pushup(ll id) { max1[id] = max(max1[id << 1], max1[id << 1 | 1]); }
void build(ll id, ll l, ll r) {
    if (l == r) {
        max1[id] = la[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
void update(ll id, ll l, ll r, ll x, ll v) {
    if (l == r) {
        max1[id] = v;
        return;
    }
    ll mid = (l + r) >> 1;
    if (x <= mid)
        update(id << 1, l, mid, x, v);
    else
        update(id << 1 | 1, mid + 1, r, x, v);
    pushup(id);
}
ll query(ll id, ll l, ll r, ll x, ll y) {
    if (x <= l && y >= r) return max1[id];
    ll mid = (l + r) >> 1, ret = -inf;
    if (x <= mid) ret = max(ret, query(id << 1, l, mid, x, y));
    if (y > mid) ret = max(ret, query(id << 1 | 1, mid + 1, r, x, y));
    return ret;
}

树写法

struct node {
    int s, e, m;
    long long val = 0;
    long long lazy = 0;
    node *l, *r;

    node(int S, int E) {
        s = S, e = E, m = (s + e) / 2;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    void apply(long long L) {
        val += L * (e - s + 1);
        lazy += L;
    }
    void push() {
        if (s == e) return;
        l->apply(lazy);
        r->apply(lazy);
        lazy = 0;
    }
    void update(int S, int E, long long L) {
        push();
        if (S <= s && e <= E) {
            apply(L);
            return;
        }
        if (S <= m) l->update(S, E, L);
        if (E > m) r->update(S, E, L);
        val = l->val + r->val;
    }
    long long query(int S, int E) {
        if (S <= s && e <= E) {
            return val;
        }
        push();
        ll res = 0;
        if (S <= m) res += l->query(S, E);
        if (E > m) res += r->query(S, E);
        return res;
    }
};

数组写法 TODO



线段树维护矩阵


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

#define rep(i, x, y) for (auto i = (x); i <= (y); i++)
#define dep(i, x, y) for (auto i = (x); i >= (y); i--)
#define DEBUG false
#define ____ puts("\n_______________\n")
#define debug(x) \
    if (DEBUG) cout << #x << " => " << (x) << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
ll MOD = 571373;

void init() {
    //
}
void solve() {
    //
}
void clear() {
    //
}
struct matrix {
    ll a[2][2];
    void crt() {
        a[0][0] = a[1][1] = 1;
        a[0][1] = a[1][0] = 0;
        return;
    }
    void clear() {
        a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
        return;
    }
    void crt1(ll x) {
        clear();
        a[0][0] = x;
        a[1][1] = 1;
        return;
    }
    void crt2(ll x) {
        clear();
        a[0][0] = 1;
        a[1][0] = x;
        a[1][1] = 1;
        return;
    }
};

struct node {
    int s, e, m;
    matrix tag;
    bool flag = false;
    ll w[2];

    node *l, *r;

    node(int S, int E) {
        tag.crt();
        s = S, e = E, m = (s + e) / 2;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        } else {
            w[1] = 1;
        }
    }
    void timesA(matrix y) {
        int f[2];
        f[0] = (w[0] * y.a[0][0] + w[1] * y.a[1][0]) % MOD;
        f[1] = (w[0] * y.a[0][1] + w[1] * y.a[1][1]) % MOD;
        w[0] = f[0], w[1] = f[1];
    }
    void timesB(matrix y) {
        matrix z;
        z.a[0][0] = (tag.a[0][0] * y.a[0][0] + tag.a[0][1] * y.a[1][0]) % MOD;
        z.a[0][1] = (tag.a[0][0] * y.a[0][1] + tag.a[0][1] * y.a[1][1]) % MOD;
        z.a[1][0] = (tag.a[1][0] * y.a[0][0] + tag.a[1][1] * y.a[1][0]) % MOD;
        z.a[1][1] = (tag.a[1][0] * y.a[0][1] + tag.a[1][1] * y.a[1][1]) % MOD;
        tag = z;
        return;
    }
    void apply(matrix ntag) {
        flag = true;
        timesB(ntag);
        timesA(ntag);
    }
    void push() {
        if (s == e) return;
        if (!flag) return;
        flag = false;
        l->apply(tag);
        r->apply(tag);
        tag.crt();
    }
    void update(int S, int E, matrix type) {
        push();
        if (S <= s && e <= E) {
            apply(type);
            return;
        }
        if (S <= m) l->update(S, E, type);
        if (E > m) r->update(S, E, type);
        w[0] = (l->w[0] + r->w[0]) % MOD;
        w[1] = (l->w[1] + r->w[1]) % MOD;
        return;
    }
    long long query(int S, int E) {
        if (S <= s && e <= E) {
            return w[0];
        }
        push();
        ll res = 0;
        if (S <= m) res += l->query(S, E);
        if (E > m) res += r->query(S, E);
        res %= MOD;
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m >> MOD;
    node root(1, n);
    int tmp;
    rep(i, 1, n) {
        cin >> tmp;
        matrix type;
        type.crt2(tmp);
        root.update(i, i, type);
    }
    int op, x, y, k;
    while (m--) {
        cin >> op;
        if (op == 1 || op == 2) {
            cin >> x >> y >> k;
            matrix type;
            if (op == 1)
                type.crt1(k);
            else
                type.crt2(k);
            root.update(x, y, type);
        } else if (op == 3) {
            cin >> x >> y;
            cout << root.query(x, y) << endl;
        }
    }

    return 0;
}


树状数组 (BIT)


区间查询单点修改


#define lowbit(x) ((x) & -(x))
ll arr[N]; void add(ll x, ll k){ while(x <= n){ arr[x] += k; x += lowbit(x); } }
ll _qry(ll x){ll sum = 0; while(x) {sum += arr[x]; x -= lowbit(x);} return sum;}
ll qry(ll l , ll r){return _qry(r) - _qry(l - 1);}


区间查询区间修改


struct bit {
    ll t1[maxn], t2[maxn], n; // !!!: 注意要初始化 n 为你想要设置的数量上限
    
    void _add(ll k, ll v) {
      ll v1 = k * v;
      while (k <= n) {
        t1[k] += v, t2[k] += v1;
        k += k & -k;
      }
    }
    ll _getsum(ll *t, ll k) {
      ll ret = 0;
      while (k) {
        ret += t[k];
        k -= k & -k;
      }
      return ret;
    }
    void add(ll l, ll r, ll v) {
      _add(l, v), _add(r + 1, -v);  // 将区间加差分为两个前缀加
    }
    long long getsum(ll l, ll r) {
      return (r + 1ll) * _getsum(t1, r) - 1ll * l * _getsum(t1, l - 1) -
             (_getsum(t2, r) - _getsum(t2, l - 1));
    }
};


区间最值单点修改


int n;
int c[maxn], d[maxn];  //另开一个数组维护原始成绩值，利用它更新max
void update(int x) {
    while (x <= n) {
        d[x] = c[x];
        int lx = lowbit(x);
        for (int i = 1; i < lx; i <<= 1)  //这里是注意点
            d[x] = max(d[x], d[x - i]);
        x += lowbit(x);
    }
}
int getmax(int l, int r) {
    int ans = 0;
    while (r >= l) {
        ans = max(ans, c[r--]);
        while (r - lowbit(r) >= l) {
            ans = max(ans, d[r]);
            r -= lowbit(r);
        }
    }
    return ans;
}


Treap


FHQ Treap


#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 1;
int n, m, tot, rt;
struct Treap {
    int pos[MAX], siz[MAX], w[MAX];
    int son[MAX][2];
    bool fl[MAX];
    void pus(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1; }
    int build(int x) {
        w[++tot] = x, siz[tot] = 1, pos[tot] = rand();
        return tot;
    }
    void down(int x) {
        swap(son[x][0], son[x][1]);
        if (son[x][0]) fl[son[x][0]] ^= 1;
        if (son[x][1]) fl[son[x][1]] ^= 1;
        fl[x] = 0;
    }
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (pos[x] < pos[y]) {
            // if (fl[x]) down(x);
            son[x][1] = merge(son[x][1], y);
            pus(x);
            return x;
        }
        // if (fl[y]) down(y);
        son[y][0] = merge(x, son[y][0]);
        pus(y);
        return y;
    }
    void split(int i, int k, int &x, int &y) {
        if (!i) {
            x = y = 0;
            return;
        }
        // if (fl[i]) down(i);
        if (w[i] <= k)
            x = i, split(son[i][1], k, son[i][1], y);
        else
            y = i, split(son[i][0], k, x, son[i][0]);
        pus(i);
    }
    int kth(int now, int k) {
        while (1) {
            if (k <= siz[son[now][0]])
                now = son[now][0];
            else if (k == siz[son[now][0]] + 1)
                return now;
            else
                k -= siz[son[now][0]] + 1, now = son[now][1];
        }
    }
    void coutt(int i) {
        if (!i) return;
        // if (fl[i]) down(i);
        coutt(son[i][0]);
        printf("%d ", w[i]);
        coutt(son[i][1]);
    }
} Tree;

int main() {
    scanf("%d", &m);
    int op, a, x;
    int y, z;
    int root = 0;
    // for (int i = 1; i <= n; i++) rt = Tree.merge(rt, Tree.build(i));
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &op, &a);
        if (op == 1) {
            Tree.split(root, a, x, y);
            root = Tree.merge(Tree.merge(x, Tree.build(a)), y);
        } else if (op == 2) {
            Tree.split(root, a, x, z);
            Tree.split(x, a - 1, x, y);
            y = Tree.merge(Tree.son[y][0], Tree.son[y][1]);
            root = Tree.merge(Tree.merge(x, y), z);
        } else if (op == 3) {
            Tree.split(root, a - 1, x, y);
            printf("%d\n", Tree.siz[x] + 1);
            root = Tree.merge(x, y);
        } else if (op == 4) {
            printf("%d\n", Tree.w[Tree.kth(root, a)]);
        } else if (op == 5) {
            Tree.split(root, a - 1, x, y);
            printf("%d\n", Tree.w[Tree.kth(x, Tree.siz[x])]);
            root = Tree.merge(x, y);
        } else if (op == 6) {
            Tree.split(root, a, x, y);
            printf("%d\n", Tree.w[Tree.kth(y, 1)]);
            root = Tree.merge(x, y);
        }
    }
    return 0;
}


旋转 Treap


#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
typedef long long LL;
using namespace std;
int RD() {
    int out = 0, flag = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flag = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        out = out * 10 + c - '0';
        c = getchar();
    }
    return flag * out;
}
//第一次打treap，不压行写注释XD
const int maxn = 1000019, INF = 1e9;
//平衡树，利用BST性质查询和修改，利用随机和堆优先级来保持平衡，把树的深度控制在log
// N，保证了操作效率 基本平衡树有以下几个比较重要的函数：新建，插入，删除，旋转
//节点的基本属性有val(值)，dat(随机出来的优先级)
//通过增加属性，结合BST的性质可以达到一些效果，如siz(子树大小，查询排名)，cnt(每个节点包含的副本数)等
int na;
int ch[maxn][2];  //[i][0]代表i左儿子，[i][1]代表i右儿子
int val[maxn], dat[maxn];
int siz[maxn], cnt[maxn];
int tot, root;
int New(int v) {        //新增节点，
    val[++tot] = v;     //节点赋值
    dat[tot] = rand();  //随机优先级
    siz[tot] = 1;       //目前是新建叶子节点，所以子树大小为1
    cnt[tot] = 1;       //新建节点同理副本数为1
    return tot;
}
void pushup(int id) {  //和线段树的pushup更新一样
    siz[id] = siz[ch[id][0]] + siz[ch[id][1]] +
              cnt[id];  //本节点子树大小 = 左儿子子树大小 + 右儿子子树大小 +
                        //本节点副本数
}
void build() {
    root = New(-INF),
    ch[root][1] = New(INF);  //先加入正无穷和负无穷，便于之后操作(貌似不加也行)
    pushup(root);  //因为INF > -INF,所以是右子树，
}
void Rotate(int &id,
            int d) {  // id是引用传递，d(irection)为旋转方向，0为左旋，1为右旋
    int temp =
        ch[id][d ^ 1];  //旋转理解：找个动图看一看就好(或参见其他OIer的blog)
    ch[id][d ^ 1] =
        ch[temp][d];  //这里讲一个记忆技巧，这些数据都是被记录后马上修改
    ch[temp][d] = id;  //所以像“Z”一样
    id = temp;  //比如这个id，在上一行才被记录过，ch[temp][d]、ch[id][d ^
                // 1]也是一样的
    pushup(ch[id][d]),
        pushup(
            id);  //旋转以后siz会改变，看图就会发现只更新自己和转上来的点，pushup一下,注意先子节点再父节点
}  //旋转实质是({在满足BST的性质的基础上比较优先级}通过交换本节点和其某个叶子节点)把链叉开成二叉形状(从而控制深度)，可以看图理解一下
void insert(int &id, int v) {  // id依然是引用，在新建节点时可以体现
    if (!id) {
        id = New(v);  //若节点为空，则新建一个节点
        return;
    }
    if (v == val[id])
        cnt[id]++;  //若节点已存在，则副本数++;
    else {  //要满足BST性质，小于插到左边，大于插到右边
        int d =
            v < val[id]
                ? 0
                : 1;  //这个d是方向的意思，按照BST的性质，小于本节点则向左，大于向右
        insert(ch[id][d], v);  //递归实现
        if (dat[id] < dat[ch[id][d]])
            Rotate(id, d ^ 1);  //(参考一下图)与左节点交换右旋，与右节点交换左旋
    }
    pushup(id);  //现在更新一下本节点的信息
}
void Remove(int &id, int v) {  //最难de部分了
    if (!id) return;  //到这了发现查不到这个节点，该点不存在，直接返回
    if (v == val[id]) {  //检索到了这个值
        if (cnt[id] > 1) {
            cnt[id]--, pushup(id);
            return;
        }  //若副本不止一个，减去一个就好
        if (ch[id][0] ||
            ch[id]
              [1]) {  //发现只有一个值，且有儿子节点,我们只能把值旋转到底部删除
            if (!ch[id][1] ||
                dat[ch[id][0]] >
                    dat[ch[id]
                          [1]]) {  //当前点被移走之后，会有一个新的点补上来(左儿子或右儿子)，按照优先级，优先级大的补上来
                Rotate(id, 1),
                    Remove(
                        ch[id][1],
                        v);  //我们会发现，右旋是与左儿子交换，当前点变成右节点；左旋则是与右儿子交换，当前点变为左节点
            } else
                Rotate(id, 0), Remove(ch[id][0], v);
            pushup(id);
        } else
            id = 0;  //发现本节点是叶子节点，直接删除
        return;      //这个return对应的是检索到值de所有情况
    }
    v < val[id] ? Remove(ch[id][0], v) : Remove(ch[id][1], v);  //继续BST性质
    pushup(id);
}
int get_rank(int id, int v) {
    if (!id)
        return 0;  //若查询值不存在，返回；因为最后要减一排除哨兵节点，想要结果为-1这里就返回0
    if (v == val[id])
        return siz[ch[id][0]] +
               1;  //查询到该值，由BST性质可知：该点左边值都比该点的值(查询值)小，故rank为左儿子大小
                   //+ 1
    else if (v < val[id])
        return get_rank(ch[id][0],
                        v);  //发现需查询的点在该点左边，往左边递归查询
    else
        return siz[ch[id][0]] + cnt[id] +
               get_rank(
                   ch[id][1],
                   v);  //若查询值大于该点值。说明询问点在当前点的右侧，且此点的值都小于查询值，所以要加上cnt[id]
}
int get_val(int id, int rank) {
    if (!id) return INF;  //一直向右找找不到，说明是正无穷
    if (rank <= siz[ch[id][0]])
        return get_val(
            ch[id][0],
            rank);  //左边排名已经大于rank了，说明rank对应的值在左儿子那里
    else if (rank <= siz[ch[id][0]] + cnt[id])
        return val
            [id];  //上一步排除了在左区间的情况，若是rank在左与中(目前节点)中，则直接返回目前节点(中区间)的值
    else
        return get_val(
            ch[id][1],
            rank - siz[ch[id][0]] -
                cnt[id]);  //剩下只能在右区间找了，rank减去左区间大小和中区间，继续递归
}
int get_pre(int v) {
    int id = root, pre;  //递归不好返回，以循环求解
    while (id) {         //查到节点不存在为止
        if (val[id] < v)
            pre = val[id],
            id = ch[id][1];  //满足当前节点比目标小，往当前节点的右侧寻找最优值
        else
            id = ch
                [id]
                [0];  //无论是比目标节点大还是等于目标节点，都不满足前驱条件，应往更小处靠近
    }
    return pre;
}
int get_next(int v) {
    int id = root, next;
    while (id) {
        if (val[id] > v)
            next = val[id],
            id = ch[id][0];  //同理，满足条件向左寻找更小解(也就是最优解)
        else
            id = ch[id][1];  //与上方同理
    }
    return next;
}
int main() {
    build();  //不要忘记初始化[运行build()会连同root一并初始化，所以很重要]
    na = RD();
    for (int i = 1; i <= na; i++) {
        int cmd = RD(), x = RD();
        if (cmd == 1)
            insert(
                root,
                x);  //函数都写好了，注意：需要递归的函数都从根开始，不需要递归的函数直接查询
        else if (cmd == 2)
            Remove(root, x);
        else if (cmd == 3)
            printf(
                "%d\n",
                get_rank(root, x) -
                    1);  //注意：因为初始化时插入了INF和-INF,所以查询排名时要减1(-INF不是第一小，是“第零小”)
        else if (cmd == 4)
            printf("%d\n",
                   get_val(root, x + 1));  //同理，用排名查询值得时候要查x +
                                           // 1名，因为第一名(其实不是)是-INF
        else if (cmd == 5)
            printf("%d\n", get_pre(x));
        else if (cmd == 6)
            printf("%d\n", get_next(x));
    }
    return 0;
}


求树的直径


两次 dfs 方法求直径


const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}


求树的重心


inline void getzx(int t, int fat) {
    int i, j;
    sz[t] = 1;
    maxp[t] = 0;
    for (i = head[t]; i; i = e[i].next) {
        j = e[i].to;
        if (j == fat || vis[j]) continue;
        getzx(j, t);
        sz[t] += sz[j];
        maxp[t] = max(sz[j], maxp[t]);
    }
    maxp[t] = max(maxp[t], tot - sz[t]);
    if (maxp[t] < maxp[rt]) rt = t;
}


笛卡尔树


每个节点是一个 $(k, v)$ 二元组，一个满足二叉搜索树另一个满足堆。


单调栈超基本笛卡尔建树模板


#include <bits/stdc++.h>
#define re register
#define il inline
#define LL long long
using namespace std;
template <typename T>
il void read(T &ff) {
    T rr = 1;
    ff = 0;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') rr = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        ff = (ff << 1) + (ff << 3) + (ch ^ 48);
        ch = getchar();
    }
    ff *= rr;
}

const int N = 1e7 + 7;
int n, a[N], stk[N], ls[N], rs[N];
LL L, R;
signed main() {
    read(n);
    for (int i = 1, pos = 0, top = 0; i <= n;
         ++i) {  //这是按下标顺序插入元素的代码
        read(a[i]);
        //除了上述的维护左右儿子就是普通单调栈啦
        pos = top;
        while (pos && a[stk[pos]] > a[i]) pos--;
        if (pos) rs[stk[pos]] = i;
        if (pos < top) ls[i] = stk[pos + 1];
        stk[top = ++pos] = i;
    }
    for (int i = 1; i <= n; ++i)
        L ^= 1LL * i * (ls[i] + 1), R ^= 1LL * i * (rs[i] + 1);
    printf("%lld %lld", L, R);
    return 0;
}



笛卡尔树算最大子矩阵


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10, INF = 0x3f3f3f3f;

struct node {
  int idx, val, par, ch[2];
  friend bool operator<(node a, node b) { return a.idx < b.idx; }
  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
} tree[N];

int root, top, stk[N];
ll ans;
int cartesian_build(int n) {  //建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}
int dfs(int x) {  //一次dfs更新答案就可以了
  if (!x) return 0;
  int sz = dfs(tree[x].ch[0]);
  sz += dfs(tree[x].ch[1]);
  ans = max(ans, (ll)(sz + 1) * tree[x].val);
  return sz + 1;
}
int main() {
  int n, hi;
  while (scanf("%d", &n), n) {
    tree[0].init(0, 0, 0);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &hi);
      tree[i].init(i, hi, 0);
    }
    root = cartesian_build(n);
    ans = 0;
    dfs(root);
    printf("%lld\n", ans);
  }
  return 0;
}


树链剖分


    

  • 
$fa(x)$: 父节点
    • 

  • 
$dep(x)$: 节点深度
    • 

  • 
$siz(x)$: 子树节点个数
    • 

  • 
$son(x)$: 重子节点
    • 

  • 
$top(x)$: x 所在重链的顶部节点
    • 

  • 
$dfn(x)$: x 的 dfs 序、线段树中编号
    • 

  • 
$rnk(x)$: dfs 序对应的节点编号，dfn 反函数
    • 



const int maxn = 1e5 + 5;

int cnt, fa[maxn], son[maxn], siz[maxn], dep[maxn], dfn[maxn], rnk[maxn],
    top[maxn];
int cur, h[maxn], p[maxn], nxt[maxn];

inline void add_edge(int x, int y) {
    cur++;
    nxt[cur] = h[x];
    h[x] = cur;
    p[cur] = y;
}
void dfs1(int o) {
    son[o] = -1;                         // 重儿子初始化
    siz[o] = 1;                          // 子树节点数量初始化
    for (int j = h[o]; j; j = nxt[j]) {  // 遍历儿子
        if (!dep[p[j]]) {                // 还没有访问过、故深度为0
            dep[p[j]] = dep[o] + 1;
            fa[p[j]] = o;
            dfs1(p[j]);
            siz[o] += siz[p[j]];  // 更新子树节点数量
            if (son[o] == -1 || siz[p[j]] > siz[son[o]])
                son[o] = p[j];  // 更新重子节点
        }
    }
}
void dfs2(int o, int t) {
    top[o] = t;  // 重链顶部节点更新
    cnt++;
    dfn[o] = cnt;
    rnk[cnt] = o;
    if (son[o] == -1) return;
    dfs2(son[o], t);  // 优先遍历重子节点
    for (int j = h[o]; j; j = nxt[j])
        if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

int lca(int u, int v) { // 找公共祖先
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}

void init() {
    dep[1] = 1; // 注意根节点深度要初始化为 1
    fa[1] = 1;
    dfs1(1);
    dfs2(1, 1);
}


再来多写一个树剖后的线段树查询，注意这里 dfs2 里面需要额外多一步 nw[cnt] = w[o] 来为树上节点初始化权重。


#define ls u << 1
#define rs u << 1 | 1
struct node {
    int l, r, maxv, sum;
} tr[maxn << 2];
void build(int u, int l, int r) {
    tr[u] = {l, r, nw[r], nw[r]};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    tr[u].maxv = max(tr[ls].maxv, tr[rs].maxv);
}
void upd(int u, int x, int v) {
    if (tr[u].l == tr[u].r) {
        tr[u].maxv = tr[u].sum = v;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) {
        upd(ls, x, v);
    } else {
        upd(rs, x, v);
    }
    tr[u].sum = tr[ls].sum + tr[rs].sum;
    tr[u].maxv = max(tr[ls].maxv, tr[rs].maxv);
}
int query_sum(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0;
    if (l <= mid) res += query_sum(ls, l, r);
    if (r > mid) res += query_sum(rs, l, r);
    return res;
}
int query_max(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].maxv;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = -1e9;
    if (l <= mid) res = query_max(ls, l, r);
    if (r > mid) res = max(res, query_max(rs, l, r));
    return res;
}

int qsum(int x, int y) {
    int res = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query_sum(1, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res += query_sum(1, dfn[x], dfn[y]);
    return res;
}
int qmax(int x, int y) {
    int res = -1e9;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = max(res, query_max(1, dfn[top[x]], dfn[x]));
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    res = max(res, query_max(1, dfn[x], dfn[y]));
    return res;
}


最近公共祖先 (LCA)


左偏树（可并堆）


#include <cstdio>
#include <iostream>

#define MAXN 150010
#define swap my_swap
#define ls S[x].Son[0]
#define rs S[x].Son[1]

using namespace std;
struct Tree {
    int dis, val, Son[2], rt;
} S[MAXN];
int N, T, A, B, C, i;

inline int Merge(int x, int y);
int my_swap(int &x, int &y) { x ^= y ^= x ^= y; }
inline int Get(int x) { return S[x].rt == x ? x : S[x].rt = Get(S[x].rt); }
inline void Pop(int x) {
    S[x].val = -1, S[ls].rt = ls, S[rs].rt = rs, S[x].rt = Merge(ls, rs);
}
inline int Merge(int x, int y) {
    if (!x || !y) return x + y;
    if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y)) swap(x, y);
    rs = Merge(rs, y);
    if (S[ls].dis < S[rs].dis) swap(ls, rs);
    S[ls].rt = S[rs].rt = S[x].rt = x, S[x].dis = S[rs].dis + 1;
    return x;
}
int main() {
    cin >> N >> T;
    S[0].dis = -1;
    for (i = 1; i <= N; ++i) S[i].rt = i, scanf("%d", &S[i].val);
    for (i = 1; i <= T; ++i) {
        scanf("%d%d", &A, &B);
        if (A == 1) {
            scanf("%d", &C);
            if (S[B].val == -1 || S[C].val == -1) continue;
            int f1 = Get(B), f2 = Get(C);
            if (f1 != f2) S[f1].rt = S[f2].rt = Merge(f1, f2);
        } else {
            if (S[B].val == -1)
                printf("-1\n");
            else
                printf("%d\n", S[Get(B)].val), Pop(Get(B));
        }
    }
    return 0;
}


DP


01 背包


#include <iostream>
#include<cstring>
using namespace std;
const int nmax=1000;
 
int v[nmax];//v[i]表示第i个物品的价值value 
int w[nmax];//w[i]表示第i个物品的重量weight 
int dp[nmax];//总价值 
int n,m;//n表示物品数量，m表示背包容量
 
int main(int argc, char** argv) {//一维数组实现的01背包模板 
	while(cin>>n>>m){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=0;i<n;i++){//遍历n个物品 
			for(int j=m;j>=0;j--){//01背包容量 逆序遍历
			  if(j>=w[i]){
			  	dp[j]=max(dp[j],(dp[j-w[i]]+v[i]));
			  }//第i个物体不选，dp[j]=dp[j];
			   //第i个物体若选	dp[j]=dp[j-w[i]]+v[i]
			} 
		}
		cout<<dp[m]<<endl;
	}
}


完全背包


#include <iostream>
#include<cstring>
using namespace std;
const int nmax=1000;
 
int v[nmax];//v[i]表示第i个物品的价值value 
int w[nmax];//w[i]表示第i个物品的重量weight 
int dp[nmax];//总价值 
int n,m;//n表示物品数量，m表示背包容量
 
int main(int argc, char** argv) {//一维数组实现的完全背包模板 
	while(cin>>n>>m){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++){
			cin>>w[i]>>v[i];
		}
		for(int i=0;i<n;i++){//遍历n个物品 
			for(int j=0;j<=m;j++){//完全背包容量 顺序遍历
			  if(j>=w[i]){
			  	dp[j]=max(dp[j],(dp[j-w[i]]+v[i]));
			  }//第i个物体不选，dp[j]=dp[j];
			   //第i个物体若选	dp[j]=dp[j-w[i]]+v[i]
			} 
		}
		cout<<dp[m]<<endl;
	}
	
	return 0;
}


状压


枚举子集合


for (int sub = S; sub; sub = (sub - 1) & S) {
	// sub 为 S 的子集
}


数位


统计 $[a,b]$ 内每个数字出现次数


#include<iostream>
using std::cin;using std::cout;using std::endl;
long long a,b;//a,b为左右区间
long long ten[20],f[20];//ten[i]=10^i;ten[i]表示i-1位数第i-1位每个数字出现几次
//f[i]表示i位数的每一个数字总共出现f[i]次
long long cnta[20],cntb[20];

void work(long long x,long long *cnt){
    long long num[20] = {0};//num[i]中i>=1，i表示位数，用来存x
    num[0] = 0;//用来计数(长度length)
    while(x){//将数字x存入数组
        num[++num[0]] = x % 10;
        x /= 10;
    }
    for(int i = num[0];i >= 1;i--){//从大位往小位处理
    //由于i位的数字不见得一样，所以需要通过i位数字与i-1位的出现个数相乘
    //得到，再加上该位置该数字出现的个数，即次位数字个次位数出现的个数，
    //同时对于每一位的数字之前的数字还有一部分零散的num2需要加
        for(int j = 0;j <= 9;j++)
         cnt[j] += f[i-1] * num[i];
        for(int j = 0;j < num[i];j++)
         cnt[j] += ten[i-1];
    //所谓num2，其实是对于形如ABC的数(B为当前处理数字，A为B之前的数字串，C为B之
    //后的数字串)，而num2就是C，所以对num2的操作就是将存入数组的C提取出来，变整型
        long long num2 = 0;
        for(int j = i-1;j >= 1;j--)
         num2 = num2*10 + num[j];
        cnt[num[i]] += num2+1;
    //减去每一个零导数字，为当前位数最高位为0的数字的个数，因此减去ten[i-1]
        cnt[0] -= ten[i-1];
    }
   
}

int main(){
    cin >> a >> b;
    ten[0]=1;
    for(int i = 1;i <= 13;i++){
        f[i] = f[i-1]*10 + ten[i-1];//每一个数字出现的次数等于10倍上一层加上这一位在总数中出现的次数
        ten[i] = 10*ten[i-1];//ten[i]=10^i的计算
    }
    work(a-1,cnta);//求得a左侧的数中i出现多少次[1,a-1]
    work(b,cntb);//求得b左侧的数中i出现了多少次[a,b]
    for(int i = 0;i <= 9;i++)
        cout << cntb[i] - cnta[i] << " ";//将结果做差得到区间内的数中i出现了多少次
    return 0;
}


LIS


void solve () {
  fill(dp, dp + top, INF);
  for (int i = 0;i < top; i++) {
    *lower_bound(dp, dp + top, t[i]) = t[i];
  }
  printf("%d\n", lower_bound(dp, dp + top, INF) - dp);
}


字符串


字符串哈希


按进制哈希


ull base = 131;
int prime = 233317;
ull mod=212370440130137957ll;
ull hashe(char s[]) {
    int len = strlen(s);
    ull ans = 0;
    for (int i = 0; i < len; i++) ans = (ans * base + (ull)s[i]) % mod + prime;
    return ans;
}


BKDRHash


unsigned int BKDRHash(char* str) {
    unsigned int seed = 131;  // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return (hash % mod);
}


KMP


#include <cstring>
#include <iostream>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la, lb, j;
char a[MAXN], b[MAXN];
int main() {
    cin >> (a + 1);
    cin >> (b + 1);
    la = strlen(a + 1);
    lb = strlen(b + 1);
    for (int i = 2; i <= lb; i++) {
        while (j && b[i] != b[j + 1]) j = kmp[j];
        if (b[j + 1] == b[i]) j++;
        kmp[i] = j;
    }
    j = 0;
    for (int i = 1; i <= la; i++) {
        while (j > 0 && b[j + 1] != a[i]) j = kmp[j];
        if (b[j + 1] == a[i]) j++;
        if (j == lb) {
            cout << i - lb + 1 << endl;
            j = kmp[j];
        }
    }

    for (int i = 1; i <= lb; i++) cout << kmp[i] << " ";
    return 0;
}


Manacher


线性求最长回文串。


#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 11000002;
char dat[maxn << 1];
int p[maxn << 1], cnt, ans;
inline void qr() {
    char c = getchar();
    dat[0] = '~', dat[cnt = 1] = '|';
    while (c < 'a' || c > 'z') c = getchar();
    while (c >= 'a' && c <= 'z')
        dat[++cnt] = c, dat[++cnt] = '|', c = getchar();
}
int main() {
    qr();
    for (int t = 1, r = 0, mid = 0; t <= cnt; ++t) {
        if (t <= r) p[t] = min(p[(mid << 1) - t], r - t + 1);
        while (dat[t - p[t]] == dat[t + p[t]]) ++p[t];
        if (p[t] + t > r) r = p[t] + t - 1, mid = t;
        if (p[t] > ans) ans = p[t];
    }
    printf("%d\n", ans - 1);
    return 0;
}


Lyndon 分解


#include <cstdio>
#include <cstring>
char s[5000005];
int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    int i, j, k, ans = 0;
    i = 1;
    while (i <= len) {
        for (j = i, k = i + 1; k <= len && s[k] >= s[j]; ++k)
            if (s[k] > s[j])
                j = i;
            else
                ++j;
        while (i <= j) ans ^= (i + k - j - 1), i += k - j;
    }
    printf("%d", ans);
    return 0;
}


AC 自动机


统计每个子串出现次数


// AC自动机加强版
#include <bits/stdc++.h>
#define maxn 1000001
using namespace std;
char s[151][maxn], T[maxn];
int n, cnt, vis[maxn], ans;
struct kkk {
    int son[26], fail, flag;
    void clear() {
        memset(son, 0, sizeof(son));
        fail = flag = 0;
    }
} trie[maxn];
void insert(char* s, int num) {
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int v = s[i] - 'a';
        if (!trie[u].son[v]) trie[u].son[v] = ++cnt;
        u = trie[u].son[v];
    }
    trie[u].flag = num;  //变化1：标记为第num个出现的字符串
}
queue<int> q;
void getFail() {
    for (int i = 0; i < 26; i++) trie[0].son[i] = 1;
    q.push(1);
    trie[1].fail = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int Fail = trie[u].fail;
        for (int i = 0; i < 26; i++) {
            int v = trie[u].son[i];
            if (!v) {
                trie[u].son[i] = trie[Fail].son[i];
                continue;
            }
            trie[v].fail = trie[Fail].son[i];
            q.push(v);
        }
    }
}
void query(char* s) {
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int v = s[i] - 'a';
        int k = trie[u].son[v];
        while (k > 1) {
            if (trie[k].flag)
                vis[trie[k].flag]++;  //如果有模式串标记，更新出现次数
            k = trie[k].fail;
        }
        u = trie[u].son[v];
    }
}
void clear() {
    for (int i = 0; i <= cnt; i++) trie[i].clear();
    for (int i = 1; i <= n; i++) vis[i] = 0;
    cnt = 1;
    ans = 0;
}
int main() {
    while (1) {
        scanf("%d", &n);
        if (!n) break;
        clear();
        for (int i = 1; i <= n; i++) {
            scanf("%s", s[i]);
            insert(s[i], i);
        }
        scanf("%s", T);
        getFail();
        query(T);
        for (int i = 1; i <= n; i++) ans = max(vis[i], ans);  //最后统计答案
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)
            if (vis[i] == ans) printf("%s\n", s[i]);
    }
}


AC 自动机 topu 优化


#include <bits/stdc++.h>
#define maxn 2000001
using namespace std;
char s[maxn], T[maxn];
int n, cnt, vis[200051], ans, in[maxn], Map[maxn];
struct kkk {
    int son[26], fail, flag, ans;
} trie[maxn];
queue<int> q;
void insert(char* s, int num) {
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; ++i) {
        int v = s[i] - 'a';
        if (!trie[u].son[v]) trie[u].son[v] = ++cnt;
        u = trie[u].son[v];
    }
    if (!trie[u].flag) trie[u].flag = num;
    Map[num] = trie[u].flag;
}
void getFail() {
    for (int i = 0; i < 26; i++) trie[0].son[i] = 1;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int Fail = trie[u].fail;
        for (int i = 0; i < 26; ++i) {
            int v = trie[u].son[i];
            if (!v) {
                trie[u].son[i] = trie[Fail].son[i];
                continue;
            }
            trie[v].fail = trie[Fail].son[i];
            in[trie[v].fail]++;
            q.push(v);
        }
    }
}
void topu() {
    for (int i = 1; i <= cnt; ++i)
        if (in[i] == 0) q.push(i);  //将入度为0的点全部压入队列里
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[trie[u].flag] = trie[u].ans;  //如果有flag标记就更新vis数组
        int v = trie[u].fail;
        in[v]--;  //将唯一连出去的出边fail的入度减去（拓扑排序的操作）
        trie[v].ans += trie[u].ans;  //更新fail的ans值
        if (in[v] == 0) q.push(v);   //拓扑排序常规操作
    }
}
void query(char* s) {
    int u = 1, len = strlen(s);
    for (int i = 0; i < len; ++i) u = trie[u].son[s[i] - 'a'], trie[u].ans++;
}
int main() {
    scanf("%d", &n);
    cnt = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s);
        insert(s, i);
    }
    getFail();
    scanf("%s", T);
    query(T);
    topu();
    for (int i = 1; i <= n; ++i) printf("%d\n", vis[Map[i]]);
}


Trie 树


基本字符串查找


struct trie {
  int nex[100000][26], cnt = 0;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }
  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return false;
      p = nex[p][c];
    }
    return true;
  }
};


维护异或极值


const int N = 100010;

int head[N], nxt[N << 1], to[N << 1], weight[N << 1], cnt;
int n, dis[N], ch[N << 5][2], tot = 1, ans;

void insert(int x) {
    for (int i = 30, u = 1; i >= 0; --i) {
        int c = ((x >> i) & 1);
        if (!ch[u][c]) ch[u][c] = ++tot;
        u = ch[u][c];
    }
}
void get(int x) {
    int res = 0;
    for (int i = 30, u = 1; i >= 0; --i) {
        int c = ((x >> i) & 1);
        if (ch[u][c ^ 1]) {
            u = ch[u][c ^ 1];
            res |= (1 << i);
        } else
            u = ch[u][c];
    }
    ans = std::max(ans, res);
}
void add(int u, int v, int w) {
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    weight[cnt] = w;
}
void dfs(int u, int fa) {
    insert(dis[u]);
    get(dis[u]);
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dis[v] = dis[u] ^ weight[i];
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);

    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }

    dfs(1, 0);

    printf("%d", ans);

    return 0;
}


数学


判整除


    

  • 2: 末尾是2
    • 

  • 3: 所有位数和整除3
    • 

  • 4:

      

    • 个位0、4、8，十位偶数
      • 

    • 个位2、6，十位奇数
      • 

    

    • 



求行列式值


#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int maxn = 210;
LL a[maxn][maxn];
int n;
LL p;

LL det(int n, LL p) {
    LL ans = 1;
    bool flag;

    for (int i = 1; i <= n; i++) {
        if (!a[i][i]) {
            flag = 0;
            for (int j = i + 1; j <= n; j++)
                if (a[j][i]) {
                    flag = 1;
                    for (int k = i; k <= n; k++) swap(a[i][k], a[j][k]);
                    ans = -ans;
                    break;
                }
            if (!flag) return 0;
        }

        for (int j = i + 1; j <= n; j++) {
            while (a[j][i]) {
                LL t = a[i][i] / a[j][i];
                for (int k = i; k <= n; k++) {
                    a[i][k] -= t * a[j][k];
                    a[i][k] %= p;
                    swap(a[i][k], a[j][k]);
                }
                ans = -ans;
            }
        }
        ans *= a[i][i];
        ans %= p;
    }
    return (ans + p) % p;
}

int main() {
    while (scanf("%d%lld", &n, &p) == 2) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%lld", &a[i][j]);
                a[i][j] %= p;
            }
        }
        LL ans = det(n, p);
        printf("%lld\n", ans);
    }
    return 0;
}


快速傅里叶变换 (FFT)


const int MAXN = 1e7 + 10;
const double Pi = acos(-1.0);
struct Complex {
    double x, y;
    Complex(int _x, int _y) { x = _x, y = _y; }
    Complex(double _x = 0, double _y = 0) { x = _x, y = _y; }
    friend Complex operator+(const Complex &a, const Complex &b) {
        return ((Complex){a.x + b.x, a.y + b.y});
    }
    friend Complex operator-(const Complex &a, const Complex &b) {
        return ((Complex){a.x - b.x, a.y - b.y});
    }
    friend Complex operator*(const Complex &a, const Complex &b) {
        return ((Complex){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x});
    }
    friend Complex operator*(const Complex &a, const double &val) {
        return ((Complex){a.x * val, a.y * val});
    }
} f[MAXN], g[MAXN], p[MAXN];
int n, m, lim = 1, maxn, rev[MAXN], a[MAXN], b[MAXN];
inline void FFT(Complex *A, int opt) {
    for (int i = 0; i < lim; i++)
        if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
        Complex Wn = ((Complex){cos(Pi / (double)mid),
                                (double)opt * sin(Pi / (double)mid)});
        for (int j = 0; j < lim; j += (mid << 1)) {
            Complex W = ((Complex){1, 0});
            for (int k = 0; k < mid; k++, W = W * Wn) {
                Complex x = A[j + k], y = W * A[j + k + mid];
                A[j + k] = x + y;
                A[j + k + mid] = x - y;
            }
        }
    }
}
void init() {
    int l = 0;
    lim = 1;
    while (lim <= n + m) lim <<= 1, l++;
    rep(i, 0, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
}

int main() {
    cin >> n >> m;
    rep(i, 0, n) cin >> f[i].x;
    rep(i, 0, m) cin >> g[i].x;
    init();
    FFT(f, 1);
    FFT(g, 1);
    rep(i, 0, lim) f[i] = f[i] * g[i];
    FFT(f, -1);
    rep(i, 0, n + m) { cout << (int)(f[i].x / lim + 0.5) << " "; }

    return 0;
}


TODO: 快速傅立叶变换求 string 匹配


筛法


埃氏筛


复杂度 $O(n loglogn)$


int Eratosthenes(int n) {
  int p = 0;
  for (int i = 0; i <= n; ++i) is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;  // prime[p]是i,后置自增运算代表当前素数数量
      if ((long long)i * i <= n)
        for (int j = i * i; j <= n; j += i)
          // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
          // 的倍数开始，提高了运行速度
          is_prime[j] = 0;  // 是i的倍数的均不是素数
    }
  }
  return p;
}


Euler 筛


线性时间复杂度，因子筛不重复。欧拉筛可以顺便求出每个数字的因子个数。


const int MAXN = 1e8 + 10;
int divisions[MAXN]; // euler 筛还可以顺便算出每个数字的因子个数
int prime[MAXN];  //保存素数，注意下面的实现 prime 从 0 开始
bool vis[MAXN];   //初始化
int Prime(int n) {
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i < n; i++) {
        if (!vis[i]) prime[cnt++] = i, divisions[i] = 1;
        for (int j = 0; j < cnt && i * prime[j] < n; j++) {
            vis[i * prime[j]] = 1, divisions[i * prime[j]] = divisions[i] + 1;
            if (i % prime[j] == 0)  //关键
                break;
        }
    }
    return cnt;  //返回小于n的素数的个数
}


BSGS


long long bsgs(long long a, long long b, long long p) {  // bsgs
    map<long long, long long> hash;
    hash.clear();  //建立一个Hash表
    b %= p;
    long long t = sqrt(p) + 1;
    for (long long i = 0; i < t; ++i)
        hash[(long long)b * power(a, i, p) % p] =
            i;  //将每个j对应的值插入Hash表
    a = power(a, t, p);
    if (!a) return b == 0 ? 1 : -1;  //特判
    for (long long i = 1; i <= t; ++i) {  //在Hash表中查找是否有i对应的j值
        long long val = power(a, i, p);
        int j = hash.find(val) == hash.end() ? -1 : hash[val];
        if (j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;  //无解返回-1
}


欧拉函数


$\varphi(n)$，小于等于 $n$ 的、和 $n$ 互质的数的个数。$\varphi(p) = p - 1, \text{p is prime}$。积性函数：$\varphi(a \times b) = \varphi(a) \times \varphi(b), \text{when} \ gcd(a, b) = 1$。


一些有用的性质:


    

  • $\varphi(p^k) = p^k - p^{k-1}, \text{p is prime}$
    • 

  • 唯一分解定理可以得到 $n = \prod_{i=1}^s p_i^{k_i}$，于是有 $\varphi(n) = n \times \prod_{i=1}^s \frac{p_i - 1}{p_i}$。
    • 



int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}


（扩展）欧拉定理


$$a^b = \begin{cases}a^{b \mod \varphi(p)}, & gcd(a,p) = 1 \ a^b, & gcd(a,p) \neq 1, b < \varphi(p)  \ (\mod \ p) \ a ^{b \mod \varphi(p) + \varphi(p)}, & gcd(a,p) \neq 1, b \ge \varphi(p) \end{cases}$$


#include <cstdio>
int a, m, phi = 1;
int bm, flag;

int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (long long)b * b % m)
		if(e & 1) a = (long long)a * b % m;
	return a;
}
int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}


int main() {
	scanf("%d%d", &a, &m);
	a %= m;
	int mm = m;
    int phi =  euler_phi(m);
	char ch;
	while ((ch = getchar()) < '0' || ch > '9') ;
	while (bm = bm * 10ll + (ch ^ '0'), (ch = getchar()) >= '0' && ch <= '9')
		if (bm >= phi) flag = 1, bm %= phi;
	if (bm >= phi) flag = 1, bm %= phi;
	if (flag) bm += phi;
	printf("%d", qPow(a, bm));
	return 0;
}


快速幂


ll power(ll base, ll power, ll p) {
    ll result = 1;
    while (power > 0) {
        if (power & 1) {
            result = result * base % p;
        }
        power >>= 1;
        base = (base * base) % p;
    }
    return result;
}


龟速乘


快速幂可能被毒瘤卡 long long，用龟速乘，牺牲速度换取正确性


long long quick_mul(long long x,long long y,long long mod) 
{
	long long ans=0;
	while(y!=0){
		if(y&1==1)ans+=x,ans%=mod;
		x=x+x,x%=mod;
		y>>=1; 
	}
	return ans;
}

long long quick_pow(long long x,long long y,long long mod)
{
	long long sum=1;
    while(y!=0){
         if(y&1==1)sum=quick_mul(sum,x,mod),sum%=mod;
    	     x=quick_mul(x,x,mod),x%=mod;
         	 y=y>>1;
    }
    return sum;
}


快速乘 (FIXME)


09 集训队论文，速度 $O(1)$


LL mul(LL a, LL b, LL P){
    LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
    LL R = a * (b & ((1LL << 25) - 1)) % P;
    return (L + R) % P;
}


gcdlcd


ll gcd(ll a, ll b) {
    while (b ^= a ^= b ^= a %= b)
        ;
    return a;
}
ll lcd(ll a, ll b) { return a * b / gcd(a, b); }


Lucas 定理


算组合数，要求模数不太大，$1e5$


long long Lucas(long long n, long long m, long long p) {
  if (m == 0) return 1;
  return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}


中国剩余定理


LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % mod) % mod;
  }
  return (ans % mod + mod) % mod;
}


康拖展开


求一个排列在全排列字典序中第几个。公式 $\sum_{i=1}^n sum_{a_i} \times (n - i)!$，利用树状数组加速 $sum$ 计算，$sum$ 表示有多少个数比自己小。


#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int n;

ll tree[1000005];  //树状数组
int lowbit(int x) { return x & -x; }
void update(int x, int y) {
    while (x <= n) {
        tree[x] += y;
        x += lowbit(x);
    }
}
ll query(int x) {
    ll sum = 0;
    while (x) {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}

const ll wyx = 998244353;  //懒人专用
ll jc[1000005] = {1, 1};   //存阶乘的数组
int a[1000005];            //存数
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {  //预处理阶乘数组和树状数组
        jc[i] = (jc[i - 1] * i) % wyx;
        update(i, 1);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ans = (ans + ((query(a[i]) - 1) * jc[n - i]) % wyx) % wyx;  //计算ans
        update(a[i], -1);  //把a[i]变成0（原来是1，减1不就是0嘛）
    }
    printf("%lld", ans + 1);
    return 0;
}


乘法逆元


利用 Fermat 小定理用快速幂算 $a$ 的逆元，注意要求模数 $p$ 必须是素数。


ll x = power(a, p - 2, mod);


线性递推求逆元


inv[1] = 1;
for (int i = 2; i <= n; ++i) {
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}


高斯消元


float 方程组


#include <bits/stdc++.h>
using namespace std;
const int N = 105;
double a[N][N];
double x[N], eps = 1e-6;
int solve(int n, int m) {
    int c = 0;
    int r;
    for (r = 0; r < n && c < m; r++, c++) {
        int maxr = r;
        for (int i = r + 1; i < n; i++) {
            if (abs(a[i][c]) > abs(a[maxr][c])) maxr = i;
        }
        if (maxr != r) swap(a[r], a[maxr]);
        if (fabs(a[r][c]) < eps) {
            r--; // 当前列全部 0，处理当前行的下一列
            continue;
        }
        for (int i = r + 1; i < n; i++) {
            if (fabs(a[i][c]) > eps) {
                double k = a[i][c] / a[r][c];
                for (int j = c; j < m + 1; j++) a[i][j] -= a[r][j] * k;
                a[i][c] = 0;
            }
        }
    }
    for (int i = r; i < m; i++) {
        if (fabs(a[i][c]) > eps) return -1;  //无解
    }
    if (r < m) return m - r;  //返回自由元个数
    for (int i = m - 1; i >= 0; i--) {
        for (int j = i + 1; j < m; j++) a[i][m] -= a[i][j] * x[j];
        x[i] = a[i][m] / a[i][i];
    }
    return 0;  //有唯一解
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    int pan = solve(n, n);
    if (pan != 0) {
        cout << "No Solution";
        return 0;
    }
    for (int i = 0; i < n; i++) {
        printf("%.2lf\n", x[i]);
    }
}


异或方程组


#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N];
int x[N];
int solve(int n, int m) {
    int c = 0;
    int r;
    for (r = 0; r < n && c < m; r++, c++) {
        int maxr = r;
        for (int i = r + 1; i < n; i++) {
            if (abs(a[i][c]) > abs(a[maxr][c])) maxr = i;
        }
        if (maxr != r) swap(a[r], a[maxr]);
        if (a[r][c] == 0) {
            r--; 
            continue;
        }
        for (int i = r + 1; i < n; i++) {
            if (a[i][c] != 0) {
                for (int j = c; j < m + 1; j++) a[i][j] ^= a[r][j];
            }
        }
    }
    for (int i = r; i < m; i++) {
        if (a[i][c] != 0) return -1;  //无解
    }
    if (r < m) return m - r;  //返回自由元个数
    for (int i = m - 1; i >= 0; i--) {
        for (int j = i + 1; j < m; j++) x[i] ^= (a[i][j] && x[j]);
        x[i] = a[i][m];
    }
    return 0;  //有唯一解
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    int pan = solve(n, n);
    if (pan != 0) {
        cout << "No Solution";
        return 0;
    }
    //for (int i = 0; i < n; i++) {
        //printf("%.2lf\n", x[i]);
    //}
}


欧拉回路


奇数个点完全图递推求欧拉回路。


void dfs(int x, int y) {
    int cnt = 2;
    edges.push_back({1, x});
    while (cnt < x) {
        edges.push_back({x, cnt});
        edges.push_back({cnt, y});

        cnt++;
        edges.push_back({y, cnt});
        edges.push_back({cnt, x});

        cnt++;
    }
    edges.push_back({x, y});
    edges.push_back({y, 1});
}

for (int i = 1; i < n; i += 2) {
    dfs(i + 1, i + 2);
}



另一种 nb 的构造方法，旋转构造欧拉回路


void solve() {
	vector<int> euler(1, n-1);
	for(int i = 0; i < n/2; ++i) {
		int sgn = 1, ct = i;
		for(int d = 1; d < n; ++d) {
			euler.push_back(ct);
			ct = (ct + sgn*d + n-1) % (n-1);
			sgn *= -1;
		}
		euler.push_back(n-1);
	}
}


矩阵 (FIXME)


struct Matrix{ 
    static const int N=511,P=998244353;
    int n,a[N][2*N]; bool t;
    
    void In(ll a[][::N],int n) {
        this->n=n;
        rep(i,1,n+1) rep(j,1,n+1) this->a[i][j]=a[i][j], this->a[i][n+j]=0;
        rep(i,1,n+1) this->a[i][i+n]=1;
    }
    
    void Out(ll b[][::N]) {
        rep(i,1,n+1) rep(j,1,n+1) b[i][j]=a[i][n+j];
    }
    
    void Print() {
        if (t) printf("Inv Is:\n"); else { printf("Not Invertable!\n"); return; }
        rep(i,1,n+1) rep(j,1,n+1) printf("%d%c",a[i][n+j]," \n"[j==n]);
    }
    
    bool getinv(){
        rep(i,1,n+1){
            if(a[i][i]==0){
                rep(j,i,n+1) if(a[j][i]) swap(a[i],a[j]);
                if(!a[i][i]) return 0;
            }
            int s=a[i][i];
            rep(j,1,n+n+1) a[i][j]=1ll*a[i][j]*Pow(s,P-2)%P;
            rep(j,1,n+1) {
                if(i==j) continue;
                s=1ll*a[j][i]*Pow(a[i][i],P-2)%P;
                rep(k,1,n+n+1) a[j][k]=(a[j][k]-1ll*a[i][k]*s)%P;
            }
        }
        rep(i,1,n+1) rep(j,1,n+n+1) a[i][n+j]=(a[i][n+j]+P)%P;
        return 1;
    }
    
    bool Solve(ll a[][::N],int n,ll b[][::N]) {
        In(a,n),t=getinv(),Out(b); return t;
    }
    
    bool Check(ll a[][::N],ll b[][::N],int n) {
        static int c[::N][::N];
        memset(c,0,sizeof(c));
        rep(i,1,n+1) rep(k,1,n+1) if (a[i][k]) 
            rep(j,1,n+1) if (b[k][j]) c[i][j]+=a[i][k]*b[k][j]%P,c[i][j]%=P;
        rep(i,1,n+1) rep(j,1,n+1) c[i][j]=(c[i][j]+P)%P;
        rep(i,1,n+1) rep(j,1,n+1) if (c[i][j]!=(i==j)) return 0;
        return 1;
    }
}; 


矩阵快速幂


#include <bits/stdc++.h>
using namespace std;
const int Mod = 1000000007;
struct Matrix {
    long long c[101][101];
} A, I;
long long n, k;
Matrix operator*(const Matrix &x, const Matrix &y) {
    Matrix a;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a.c[i][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                a.c[i][j] += x.c[i][k] * y.c[k][j] % Mod;
                a.c[i][j] %= Mod;
            }
    return a;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> A.c[i][j];
    for (int i = 1; i <= n; i++) I.c[i][i] = 1;
    while (k > 0) {
        if (k % 2 == 1) I = I * A;
        A = A * A;
        k = k >> 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << I.c[i][j] << ' ';
        cout << endl;
    }
    return 0;
}


进制转换


借助十进制为媒介转换


int c[10000000];
void transform(int f, int t) { // from to
    int e;
    int sum = 0;
    string a;
    cin >> a;
    for (int x = 0; (int)x < a.size(); x++) {
        if (a[x] < 'A') {
            e = pow(f, (int)a.size() - x - 1);
            e *= (a[x] - '0');
            sum += e;
        } else {
            e = pow(f, (int)a.size() - x - 1);
            e *= (a[x] - 'A' + 10);
            sum += e;
        }
    }
    int g = 0;
    while (sum > 0) {
        c[g++] = sum % t;
        sum /= t;
    }
    for (int i = g - 1; i >= 0; i--) {
        if (c[i] >= 10) {
            printf("%c", c[i] + 'A' - 10);
        } else {
            printf("%d", c[i]);
        }
    }
}


数据结构


ST 表


$\Theta(nlogn)$ 预处理，$\Theta(1)$ 查询，不支持修改。


const int logn = 21;
const int maxn = 2000001;
int f[maxn][logn + 1], Logn[maxn + 1]; // f[i][j]: [i, i + 2^j - 1] 中最大值
void pre() {
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < maxn; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i][0] = read();
  pre();
  for (int j = 1; j <= logn; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    int s = Logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}


杂


求逆序对


用归并排序即可，树状数组/线段树也可以做


ll ans = 0;  // 逆序对数量
const int maxn = 6e5 + 5;
ll a[maxn], t[maxn];
void merge(ll b, ll e) {
    if (e == b) return;
    ll mid = b + ((e - b) >> 1);
    merge(b, mid);
    merge(mid + 1, e);
    ll i = b, j = mid + 1, s = b;
    while (i <= mid && j <= e)
        if (a[i] <= a[j])
            t[s++] = a[i++];
        else
            t[s++] = a[j++], ans += mid - i + 1;
    while (i <= mid) t[s++] = a[i++];
    while (j <= e) t[s++] = a[j++];
    for (ll l = b; l <= e; l++) a[l] = t[l];
}


悬线法


算最大子矩阵面积


int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      l[j] = r[j] = j;
    }
    char s[3];
    for (int j = 1; j <= m; j++) {
      scanf("%s", s);
      if (s[0] == 'F')
        a[j]++;
      else if (s[0] == 'R')
        a[j] = 0;
    }
    for (int j = 1; j <= m; j++)
      while (l[j] != 1 && a[l[j] - 1] >= a[j]) l[j] = l[l[j] - 1];
    for (int j = m; j >= 1; j--)
      while (r[j] != m && a[r[j] + 1] >= a[j]) r[j] = r[r[j] + 1];
    for (int j = 1; j <= m; j++) ans = std::max(ans, (r[j] - l[j] + 1) * a[j]);
  }
  printf("%d", ans * 3);
  return 0;
}


倍增


一个经典的倍增例子。


#include <cstdio>
using namespace std;

const int mod = 1000000007;

int modadd(int a, int b) {
    if (a + b >= mod) return a + b - mod;  // 减法代替取模，加快运算
    return a + b;
}
int vi[1000005];

int go[75][1000005];  // 将数组稍微开大以避免越界，小的一维尽量定义在前面
int sum[75][1000005];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", vi + i);
    }

    for (int i = 1; i <= n; ++i) {
        go[0][i] = (i + k) % n + 1;
        sum[0][i] = vi[i];
    }

    int logn = 31 - __builtin_clz(n);  // 一个快捷的取对数的方法
    for (int i = 1; i <= logn; ++i) {
        for (int j = 1; j <= n; ++j) {
            go[i][j] = go[i - 1][go[i - 1][j]];
            sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
        }
    }

    long long m;
    scanf("%lld", &m);

    int ans = 0;
    int curx = 1;
    for (int i = 0; m; ++i) {
        if (m & (1 << i)) {  // 参见位运算的相关内容，意为 m 的第 i 位是否为 1
            ans = modadd(ans, sum[i][curx]);
            curx = go[i][curx];
            m ^= 1ll << i;  // 将第 i 位置零
        }
    }

    printf("%d\n", ans);
}


摩尔投票法


$O(n)$ 求众数


def (nums):
    res = cnt = 0
    for num in nums:
        if cnt == 0:
            res = num
            cnt += 1
        elif res == num:
            cnt += 1
        else:
            cnt -= 1
    return res


离散化


int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dis[i] = a[i];
    sort(dis + 1, dis + n + 1);
    int num = unique(dis + 1, dis + n + 1) - dis - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(dis + 1, dis + num + 1, a[i]) - dis;
    for (int i = 1; i <= n; i++) printf("%d ", dis[a[i]]);
    return 0;
}



快速选择


借助快排的思想，$O(logn)$ 选出数列第 k 大（小）的元素


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

int partition(int arr[], int l, int r) {
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

int kthSmallest(int arr[], int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int index = partition(arr, l, r);

        if (index - l == k - 1) return arr[index];
        if (index - l > k - 1) return kthSmallest(arr, l, index - 1, k);

        return kthSmallest(arr, index + 1, r, k - index + l - 1);
    }

    return INT_MAX;
}

// Driver program to test above methods
int main() {
    int arr[] = {10, 4, 5, 8, 6, 11, 26};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "K-th smallest element is " << kthSmallest(arr, 0, n - 1, k);
    return 0;
}


计算几何


计算几何通用头


900 行的大模板在 ./geometry 里面，下面的已经被淘汰。


namespace geometry {

struct Vector {
    double x, y;
    Vector(double xx = 0, double yy = 0) : x(xx), y(yy) {}
};
typedef Vector Point;
const double epsilon = 1e-10;

Vector operator+(Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator-(Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator*(Vector a, double p) { return Vector(a.x * p, a.y * p); }
Vector operator/(Vector a, double p) { return Vector(a.x / p, a.y / p); }

bool operator<(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int dcmp(double x) {
    if (fabs(x) < epsilon)
        return 0;
    else
        return x < 0 ? -1 : 1;
}
bool operator==(const Point &a, const Point &b) {
    return (!dcmp(a.x - b.x)) && (!dcmp(a.y - b.y));
}

double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double length(Vector a)  // Vector
{
    return sqrt(dot(a, a));
}
double angle(Vector a, Vector b) {
    return acos(dot(a, b) / length(a) / length(b));
}

double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double area_2(Point a, Point b, Point c) { return cross(b - a, c - a); }
double length(Point a, Point b)  // 2 points
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Vector rotate(Vector a, double rad) {
    return Vector(a.x * cos(rad) - a.y * sin(rad),
                  a.x * sin(rad) + a.y * cos(rad));
}
Vector normal(Vector a) {
    double l = length(a);
    return Vector(-a.y / l, a.x / l);
}
}  // namespace geometry


扫描线 (TODO)


凸包


算凸包周长


#include <bits/stdc++.h>
using namespace std;
int n;
struct vec {
    double x, y;
    vec(double xx = 0, double yy = 0) : x(xx), y(yy) {}
    vec operator-(const vec &a) { return vec(x - a.x, y - a.y); }
} p[100010], sta[100010];
int top;
double K(vec a) { return atan2(a.y, a.x); }
double dis(vec a, vec b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(vec a, vec b) {
    double t = K(a - p[1]) - K(b - p[1]);
    if (t)
        return t < 0;
    else
        return dis(p[1], a) < dis(p[1], b);
}
double cp(vec a, vec b) { return a.x * b.y - a.y * b.x; }
double ans;
int main() {
    scanf("%d", &n);
    if (n == 1) return putchar('0'), 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if (p[1].y > p[i].y)
            swap(p[1], p[i]);
        else if (p[1].y == p[i].y && p[1].x > p[i].x)
            swap(p[1], p[i]);
    }
    sort(p + 2, p + n + 1, cmp);
    sta[1] = p[1];
    sta[top = 2] = p[2];
    for (int i = 3; i <= n; ++i) {
        while (top >= 2 &&
               cp(p[i] - sta[top - 1], sta[top] - sta[top - 1]) >= 0)
            --top;
        sta[++top] = p[i];
    }
    sta[++top] = p[1];
    for (int i = 1; i < top; ++i) ans += sqrt(dis(sta[i], sta[i + 1]));
    printf("%.2f", ans);
}


求直线交点


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double eps = 1e-10;

inline int sign(const double &x)
{
	if(x>eps) return 1;
	if(x<-eps) return -1;
	return 0;
}
struct Point
{
	double x,y;
		Point(double _x=0,double _y=0):x(_x),y(_y) {	}
		Point operator -(const Point &op2) const {
		return Point(x-op2.x,y-op2.y);
	}
		double operator ^(const Point &op2) const {
		return x*op2.y-y*op2.x;
	}
};
inline double sqr(const double &x) {
	return x*x;
}
inline double mul(const Point &p0,const Point &p1,const Point &p2) {
	return (p1-p0) ^ (p2-p0);
}
inline double dis2(const Point &p0,const Point &p1) {
	return sqr(p0.x-p1.x)+sqr(p0.y-p1.y);
}
inline double dis(const Point &p0,const Point &p1) {
	return sqrt(dis2(p0,p1));
}
inline int cross(const Point &p1,const Point &p2,const Point &p3,const Point &p4,Point &p) {
	double a1 = mul(p1,p2,p3),a2 = mul(p1,p2,p4);
	if(sign(a1)==0 && sign(a2)==0) return 2;
	if(sign(a1-a2)==0) return 0;
	p.x = (a2*p3.x-a1*p4.x) /(a2-a1);
	p.y = (a2*p3.y-a1*p4.y) /(a2-a1);
	return 1;
}
Point p1,p2,p3,p4,p;
Point e[1005], ans[1005];
bool cmp(Point a, Point b) {
	return dis(a, p1) < dis(b, p1);
}
int main()
{
	int n, m, id = 0;
	cin >> n >> m;
	cin >> p1.x >> p1.y >> p2.x >> p2.y;
	for (int i = 1; i <= n; i++) {
		cin >> e[i].x >> e[i].y;
	}
	for (int op = 1; op <= m; op++) {
		int h, k;
		id = 0;
		cin >> h >> k;
		p3.x = e[h].x;
		p3.y = e[h].y;
		for (int i = 1; i <= n; i++) {
			if (i == h) continue;
			p4.x = e[i].x;
			p4.y = e[i].y;
			int flag = cross(p1,p2,p3,p4,p);
			if (flag == 0 || flag == 2) continue;
			else {
				if (p.x < p1.x && p.x < p2.x) continue;
				if (p.y < p1.y && p.y < p2.y) continue;
				if (p.x > p1.x && p.x > p2.x) continue;
				if (p.y > p1.y && p.y > p2.y) continue;
				ans[++id].x = p.x;
				ans[id].y = p.y;
			}
		}
		sort(ans+1, ans+1+id, cmp);
		if (id < k) cout << -1 << endl;
		else {
			printf("%.6lf %.6lf\n", ans[k].x, ans[k].y);
		}
	}
	return 0;
}


C++ 相关


位运算


    

  • int __builtin_ffs (unsigned int x): 返回x的最后一位1的是从后向前第几位，比如7368（1110011001000）返回4。
    • 

  • int __builtin_clz (unsigned int x): 返回前导的0的个数。
    • 

  • int __builtin_ctz (unsigned int x): 返回后面的0个个数，和__builtin_clz相对。
    • 

  • int __builtin_popcount (unsigned int x): 返回二进制表示中1的个数。
    • 

  • int __builtin_parity (unsigned int x): 返回x的奇偶校验位，也就是x的1的个数模2的
    • 



STL


bitset


Constructor


    

  • std::bitset<8> b1;： 默认全 0
    • 

  • std::bitset<8> b2(42);：unsigned long long init
    • 



template< class CharT, class Traits, class Alloc >
explicit bitset( const std::basic_string<CharT,Traits,Alloc>& str,
                 typename std::basic_string<CharT,Traits,Alloc>::size_type
                     pos = 0,
                 typename std::basic_string<CharT,Traits,Alloc>::size_type
                     n = std::basic_string<CharT,Traits,Alloc>::npos,
                 CharT zero = CharT('0'),
                 CharT one = CharT('1'));


    

  • 

    std::bitset<8> b7("XXXXYYYY", 8, 'X', 'Y'): string init, custom size, pos and 01 chars
    

    • 

  • 

    constexpr bool operator[]( std::size_t pos ) const;：选择某位，注意位是从低位到高位的
    

    • 

  • 

    bool all() const noexcept;: all 1
    

    • 

  • 

    bool any() const noexcept;: any 1
    

    • 

  • 

    bool none() const noexcept;: none 1
    

    • 

  • 

    std::size_t count() const noexcept;: 多少个 1
    

    • 

  • 

    bool test(std::size_t pos) const;: 返回 pos 位的值，比 [] 多边界检查
    

    • 



Capacity


    

  • constexpr std::size_t size() const noexcept;: 大小，即初始化模板里的参数
    • 



Modifiers


    

  • bitset& set( std::size_t pos, bool value = true );: 直接使用 b.set() 全设为 1，否则按参数处理
    • 

  • bitset& reset( std::size_t pos );: set bit to false
    • 

  • bitset& flip( std::size_t pos ): true to false, false to true, 直接使用全部反转
    • 



Convertions


template<
    class CharT = char,
    class Traits = std::char_traits<CharT>,
    class Allocator = std::allocator<CharT>
> std::basic_string<CharT,Traits,Allocator>
    to_string(CharT zero = CharT('0'), CharT one = CharT('1')) const;


    

  • to_string: b.to_string('0', 'X')
    • 

  • to_ulong: unsigned long to_ulong() const
    • 

  • to_ullong: unsigned long long to_ullong() const
    • 



set


Modifiers


    

  • insert: std::pair<iterator,bool> insert( value_type&& value );: 插入
    • 

  • clear: void clear() noexcept;: 清除 set
    • 

  • erase: iterator erase( const_iterator pos );: 删除元素
    • 



Capacity


    

  • empty: bool empty() const noexcept;: 是否没有元素
    • 

  • size: size_type size() const noexcept;: 返回元素数量
    • 



Lookup


    

  • find: const_iterator find( const Key& key ) const;: 查找元素
    • 

  • count: size_type count( const Key& key ) const: 查找元素数量，只会返回 0 或 1
    • 

  • 



priority_queue


    

  • 自定义 cmp 函数
    • 



struct node {
    int i, j, num, f;
};  
struct cmp1 {
    bool operator()(node x, node y) { return x.num > y.num; }
};                                           
priority_queue<node, vector<node>, cmp1> q;  


vector


    

  • constexpr void assign( size_type count, const T& value );: 替换 vector 中元素
    • 



STL Algorithms


std::lower_bound


template< class ForwardIt, class T, class Compare >
constexpr ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );


    

  • [first, last) 中找第一个不小于 (not less than) value 的元素。
    • 

  • comp: binary predicate which returns true fi the first argument is less than (ordered before) the second
    • 



std::upper_bound


template< class ForwardIt, class T, class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );


    

  • Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.
    • 



std::binary_search


template< class ForwardIt, class T >
constexpr bool binary_search( ForwardIt first, ForwardIt last, const T& value );


    

  • 二分搜索判断一个值存不存在，返回 1 或者 0。注意需要先 sort！
    • 



std::accumulate


template< class InputIt, class T >
constexpr T accumulate( InputIt first, InputIt last, T init );


    

  • 计算 $[first, last)$ 的和
    • 



C++ USK


sort with lambda


sort(a, a + 4, [](int a, int b) { return a > b; });


注意！




十年OI一场空，不开long long见祖宗




一下常见错误：


    

  • 没用 long long 或者 double 数据溢出
    • 

  • mod 过程中数据溢出、没有用逆元计算、每一步都需要 mod，否则很有可能算法正确但是 mod 中间出错
    • 

  • 题意读错，漏掉细节，看清楚到底要求什么、题目的一些细小限制
    • 

  • 忘了重置相关数组和变量
    • 



References



   



      


  
      

      

        

          

            

  
About


      

        祖传模板++
      



    
Resources

    

      
        
        Readme
    


  



  
  

  

    
      
      Activity
  


    

      
        
        Custom properties
    


  
Stars

  

    
      
      0
      stars
  


  
Watchers

  

    
      
      2
      watching
  


  
Forks

  

    
      
      0
      forks
  


    

      
          Report repository
    




          

        


        
            

              

                

  
    Releases
      1



  
    
    

      

        100 发了庆祝一下🙌🏻
        
          Latest
      

      
Sep 25, 2021

    


              

            


        
        
            

              

                
  

  
    Packages
      




      

        No packages published