一些模板

$数位DP$

#include <bits/stdc++.h>
using namespace std;
long long l , r , x;
long long dp[20][2];
int n;
long long dgt[20100];
long long dfs(int i , int o){
	if(i == 0) return 1;
	if(~dp[i][o]) return dp[i][o];
	long long ret = 0;
	int k = (o? dgt[i] : 9);
	for(int d = 0 ; d <= k ; d++){
		if(d == x) continue;
		ret += dfs(i - 1 , o && d == k);
	}
	return (dp[i][o] = ret);
}
long long solve(long long a){
	n = 0;
	while(a){
		dgt[++n] = a % 10;
		a /= 10;
	}
	memset(dp , -1 , sizeof(dp));
	return dfs(n , 1);
}
int main(){
	cin >> l >> r >> x;
	cout << solve(r) - solve(l - 1);
	return 0;
}

$线段树$

#include <iostream>
#define int long long

using namespace std;
long long a[10010000] , b[10010000] , d[19919999] , n , q;
void build(int s, int t, int p) {
	if (s == t) {
		d[p] = a[s];
		return;
	}
	int m = s + ((t - s) >> 1);
	build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[(p * 2) + 1];
}
void update(int l, int r, int c, int s, int t, int p) {
	if (l <= s && t <= r) {
		d[p] += (t - s + 1) * c, b[p] += c;
		return;
	}
	int m = s + ((t - s) >> 1);
	if (b[p] && s != t) {
		d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
		b[p * 2] += b[p], b[p * 2 + 1] += b[p];  
		b[p] = 0;                              
	}
	if (l <= m) update(l, r, c, s, m, p * 2);
	if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
	d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
	if (l <= s && t <= r) return d[p];
	int m = s + ((t - s) >> 1);
	if (b[p]) {
		d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
		b[p * 2] += b[p], b[p * 2 + 1] += b[p]; 
		b[p] = 0;                             
	}
	int sum = 0;
	if (l <= m) sum = getsum(l, r, s, m, p * 2);
	if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
	return sum;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1 ; i <= n; i++){
		cin >> a[i];
	}
	build(1 , n , 1);
	while(q--){
		int f;
		cin >> f;
		if(f == 1){
			int l , r , x;
			cin >> l >> r >> x;
			update(l , r , x , 1 , n , 1);
		}
		else{
			int l , r;
			cin >> l >> r;
			cout << getsum(l , r , 1 , n , 1)<< endl;
		}
	}
	return 0;
}

$平衡树$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
int psz;
long long key[maxn], pri[maxn], sz[maxn], lc[maxn], rc[maxn];

int node(int x) {
	int u = ++psz;
	key[u] = x;
	pri[u] = rand();
	sz[u] = 1;
	lc[u] = rc[u] = 0;
	return u;
}

void maintain(int u) {
	sz[u] = sz[lc[u]] + sz[rc[u]] + 1;
}

pair<int, int> split(int u, int x) {
	if (u == 0) return make_pair(0, 0);
	pair<int, int> p;
	if (key[u] >= x) {
		p = split(lc[u], x);
		lc[u] = p.second;
		p.second = u;
	} else {
		p = split(rc[u], x);
		rc[u] = p.first;
		p.first = u;
	}
	maintain(u);
	return p;
}

int merge(int u, int v) {
	if (u == 0 || v == 0) return u + v;
	if (pri[u] > pri[v]) {
		rc[u] = merge(rc[u], v);
		maintain(u);
		return u;
	} else {
		lc[v] = merge(u, lc[v]);
		maintain(v);
		return v;
	}
}

void insert(int &root, int x) {
	pair<int, int> rt = split(root, x);
	root = merge(merge(rt.first, node(x)), rt.second);
}

void erase(int &root, int x) {
	pair<int, int> rt1 = split(root, x);
	pair<int, int> rt2 = split(rt1.second, x + 1);
	int u = merge(lc[rt2.first], rc[rt2.first]);
	root = merge(merge(rt1.first, u), rt2.second);
}

int order_of_key(int root, int k) {
	int ret = 0;
	int u = root;
	while (u) {
		if (key[u] >= k) {
			u = lc[u];
		} else {
			ret += sz[lc[u]] + 1;
			u = rc[u];
		}
	}
	return ret;
}

int key_by_order(int root, int k) {
	int u = root;
	while (u) {
		if (sz[lc[u]] == k) {
			break;
		}
		if (k < sz[lc[u]]) {
			u = lc[u];
		} else {
			k -= sz[lc[u]] + 1;
			u = rc[u];
		}
	}
	return key[u];
}

int get_prev(int root, int x) {
	return key_by_order(root, order_of_key(root, x) - 1);
}

int get_next(int root, int x) {
	return key_by_order(root, order_of_key(root, x + 1));
}

signed main() {
	int n;
	scanf("%d", &n);
	int root = 0;
	while (n--) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if (opt == 1) {
			insert(root, x);
		} else if (opt == 2) {
			erase(root, x);
		} else if (opt == 3) {
			int r = order_of_key(root, x);
			printf("%d\n", r + 1);
		} else if (opt == 4) {
			int val = key_by_order(root, x - 1);
			printf("%d\n", val);
		} else if (opt == 5) {
			int prev = get_prev(root, x);
			printf("%d\n", prev);
		} else if (opt == 6) {
			int next = get_next(root, x);
			printf("%d\n", next);
		}
	}
	return 0;
}

$ST表$

#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 2000001;
const int logN = 21;
int f[MAXN][logN + 1], Logn[MAXN + 1];

void pre() { 
	Logn[1] = 0;
	Logn[2] = 1;
	for (int i = 3; i < MAXN; i++) {
		Logn[i] = Logn[i / 2] + 1;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> f[i][0];
	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, y;
		cin >> x >> y;
		int s = Logn[y - x + 1];
		cout << max(f[x][s], f[y - (1 << s) + 1][s]) << '\n';
	}
	return 0;
}

$dijkstra$

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

using ll = long long;
const int maxn = 100010;
struct Edge {
    int v, w;
};
vector<Edge> G[maxn];
struct Node {
    int u;
    ll d;
    bool operator<(const Node &n) const { return d > n.d; }
};
ll d[maxn];
bool vis[maxn];

void Dij(int s) {
    memset(d, 0x3f, sizeof(d));
    priority_queue<Node> pq;
    d[s] = 0, pq.push({s, d[s]});
    while (!pq.empty()) {
        int u = pq.top().u;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (Edge e : G[u]) {
            int v = e.v, w = e.w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({v, d[v]});
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    Dij(1);
    for (int i = 1; i <= n; ++i) cout << d[i] << " ";
    return 0;
}

$SPFA$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5010, maxm = 5010;
struct edge {
    int v, w;
};
vector<edge> G[maxn];
ll d[maxn];
int n;
bool inq[maxn];
int cnt[maxn];
bool spfa(int s) {
    memset(d, 0x3f, sizeof(d));
    queue<int> q;
    d[s] = 0, cnt[s] = 0, q.push(s), inq[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop(), inq[u] = 0;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v, w = G[u][i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return 1;  
                if (!inq[v]) {
                    q.push(v), inq[v] = 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    int m, u, v, w, s = 1;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        G[u].push_back({v, w});
    }
    spfa(1);
    for(int i = 1 ; i < n + 1 ; i++){
    	if(d[i] != inf)
		cout << d[i] << " ";
		else{
			cout << "inf" << " ";
		}
	}
    return 0;
}

$强连通分量$

#include <iostream>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
int n , m;
int clk , dfn[maxn] , low[maxn];
int stc[maxn] , top;
int id[maxn] , scc;
vector<int> e[maxn];
void dfs(int u){
	stc[top++] = u;
	dfn[u] = low[u] = ++clk;
	for(int v : e[u]){
		if(!dfn[v]){
			dfs(v);
			low[u] = min(low[u] , low[v]);
		}
		else if(!id[v]){
			low[u] = min(low[u] , dfn[v]);
		}
	}
	if(low[u] == dfn[u]){
		++scc;
		do{
			id[stc[--top]] = scc;
		}while(stc[top] != u);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	while(m--){
		int u , v;
		cin >> u >> v;
		e[u].push_back(v);
	}
	for(int u = 1 ; u <= n ; u++){
		if(!dfn[u]){
			dfs(u);
		}
	}
	cout << scc;
	return 0;
}

$割点$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n , m;
int clk , dfn[maxn] , low[maxn];
int cvnum;
vector<int> e[maxn];
void dfs(int u , int fa){
	bool iscut = false;
	int son = 0;
	dfn[u] = low[u] = ++clk;
	for(int v: e[u]){
		if(!dfn[v]){
			dfs(v , u);
			low[u] = min(low[u] , low[v]);
			son++;
			if(fa != -1 && low[v] >= dfn[u]){
				iscut = true;
			}
		}else{
			low[u] = min(low[u] , dfn[v]);
		}
	}
	iscut |= (fa == -1 && son > 1);
	if(iscut){
		cvnum++;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	while(m--){
		int u , v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int u = 1 ; u <= n ; u++){
		if(!dfn[u]){
			dfs(u , -1);
		}
	}
	cout << cvnum;
	return 0;
}

$桥$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n , m;
int clk , dfn[maxn] , low[maxn];
int cvnum;
vector<int> e[maxn];
void dfs(int u , int fa){
	dfn[u] = low[u] = ++clk;
	for(int v: e[u]){
		if(fa == v){
			continue;
		}
		if(!dfn[v]){
			dfs(v , u);
			low[u] = min(low[u] , low[v]);
			if(low[v] > dfn[u]){
				cvnum++;
			}
		}else{
			low[u] = min(low[u] , dfn[v]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	while(m--){
		int u , v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int u = 1 ; u <= n ; u++){
		if(!dfn[u]){
			dfs(u , -1);
		}
	}
	cout << cvnum;
	return 0;
}

$kruskal$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, maxm = 100010;
struct Edge {
    int u, v, w;
    bool operator<(const Edge &n) const { return w < n.w; }
}E[maxm];
int fa[maxn], n, m;
void init() {
    for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    fa[ry] = rx;
}
long long kru() {
	sort(E, E + m); 
    long long res = 0;
	int cnt = n; 
    for (int i = 0; i < m; ++i) {
        Edge e = E[i];
        if (find(e.u) != find(e.v)) {
			merge(e.u, e.v);
        	--cnt, res += e.w;
		}
    }
    if (cnt > 1) return -1; 
    return res;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> E[i].u >> E[i].v >> E[i].w;
	}
	init();
	cout << kru() << endl;
	return 0;
}

$KMP$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn];
int kmp(string a , string b){
	int n = a.size();
	int m = b.size();
	a = '$' + a;
	b = '$' + b;
	for(int k = 2 , j = 0 ; k <= m ; k++){
		while(j > 0 && b[k] != b[j + 1]){
			j = f[j];
		}
		if(b[k] == b[j + 1]){
			j++;
		}
		f[k] = j;
	}
	int ans = 0;
	for(int k = 1 , j = 0 ; k <= n ; k++){
		while(j > 0 && a[k] != b[j + 1]){
			j = f[j];
		}
		if(a[k] == b[j + 1]){
			j++;
			if(j == m){
				ans++;
				j = f[j];
			}
		}
	}
	return ans;
}
int main(){
	string a , b;
	cin >> a >> b;
	cout << kmp(a , b);
	return 0;
}