模板汇总

也许是中学生涯最后一次打板子了呀...

---

KMP模式匹配

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000005;
char a[N], b[N];
int a1, b1, Next[N];
int main(){
    cin >> a + 1;
    cin >> b + 1;
    a1 = strlen(a + 1);
    b1 = strlen(b + 1);
    Next[1] = 0;
    for(int i = 2, j = 0; i <= b1; i++){
        while( j > 0 && b[j + 1] != b[i] ) j = Next[j];
        if( b[i] == b[j + 1] ) j++;
        Next[i] = j;
    }
    for(int i = 1, j = 0; i <= a1; i++){
        while( j > 0 && a[i] != b[j + 1]) j = Next[j];
        if(a[i] == b[j + 1]) j++;
        if(j == b1) {
            cout << i - j + 1 <<"\n";
            j = Next[j];
        }
    }
    for(int i = 1; i <= b1; i++) cout << Next[i] <<" ";
    return 0;
} 

---

Trie字典树

#include<iostream>
#include<cstdio>
using namespace std;
int Trie[N][27], end[p] = 1, tot = 1;
void insert(char* str){
    int len = strlen(str), p = 1;
    for(int k = 0; k < len; k++){
        int ch = str[k] - 'a';
        if(trie[p][ch] == 0) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    end[p] = 1;
}
bool search(char* str){
    int len = strlen(str), p = 1;
    for(int k = 0; k < len; k++){
        p = trie[p][str[k]];
        if(p == 0) return 0;
    }
    return end[p];
}

---

ST表

值得注意的是，log函数最好配强制类型转换（不然poj会编译错误），转换的时候要用括号把log全部括一下，初始化的时候k要加一。初始化的时候j从0开始，

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 100005;
int a[N][30], n, m, k;
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) a[i][0] = read();
    k = int(log(n) / log(2) + 1);
    for(int i = 1; i <= k; i++)
        for(int j = 0; j <= n - (1 << i) + 1; j++)
            a[j][i] = max(a[j][i - 1], a[j + (1 << (i-1))][i - 1]);
    while(m--){
        int x = read(), y = read();
        k = int(log(y - x + 1) / log(2));
        cout << max(a[x][k], a[y - (1 << k) + 1][k]) << "\n";
    }
    return 0;
}

---

单源最短路径 \(dijkstra\)

注意打标记和判重都在取出队头的时候进行

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 500005;
int ver[N], head[N], Next[N], edge[N], tot;
int n, m, s;
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z;
    Next[tot] = head[x], head[x] = tot;
}
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}

/*Dijkstra*/
int d[N], v[N];
void dijkstra(int s){
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    priority_queue< pair< int, int > > q;
    q.push(make_pair(0, s)); d[s] = 0;
    while(q.size()){
        int x = q.top().second; q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push(make_pair(-d[y], y));
            }
        }
    }
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++){
        int x = read(), y = read(), z = read();
        add(x, y, z);
    }
    dijkstra(s);
    for(int i = 1; i <= n; i++){
        if(d[i] == 0x3f3f3f3f)
            cout << "2147483647 ";
        else cout << d[i] <<" ";
    }
    return 0;
}

---

单源最短路径\(SPFA\)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 500005;
int ver[N], head[N], Next[N], edge[N], tot;
int n, m, s;
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z;
    Next[tot] = head[x], head[x] = tot;
}
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int d[N], v[N];
/* spfa */
void spfa(int s){
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    queue<int> q;
    q.push(s); v[s] = 1; d[s] = 0;
    while(q.size()){
        int x = q.front(); q.pop();
        v[x] = 0;
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                if(!v[x]) q.push(y), v[y] = 1;
            }
        }
    }
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1; i <= m; i++){
        int x = read(), y = read(), z = read();
        add(x, y, z);
    }
    spfa(s);
    for(int i = 1; i <= n; i++){
        if(d[i] == 0x3f3f3f3f)
            cout << "2147483647 ";
        else cout << d[i] <<" ";
    }
    return 0;
}

---

扩展欧几里得

\(x = \frac{c}{d}x_0 + k \frac{b}{d}, y = \frac {c}{d}y_0 - k \frac{a}{d}\)

#include<iostream>
#define ll long long
using namespace std;
int exgcd1(int a, int b, int &x, int &y){
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd1(b, a % b, x, y);
    int z = x; x = y, y = z - (a / b) * y;
    return d;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x; x = y, y = z - (a / b) * y;
    return d;
}
int main(){
    ll a, b, x, y, d;
    cin >> a >> b;
    d = exgcd(a, b, x, y);
    cout << (x % (b / d) + (b / d)) % (b / d) <<"\n";
    return 0;
}

---

最近公共祖先 LCA

• 树上倍增法
  敲这个板子出了一堆错误。所以要记得空间开到两倍，lca的大于等于号。
  

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1000005;
int ver[N], head[N], Next[N], tot;
int n, m, s, k, f[N][25], d[N];
void add(int x, int y){
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void bfs(){
    queue<int> q;
    q.push(s); d[s] = 1;
    while(q.size()){
        int x = q.front(); q.pop();
        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i];
            if(d[y]) continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1; j <= k; j++)
                f[y][j] = f[f[y][j - 1]][j - 1];
            q.push(y);
        }
    }
}
int lca(int x, int y){
    if(d[y] < d[x]) swap(x, y);
    for(int i = k; i >= 0; i--)
        if(d[f[y][i]] >= d[x]) y = f[y][i];
    if(x == y) return x;
    for(int i = k; i >= 0; i--)
        if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main(){
    cin >> n >> m >> s;
    k = (int)( log(n) / log(2) ) + 1;
    for(int i = 1; i < n; i++) {
        int x = read(), y = read();
        add(x, y), add(y, x);
    }
    bfs();
    while(m--){
        int x = read(), y = read();
        cout << lca(x, y) <<"\n";
    }

    return 0;
}

---

• 树链剖分法

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1000005;
int ver[N], head[N], Next[N], tot;
int d[N], son[N], f[N], top[N], v[N], size[N];
int n, m, s;
void add(int x, int y){
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void dfs1(int x){
    v[x] = 1;
    size[x] = 1;
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i];
        if(v[y]) continue;
        d[y] = d[x] + 1;
        dfs1(y);
        f[y] = x;
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])
            son[x] = y;
    }
}
void dfs2(int x, int p){
    top[x] = p;
    if(son[x]) dfs2(son[x], p);
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i];
        if(y == f[x] || y == son[x]) continue;
        dfs2(y, y);
    }
}
int lca(int x, int y){
    while(top[x] != top[y])
        if(d[top[x]] > d[top[y]]) x = f[top[x]];
        else y = f[top[y]];
    if(d[x] > d[y]) return y;
    return x;
}
int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++) {
        int x = read(), y = read();
        add(x, y), add(y, x);
    }
    d[s] = 1;
    dfs1(s);
    dfs2(s, s);
    while(m--){
        int x = read(), y = read();
        cout << lca(x, y) <<"\n";
    }
    return 0;
}

---

最小生成树 Kruskal

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 200005;
int n, m, f[N], ans = 0;
struct node{
    int x, y, z;
}edge[N];
bool cmp(node a, node b){
    return a.z < b.z;
}
int get(int x){
    if(x == f[x]) return x;
    return f[x] = get(f[x]);
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= m; i++){
        cin >> edge[i].x >> edge[i].y >> edge[i].z;
    }
    sort(edge + 1, edge + m + 1, cmp);
    for(int i = 1; i <= m; i++){
        int x = edge[i].x, y = edge[i].y;
        x = get(x), y = get(y);
        if(x == y) continue;
        f[x] = y;
        ans += edge[i].z;
    }
    cout << ans;
    return 0;
}

---

树的直径

void dp(int x){
    v[x] = 1;
    for(int i = head[x]; i; i = Next[i]){
        int y = ver[i];
        if(v[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
}

---

树状数组

OI生涯学的第一个数据结构！
板子超好写，难在分析题目中能用前缀和、差分解决的地方。

void update(int x, int y){
    for(; x <= n; x += x & -x)
        s[x] += y;
}
int getsum(int x){
    int ans = 0;
    for(; x; x -= x & -x)
        ans += s[x];
    return ans;
}

---

归并排序

\(mid - i + 1\)

#include<iostream>
using namespace std;
int a[100005], b[100005], ans;
void merge_sort(int l, int r){
    if(l == r) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid || j <= r){
        if(j > r || ( a[i] <= a[j] && i <= mid ))
            b[k++] = a[i++];
        else
            b[k++] = a[j++], ans += mid - i + 1;
    }
    for(int i = l; i <= r; i++)
        a[i] = b[i];
}
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(1, n);
    cout << ans;
    return 0;
}

---

乘法逆元

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3000005;
long long a[N], n, p;
int main(){
    cin >> n >> p;
    a[0] = a[1] = 1;
    cout << 1 <<"\n";
    for(int i = 2; i <= n; i++){
        a[i] = (p - p / i) * a[p % i] % p;
        cout << a[i] <<"\n";
    }

    return 0;
}

---

卢卡斯定理

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1000005;
long long a[N];
long long n, m, p;

long long fp(long long a, long long b){
    long long ans = 1;
    for(; b; b >>= 1){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
    }

    return ans;
}


long long C(long long n, long long m){
    if(n < m) return 0;
    return (a[n] * fp(a[m], p - 2)) % p * fp(a[n - m], p - 2) % p ;
}
long long Lucas(long long n, long long m){
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

int read(){
    int x = 0, ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x;
}



int main(){
//  for(int i = 2; i < p; i++) a[i] = (p - p / i) * a[p % i] % p;

    int t = read();
    while(t--){
        n = read(), m = read(), p = read();
        a[0] = 1;
        for(int i = 1; i <= p; i++) a[i] = a[i - 1] * i % p;
        cout << Lucas(n + m, n) <<"\n";
    }


    return 0;
}

---

线段树

一个暑假的记忆，大概是我最有把握的模板了吧。

#include<iostream>
#include<cstdio>
using namespace std;
const int SIZE = 100005;
struct SegmentTree{
    int l, r;
    long long sum, add;
}t[SIZE * 4];
int a[SIZE];
void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r) {
        t[p].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(p*2, l, mid);
    build(p*2+1, mid + 1, r);
    t[p].sum = t[p*2].sum + t[p*2+1].sum;
}
void spread(int p){
    if(t[p].add){
        t[p*2].sum += (long long)(t[p*2].r - t[p*2].l + 1) * t[p].add;
        t[p*2+1].sum += (long long)(t[p*2+1].r - t[p*2+1].l + 1) * t[p].add;
        t[p*2].add += t[p].add;
        t[p*2+1].add += t[p].add;
        t[p].add = 0;
    }
}
void change(int p, int l, int r, int val){
    if(l <= t[p].l && r >= t[p].r){
        t[p].add += val;
        t[p].sum += (long long)(t[p].r - t[p].l + 1) * val;
        return;
    }
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if(l <= mid) change(p*2, l, r, val);
    if(r > mid) change(p*2+1, l, r, val);
    t[p].sum = t[p*2].sum + t[p*2+1].sum;
}
long long ask(int p, int l, int r){
    if(l <= t[p].l && r >= t[p].r) return t[p].sum;
    spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    long long val = 0;
    if(l <= mid) val += ask(p*2, l, r);
    if(r > mid) val += ask(p*2+1, l, r);
    return val;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--){
        int f, x, y, h;
        cin >> f >> x>> y;
        if(f == 1){
            cin >> h;
            change(1, x, y, h);
        }
        if(f == 2){
            cout << ask(1, x, y) <<"\n";
        }
    }
    return 0;
}

---

并查集

板子不重要，路径压缩和带权才重要

int get(int x){
    if(x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y){
    fa[get(x)] = get(y);
}

---

平衡树Treap

#include<iostream>
#include<cstdlib>
using namespace std;
const int SIZE = 100005;
struct Treap{
    int l, r;
    int val, dat;
    int size, cnt;
}a[SIZE];
int tot, root, n, INF=0x7fffffff;

int New(int val){
    a[++tot].val = val;
    a[tot].dat = rand();
    a[tot].size = a[tot].cnt = 1;
    return tot;
}

void Update(int p){
    a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
}

void Build(){
    New(-INF), New(INF);
    root = 1, a[1].r = 2;
    Update(root);
}

void zig(int &p){
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p, p = q;
    Update(a[p].r), Update(p);
}

void zag(int &p){
    int q = a[p].r;
    a[p].r = a[q].l, a[q].l = p, p = q;
    Update(a[p].l), Update(p);
}

void Insert(int &p, int val){
    if(p == 0){
        p = New(val);
        return;
    }
    if(a[p].val == val){
        a[p].cnt++, Update(p);
        return;
    }
    if(val < a[p].val){
        Insert(a[p].l, val);
        if(a[p].dat < a[a[p].l].dat) zig(p);
    }
    else{
        Insert(a[p].r, val);
        if(a[p].dat < a[a[p].r].dat) zag(p);
    }
    Update(p);
}

int GetRankByVal(int p, int val){
    if(p == 0) return 0;
    if(val == a[p].val) return a[a[p].l].size;
    if(val < a[p].val) return GetRankByVal(a[p].l, val);
    return a[a[p].l].size + a[p].cnt + GetRankByVal(a[p].r, val);
}

int GetValByRank(int p, int rank){
    if(p == 0) return INF;
    if(a[a[p].l].size >= rank) return GetValByRank(a[p].l, rank);
    if(a[a[p].l].size + a[p].cnt >= rank) return a[p].val;
    return GetValByRank(a[p].r, rank - a[a[p].l].size - a[p].cnt);
}

int GetPrev(int val){
    int ans = 1;
    int p = root;
    while(p){
        if(val == a[p].val){
            if(a[p].l > 0){
                p = a[p].l;
                while(a[p].r > 0) p = a[p].r;
                ans = p;
            }
            break;
        }
        if(a[ans].val < a[p].val && a[p].val < val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}
int GetNext(int val){
    int ans = 2;
    int p = root;
    while(p){
        if(val == a[p].val){
            if(a[p].r > 0){
                p = a[p].r;
                while(a[p].l > 0) p = a[p].l;
                ans = p;
            }
            break;
        }
        if(a[ans].val > a[p].val && a[p].val > val) ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return a[ans].val;
}

void Remove(int &p, int val){
    if(p == 0) return;
    if(val == a[p].val){
        if(a[p].cnt > 1){
            a[p].cnt--, Update(p);
            return;
        }
        if(a[p].l || a[p].r){
            if(a[p].r == 0 && a[a[p].l].dat > a[a[p].r].dat)
                zig(p), Remove(a[p].r, val);
            else
                zag(p), Remove(a[p].l, val);
            Update(p);
        }else p = 0;
        return;
    }
    val < a[p].val ? Remove(a[p].l, val) : Remove(a[p].r, val);
    Update(p);
}
int main(){
    Build();
    cin >> n;
    while(n--){
        int opt, x;
        cin >> opt >> x;
        switch(opt){
            case 1:
                Insert(root, x);
                break;
            case 2:
                Remove(root, x);
                break;
            case 3:
                cout << GetRankByVal(root, x) - 1 <<"\n";
                break;
            case 4:
                cout << GetValByRank(root, x+1) <<"\n";
                break;
            case 5:
                cout << GetPrev(x) <<"\n";
                break;
            case 6:
                cout << GetNext(x) <<"\n";
                break;
        }
    }
    return 0;
}

---

平衡树Splay

#include<iostream>
using namespace std;

const int _ = 100005;
const int INF = 0x7fffffff;

int n, opt, x;

struct Spaly{
    int root, tot, cnt[_], val[_], size[_], ch[_][2], fa[_];

    bool chk(int x){
        return ch[fa[x]][1] == x;
    }

    void pushup(int x){
        if(!x) return;
        size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
    }

    int newnode(int x){
        val[++tot] = x;
        cnt[tot] = size[tot] = 1;
        ch[x][0] = ch[x][1] = 0;
        return tot;
    }

    void rotate(int x){
        int y = fa[x], z = fa[y], k = chk(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][chk(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        pushup(y), pushup(x);
    }

    void splay(int x, int goal = 0){
        while(fa[x] != goal){
            int y = fa[x], z = fa[y];
            if(z != goal){
                if(chk(x) == chk(y)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        if(!goal) root = x;
    }

    void insert(int x){
        int cur = root, p = 0;
        while(cur && x != val[cur])
            p = cur, cur = ch[cur][x > val[cur]];
        if(cur) ++cnt[cur], splay(cur);
        else cur = ch[p][x > val[p]] = newnode(x), fa[cur] = p, splay(cur);
    }

    void find(int x){
        if(!root) return;
        int cur = root;
        while(ch[cur][x > val[cur]] && x != val[cur]) cur = ch[cur][x > val[cur]];
        splay(cur);
    }

    int rank(int x){
        find(x);
        return cnt[ch[root][0]] + 1;
    }

    int kth(int k){
        int cur = root;
        while(1){
            if(ch[cur][0] && k <= size[ch[cur][0]]) cur = ch[cur][0];
            else if(k > size[ch[cur][0]] + cnt[cur]) k -= size[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }

    int pre(int x){
        find(x);
        if(val[root] < x) return root;
        int cur = ch[root][0];
        while(ch[cur][1]) cur = ch[cur][1];
        return cur;
    }

    int next(int x){
        find(x);
        if(val[root] > x) return root;
        int cur = ch[root][1];
        while(ch[cur][0]) cur = ch[cur][0];
        return cur;
    }

    void remove(int x){
        int u = pre(x), v = next(x);
        splay(u), splay(v, u);
        int w = ch[v][0];
        if(cnt[w] > 1) --cnt[w], splay(w);
        else size[0] = cnt[0] = ch[v][0] = 0;
    }

    void maintain(int x){
        if(!ch[x][0] && !ch[x][1]) size[x] = cnt[x];
        if(ch[x][0]) maintain(ch[x][0]);
        if(ch[x][1]) maintain(ch[x][1]);
        pushup(x);
    }

}T;

int main(){
    T.insert(-INF), T.insert(INF);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> opt >> x;
        if(opt == 1) T.insert(x);
        if(opt == 2) T.remove(x);
        if(opt == 3) cout << T.rank(x) - 1 <<"\n";
        if(opt == 4) cout << T.val[T.kth(x)+1] <<"\n";
        if(opt == 5) cout << T.val[T.pre(x)] <<"\n";
        if(opt == 6) cout << T.val[T.next(x)] <<"\n";
    }

    return 0;
}