预计可能会有:

数论:快速幂,gcd,exgcd,逆元,Lucas定理,CRT,BSGS,欧拉函数,线性筛,矩阵乘法,FFT

图论:最短路,最小生成树,最大流,费用流,有向图的强连通分量,无向图的边的双联通分量

树:LCA,树分治,树链剖分

数据结构:树状数组,线段树,Splay,Treap,LCT,莫队,左偏树

先写一部分吧,反正大多数也不会,会写多少写多少吧…

数论

快速幂

typedef long long ll;
inline ll qpow(ll a, ll n, ll mod){
	ll res=1;
    while(n){
        if(n&1) res=(res*a)%mod;
        n>>=1;
        a=(a*a)%mod;
    }
    return res;
}

gcd

inline int gcd(int a,int b){
	return b==0?a:gcd(b,a%b);
}
inline int lcm(int a,int b){
    return a*b/gcd(a,b);
}

exgcd

inline void exgcd(int a,int b,int c,int &x,int &y){
    if(!b){c=a;x=1;y=0;return ;}
    else{exgcd(b,a%b,c,y,x);y-=(a/b)*x;}
}

逆元

inline int inv(int a,int n){
    return qpow(a,n-2,n);
}

inline int inv(int a,int n){
    int x, y;
    exgcd(a,n,x,y);
    return (x+n)%n;
}

欧拉函数

inline void get_phi(){
    memset(not_prime, 0, sizeof(not_prime));
    phi[1]=1;
    for(int i = 2; i <= n; ++i){
        if(!not_prime[i]){prime[++top]=i;phi[i]=i-1;}
        for(int j = 1; j <= top&&i*prime[j] <= n; ++j){
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0){phi[prime[j]*i]=phi[i]*prime[j];break;}
            phi[prime[j]*i]=phi[i]*(prime[j]-1);
        }
    }
}

中国剩余定理

int CRT(int a[],int m[],int n)
{
    int M = 1;
    int ans = 0;
    for(int i=1; i<=n; i++)
        M *= m[i];
    for(int i=1; i<=n; i++)
    {
        int x, y;
        int Mi = M / m[i];
        exgcd(Mi, m[i], x, y);
        ans = (ans + Mi * x * a[i]) % M;
    }
    if(ans < 0) ans += M;
    return ans;
}

线性筛

int prime[max_], primes[max_], num;
memset(prime,1,sizeof(prime));
prime[0]=prime[1]=0;
for(int i=2;i<=limit;i++)
{
	if(prime[i])primes[num++]=i;
	for(int j=0;j<num&&i*primes[j]<limit;j++)
	{
		prime[i*primes[j]]=0;
		if(!(i%primes[j]))break;
	}
}

矩阵乘法

//顺便带了一个快速幂,递推数列的矩阵自己推
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
const int Mod = 1e9 + 7;
struct Mat{
    ll m[110][110];
};

ll n, k;
Mat input, unit;

Mat Matrix_Mul(Mat x, Mat y) {
    Mat c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            c.m[i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                c.m[i][j] = c.m[i][j] % Mod + x.m[i][k] * y.m[k][j] % Mod;
            }
        }
    }
    return c;
}
Mat Quick_Matrix_pow(Mat a, ll n) {
    Mat res = unit;
    while (n) {
        if (n & 1)
            res = Matrix_Mul(res, a);
        a = Matrix_Mul(a, a);
        n >>= 1;
    }
    return res;
}
int main(){
    scanf("%lld %lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%lld", &input.m[i][j]);
        }
    }
    for (int i = 1; i <= n; i++)
        unit.m[i][i] = 1;
    Mat ans = Quick_Matrix_pow(input, k);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%lld ", ans.m[i][j] % Mod);
        }
        printf("\n");
    }
    return 0;
}

Lucas定理

用不熟练还是不写了

BSGS

只听过

FFT

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cassert>
#include<climits>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<iomanip>
#include<bitset>
#include<sstream>
#include<fstream>
#define debug puts("-----")
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define dep(i,r,l) for(register int i=r;i>=l;--i)

typedef long long ll;
typedef unsigned long long ull;
template <class T> T chkmax(T a, T b) {return a > b ? a : b;}
template <class T> T chkmin(T a, T b) {return a > b ? b : a;}
const int Maxn = 2e6 + 7;
const int INF = 2147483647;
const int mod = 19260817;
const double pi = acos(-1.0);

inline int read() {
	register int g = 1; register char ch;
	while(!isdigit(ch = getchar())) if(ch == '-') g = -1;
	register int x = ch ^ '0';
	while(isdigit(ch = getchar())) x = x * 10 + (ch ^ '0');
	return x * g;	
}

inline void print(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');	
}

struct Complex{
    double a, b;
    Complex() {}
    Complex(double _a, double _b) : a(_a), b(_b) {}
    Complex(double _a) : a(_a), b(0.0) {}
    inline Complex operator + (const Complex &z) const {
        return Complex(a + z.a, b + z.b);
    }
    inline Complex operator - (const Complex &z) const {
        return Complex(a - z.a, b - z.b);	
    }
    inline Complex operator * (const Complex &z) const {
        return Complex(a * z.a - b * z.b, a * z.b + b * z.a);
    }
    inline Complex operator / (const Complex &z) const {
        double m = z.a * z.a + z.b * z.b;
        return Complex((a * z.a + b * z.b) / m, (b * z.a - a * z.b) / m);	
    }
};

Complex a[Maxn], b[Maxn];
int alen, blen, len, L, n, rev[Maxn], ans[Maxn];
int _a[Maxn], _b[Maxn];

inline void FFT(Complex c[], int n, int f) {
    Complex wn, w, x, y;
    for(int i = 0; i < n; ++i)
        if(i < rev[i]) std::swap(c[i], c[rev[i]]);
    for(int i = 1; i < n; i <<= 1) {
        wn = Complex(cos(pi / i), sin(pi / i) * f);
        for(int p = i << 1, j = 0; j < n; j += p) {
            w = Complex(1, 0);
            for(int k = 0; k < i; ++k, w = w * wn) {
                x = c[j + k]; y = w * c[j + k + i];
                c[j + k] = x + y; c[j + k + i] = x - y;
            }
        }
    }
    if(!~f) for(int i = 0; i < n; ++i) c[i].a /= (double)n;
    return ;
}

int main() {
    alen = read(), blen = read(), len = alen + blen;
    for(n = 1; n <= len; n <<= 1, L++);
    for(int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
	for(int i = 0; i <= alen; ++i) a[i].a = read();
    for(int i = 0; i <= blen; ++i) b[i].a = read();
    FFT(a, n, 1); FFT(b, n, 1);
    for(int i = 0; i <= n; ++i) a[i] = a[i] * b[i];
    FFT(a, n, -1);
    for(int i = 0; i <= len; ++i) ans[i] = (int)(a[i].a + 0.5);
	for(int i = 0; i <= len; ++i) printf("%d ", ans[i]);
	return 0;
}

图论

最短路

Dijkstra
typedef long long ll;
#define N 200010
#define INF 1 << 30

struct EdGe
{
    int next, to, val;	
}edge[N * 2];

int last[N * 2], cnt, dis[N];
bool vis[N];

struct heapnode
{
    int node,val;
    bool operator < (const heapnode &rhs) const 
    {
        return val > rhs.val;
    }
};

inline void addedge(int u, int v, int w)
{
    edge[++cnt].next = last[u];
    edge[cnt].to = v;
    edge[cnt].val = w;
    last[u] = cnt;
}

int n, m, s;

void dijkstra(int s)
{	
    std::priority_queue<heapnode> Q;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        vis[i] = 0;
    }
    dis[s] = 0;
    Q.push((heapnode){s,0});
    while (!Q.empty())
    {
        heapnode U = Q.top();
        Q.pop();
        if (vis[U.node])
            continue;
        int u = U.node;
        vis[u] = 1;
        for (int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].val)
            {
                dis[v] = dis[u] + edge[i].val;
                Q.push((heapnode){v,dis[v]});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dijkstra(s);
    ///do something...
    return 0;
}
SPFA///slf
typedef long long ll;
#define N 200010
#define INF 1 << 30

struct EdGe
{
    int next, to, val;	
}edge[N * 2];

int last[N * 2], cnt, dis[N];
bool vis[N];

inline void addedge(int u, int v, int w)
{
    edge[++cnt].next = last[u];
    edge[cnt].to = v;
    edge[cnt].val = w;
    last[u] = cnt;
}

int n, m, s;

void spfa(int s)
{
    std::deque<int> Q;
    for (int i = 1; i <= P; i++)
    {
        dis[i] = INF;
        vis[i] = 0;
    }
    Q.push_back(s);
    dis[s] = 0;
    vis[s] = 1;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop_front();
        vis[u] = 0;
        for (int i = last[u]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            if (dis[v] > dis[u] + edge[i].val)
            {
                dis[v] = dis[u] + edge[i].val;
                if (!vis[v])
                {
                    vis[v] = 1;
                    if(!q.empty()&&dis[to]<dis[q.front()]) q.push_front(to);
                    else q.push_back(to);
                    //忘了是不是这么写了...
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= C; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    spfa(s);
    return 0;
}

最小生成树

Kruskal
struct edge{
	int next, to, val;
}e[max_<<1];

int F[max_];
inline int find(int x){
	return x==F[x]?x:F[x]=find(F[x]);
}
inline void merge(int a, int b){
	F[find(b)]=find(a);
}
inline bool cmp(edge a, edge b){
	return a.val<b.val;
}
int ans=0;
inline void kruskal(){
	int k=0;
	for(int i=1;i<=n;++i) F[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i){
		int u=e[i].next;
		int v=e[i].to;
		if(find(u)!=find(v)){
			merge(u,v);
			ans+=e[i].val;k++;
			if(k==n-1) break;
		}
	}
}
Prim

先占坑,不会写

网络流

Dinic
int n, m, s, t;
struct edge{
	int next, to, val;
}e[max_<<1];
int head[max_], cnt=1, cur[max_], depth[max_];

inline void add(int u,int v,int w){e[++cnt].next=head[u];e[cnt].to=v;e[cnt].flow=w;head[u]=cnt;}
inline void ins(int u,int v,int w){add(u,v,w);add(v,u,0);}

inline bool bfs(){
    memset(depth, -1, sizeof(depth));
    queue<int> q;
    q.push(s), depth[s]=0;
    while(!q.empty()){
    	int now=q.front();q.pop();
    	for(int i=head[now];i;i=e[i].next){
    		int to=e[i].to;
    		if(depth[to]==-1&&e[i].flow){
    			depth[to]=depth[now]+1;q.push(to);
    		}
    	}
    }
    return depth[t]!=-1;
}

inline int dfs(int now, int limit){
	if(now==t) return limit;
	int w, flow=0;
	for(int& i=cur[now];i;i=e[i].next){
		int to=e[i].to;
		if(depth[to]==depth[now]+1&&e[i].flow){
			w=dfs(to, min(limit-flow, e[i].flow));
			e[i].flow-=w;
			e[i^1].flow+=w;
			flow+=w;
			if(flow==limit) return flow;
		}
	}
	if(!flow) depth[now]=-1;
	return flow;
}

int maxflow=0;
inline void dinic(){
	while(bfs()){
		memcpy(cur, head, sizeof(head));
		maxflow+=dfs(s, inf);
	}
}
zkw费用流//不想写一般的费用流了
int n, m, s, t;
struct edge{
	int next, to, flow, dis;
}e[max_<<1];
int head[max_], cnt=1, depth[max_], cur[max_], dis[max_], vis[max_];

inline void add(int u,int v,int w,int c){
	e[++cnt].next=head[u];e[cnt].to=v;e[cnt].flow=w;e[cnt].dis=c;head[u]=cnt;
}
inline void ins(int u,int v,int w, int c){
	ins(u,v,w,c);ins(v,u,0,-c);
}

bool spfa(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    deque<int> q;
    q.push_back(t), dis[t]=0, vis[t]=1;
    while(!q.empty()){
        int now=q.front();q.pop_front();vis[now]=0;
        for(int i=head[now];i;i=e[i].next){
            int to=e[i].to;
            if(e[i^1].flow&&dis[to]>dis[now]-e[i].dis){
                dis[to]=dis[now]-e[i].dis;
                if(!vis[to]){
                    vis[to]=1;
                    if(!q.empty()&&dis[to]<dis[q.front()]) q.push_front(to);
                    else q.push_back(to);
                }
            }
        }
    }
    return dis[s]<inf;
}

int dfs(int now, int limit){
    if(now==t){
        vis[now]=1;return limit;
    }
    int w, flow=0;
    vis[now]=1;
    for(int& i=cur[now];i;i=e[i].next){
        int to=e[i].to;
        if(!vis[to]&&e[i].flow&&dis[now]-e[i].dis==dis[to]){
            w=dfs(to,min(e[i].flow,limit-flow));
            if(w){
                ans+=w*e[i].dis;e[i].flow-=w;e[i^1].flow+=w;flow+=w;
            }
            if(flow==limit) break;
        }
    }
    return flow;
}

int mcf(){
    int flow=0;
    while(spfa()){
        vis[t]=1;
        while(vis[t]){
            memset(vis, 0, sizeof(vis));
            memcpy(cur, head, sizeof(head));
            flow+=dfs(s, inf);
        }
    }
    return flow;
}

强连通分量

割点
#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 300010;
const int inf = 0x7f7f7f7f;

inline int read() {
    register char ch;
    while(!isdigit(ch = getchar()));
    register int x = ch ^ '0';
    while(isdigit(ch = getchar())) x = (((x << 2) + x) << 1) + (ch ^ '0');
    return x;
}

int n, m;
struct edge{
    int next, to;
}e[maxn<<1];
int head[maxn], cnt = 0;

inline void add(int u, int v) {e[++cnt] = (edge){head[u], v}; head[u] = cnt;}
inline void ins(int u, int v) {add(u, v); add(v, u);}

int low[maxn], dfn[maxn], idx = 0, cut[maxn], point = 0;

inline void tarjan(int now, int fa) {
    low[now] = dfn[now] = ++idx;
    int child = 0;
    for(register int i = head[now]; i; i = e[i].next) {
        int to = e[i].to;
        if(!dfn[to]) {
            tarjan(to, fa);
            low[now] = std::min(low[now], low[to]);
            if(low[to] >= dfn[now] && now != fa)
                cut[now] = 1;
            if(now == fa) ++child;
        }
        low[now] = std::min(low[now], dfn[to]);
    }
    if(child >= 2 && now == fa) cut[now] = 1;
}

int main() {
    n = read(), m = read();
    for(register int i = 1; i <= m; ++i) {
        int x = read(), y = read();
        ins(x, y);
    }
    for(register int i = 1; i <= n; ++i) 
        if(!dfn[i]) tarjan(i, i);
    for(register int i = 1; i <= n; ++i)
        if(cut[i]) ++point;
    printf("%d\n", point);
    for(register int i = 1; i <= n; ++i)
        if(cut[i]) printf("%d ", i);
    return 0;
}

LCA

//不想自己打了…

倍增
int lgn, dep[maxn], anc[maxn][30];
inline void dfs(int u) {
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(v == anc[u][0]) continue;
        anc[v][0] = u;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}
 
inline void calanc() {
    for(int j = 1; (1 << j) <= sz; j++) {
        for(int i = 1; i <= sz; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}
 
inline int querylca(int u, int v) {
    if(dep[u] > dep[v]) std::swap(u, v);
    int del = dep[v] - dep[u];
    for(int i = 0; (1 << i) <= del; i++) {
        if((1 << i) & del) v = anc[v][i];
    }
    if(u == v) return u;
    for(int i = lgn; i >= 0; i--) {
        if(anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}
ST表
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define N 500010
typedef long long ll;
struct Edge
{
    int next, to;
}edge[N * 2];

int n, m, s, cnt = 0;
int num = 0, cnt_ = 0;
struct Tree
{
    int last[N];
    int depth[N];//深度 
    bool vis[N];
    void add(int u, int v)
    {
        edge[++cnt].next = last[u];
        edge[cnt].to = v;
        last[u] = cnt; 
    }   
} tree;

struct RMQ
{
    int F[N], dp[N][21], eu[N];// 
} rmq;

void dfs(int u, int fa)
{
    int tmp = ++num;
    rmq.eu[++cnt_] = tmp;
    rmq.F[tmp] = u;
    tree.depth[u] = cnt_;
    for (int i = tree.last[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        else
        {
            tree.vis[v] = 1;
            dfs(v, u);
            rmq.eu[++cnt_] = tmp;
        } 
    }
}

void rmq_st(int n)
{
    for (int i = 1; i <= n; i++)
        rmq.dp[i][0] = rmq.eu[i];
    int m = (int) (log(1.0 * n) / log(2.0));
    for (int j = 1; j <= m; j++)
    {
        int k = n - (1 << j) + 1;
        for (int i = 1; i <= k; i++)
        {
            rmq.dp[i][j] = std::min(rmq.dp[i][j - 1], rmq.dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

inline int rmq_find(int l, int r)
{
    int k = (int) (log(1.0 * (r - l) + 1) / log(2.0));
    return std::min(rmq.dp[l][k] , rmq.dp[r - (1 << k) + 1][k]);
}

inline int lca(int x, int y)
{
    if (tree.depth[x] > tree.depth[y])
        std::swap(x, y);
    int k = rmq_find(tree.depth[x], tree.depth[y]);
    return rmq.F[k];
}

inline void init()
{
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1, x, y; i <= n - 1; i++)
    {
        scanf("%d%d", &x, &y);
        tree.add(x, y);
        tree.add(y, x);
    }
    dfs(s, 0);
}

inline void query()
{
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }   
}

int main()
{
    init();
    rmq_st(cnt_);
    query();
    return 0;
}

树分治

不会

树链剖分

#include <bits/stdc++.h>
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define dep(i,r,l) for(register int i=r;i>=l;--i)
using namespace std;
typedef long long ll;
const int maxn = 200010;
const int inf = 0x7f7f7f7f;

inline int read(){
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}

int n, m, r, p;
int a[maxn], b[maxn], size=0;

struct Edge{
    int next, to, val;
}e[maxn];
int head[maxn], cnt=0;

inline void add(int u,int v){e[++cnt]=(Edge){head[u],v};head[u]=cnt;}
inline void ins(int u,int v){add(u,v);add(v,u);}

struct SegMent{
    int l, r, sum, tags, sz;
}tr[maxn];

struct Sub_Tree{
    int dep[maxn], fa[maxn], son[maxn], tot[maxn];
    int top[maxn], idx[maxn];
    inline int dfs1(int now, int f, int depth){
        dep[now]=depth;
        fa[now]=f;
        tot[now]=1;
        int maxson=-1;
        for(int i=head[now];i;i=e[i].next){
            int to=e[i].to;
            if(to==f) continue;
            tot[now]+=dfs1(to,now,depth+1);
            if(tot[to]>maxson) maxson=tot[to], son[now]=to;
        }
        return tot[now];
    }
    inline void dfs2(int now, int top_node){
        idx[now]=++size;
        a[size]=b[now];
        top[now]=top_node;
        if(!son[now]) return;
        dfs2(son[now],top_node);
        for(int i=head[now];i;i=e[i].next){
            int to=e[i].to;
            if(!idx[to])
                dfs2(to,to);
        }
    }
}sub;

struct SegMent_Tree{
    #define lson o<<1
    #define rson o<<1|1
    inline void push_up(int o){tr[o].sum=(tr[lson].sum+tr[rson].sum+p)%p;}
    inline void push_down(int o){
        if(tr[o].tags){
            tr[lson].tags=(tr[lson].tags+tr[o].tags)%p;
            tr[rson].tags=(tr[rson].tags+tr[o].tags)%p;
            tr[lson].sum=(tr[lson].sum+tr[lson].sz*tr[o].tags)%p;
            tr[rson].sum=(tr[rson].sum+tr[rson].sz*tr[o].tags)%p;
            tr[o].tags=0;
        }
    }
    inline void build(int o, int l, int r){
        tr[o].l=l,tr[o].r=r,tr[o].sz=r-l+1;
        if(l==r){
            tr[o].sum=a[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(lson,l,mid); build(rson,mid+1,r);
        push_up(o);
    }
    inline void update_add(int o, int l, int r, int v){
        if(l<=tr[o].l&&tr[o].r<=r){
            tr[o].sum+=tr[o].sz*v;
            tr[o].tags+=v;
            return ;
        }
        push_down(o);
        int mid=(tr[o].l+tr[o].r)>>1;
        if(l<=mid) update_add(lson,l,r,v);
        if(r>mid) update_add(rson,l,r,v);
        push_up(o);
    }
    inline int ask_sum(int o, int l, int r){
        if(l<=tr[o].l&&tr[o].r<=r){
            return tr[o].sum%p;
        }
        push_down(o);
        int mid=(tr[o].l+tr[o].r)>>1;
        int ans=0;
        if(l<=mid) ans=(ans+ask_sum(lson,l,r))%p;
        if(r>mid) ans=(ans+ask_sum(rson,l,r))%p;
        return ans; 
    }
    #undef lson
    #undef rson
}seg;

struct Modify{
    inline void query_sum(int x,int y){
        int ans=0;
        while(sub.top[x]!=sub.top[y]){
            if(sub.dep[sub.top[x]]<sub.dep[sub.top[y]]) swap(x,y);
            ans=(ans+seg.ask_sum(1,sub.idx[sub.top[x]],sub.idx[x]))%p;
            x=sub.fa[sub.top[x]];
        }
        if(sub.dep[x]>sub.dep[y]) swap(x,y);
        ans=(ans+seg.ask_sum(1,sub.idx[x],sub.idx[y]))%p;
        printf("%d\n", ans%p);
    }
    inline void modify_reg(int x,int y,int v){
        while(sub.top[x]!=sub.top[y]){
            if(sub.dep[sub.top[x]]<sub.dep[sub.top[y]]) swap(x,y);
            seg.update_add(1,sub.idx[sub.top[x]],sub.idx[x],v);
            x=sub.fa[sub.top[x]];
        }
        if(sub.dep[x]>sub.dep[y]) swap(x,y);
        seg.update_add(1,sub.idx[x],sub.idx[y],v);
    }
    inline void modify_sontree(int x,int v){
        seg.update_add(1,sub.idx[x],sub.idx[x]+sub.tot[x]-1,v);
    }
    inline void query_sontree(int x){
    	printf("%d\n", seg.ask_sum(1,sub.idx[x],sub.idx[x]+sub.tot[x]-1)%p);
    }
}modify;

int main(){
    memset(head,0,sizeof(head));
    n=read(),m=read(),r=read(),p=read();
    rep(i,1,n) b[i]=read();
    rep(i,1,n-1){
        int x=read(), y=read();
        ins(x,y);
    }
    sub.dfs1(r,0,1);
    sub.dfs2(r,r);
    seg.build(1,1,n);
    rep(i,1,m){
        int opt=read(),x,y,z;
        if(opt==1){
            x=read(),y=read(),z=read()%p;
            modify.modify_reg(x,y,z);
        }
        if(opt==2){
            x=read(),y=read();
            modify.query_sum(x,y);
        }
        if(opt==3){
            x=read(),z=read()%p;
            modify.modify_sontree(x,z);
        }
        if(opt==4){
            x=read();
            modify.query_sontree(x);
        }
    }
    return 0;
}

数据结构

树状数组

//真的不想写了…

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

int n,m;
int tree[2000010];
int a,b,c,d;

inline int lowbit(int x){
    return x & -x;
}

inline void add(int x,int k){//单点+
    while(x<=n){
        tree[x] += k;
        x += lowbit(x);
    }
}

inline int sum(int x){
    int ans=0;
    while(x>0){
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>a;
        add(i,a);   
    }
    for(int i = 1; i <= m; ++i){
        cin>>b>>c>>d;
        if(b==1){
            add(c,d);
        }
        if(b==2){
            cout<<sum(d)-sum(c-1)<<endl;
        }
    }
    return 0;
}
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <time.h>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rpe(i,r,l) for(int i=r;i>=l;--i)
#define pts puts("")
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int node=500010;
int tree[node], n, m, in[node];

inline int lowbit(int x){return x &-x;}
inline void add(int x,int v){while(x<=n){tree[x]+=v;x+=lowbit(x);}}//区间+
inline int query(int x){int ans=0;while(x!=0){ans+=tree[x];x-=lowbit(x);}return ans;}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    rep(i,1,n) cin>>in[i];
    rep(i,1,m){
    	int t,x,y,z;
    	cin>>t;
    	if(t==1){
    		cin>>x>>y>>z;
    		add(x,z);
    		add(y+1,-z);
        } else{
            cin>>x;
            cout<<in[x]+query(x)<<endl;
        }
    }
}

线段树

简单的线段树
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const int MAX = 110000;
int N, M, Q;
LL sum[500000], add[500000];
inline int read()
{
	int X = 0, w = 1; char ch = 0;
	while (ch<'0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') X = (X << 3) + (X << 1) + ch - '0', ch = getchar();
	return X * w;
}//读入优化
inline void write(long long x)
{
	if (x<0) putchar('-'), x = -x;
	if (x>9) write(x / 10);
	putchar(x % 10 + '0');
}//输出优化

inline void push_up(int p) {
	sum[p] = sum[p * 2] + sum[p * 2 + 1];
}//向上维护线段树

void build(int root, int l, int r)
{
	add[root] = 0;
	if (l == r)
		sum[root] = read();
	else
	{
		int k = (l + r) >> 1;
		build(2 * root, l, k);
		build(2 * root + 1, k + 1, r);
		push_up(root);
	}
}//建树

void pushdown(int root, int l, int r)
{
	if (add[root])
	{
		int s1 = 2 * root, s2 = 2 * root + 1, k = (l + r) >> 1;
		add[s1] += add[root];
		add[s2] += add[root];
		sum[s1] += add[root] * (k - l + 1);
		sum[s2] += add[root] * (r - k);
		add[root] = 0;
	}
}//向下维护线段树

void update(int nl, int nr, int c, int root, int l, int r)//访问区间 增加值 节点位置(或者用pos更好?) 原区间
{
	if (nl <= l && r <= nr)//访问区间直接包含原区间
	{
		add[root] += c;
		sum[root] += c * (r - l + 1);
		return;
	}
	pushdown(root, l, r);
	int k = (l + r) >> 1;
	if (nl <= k) update(nl, nr, c, 2 * root, l, k);//左边
	if (nr >= k + 1) update(nl, nr, c, 2 * root + 1, k + 1, r);//右边
	push_up(root);
}

LL query(int nl, int nr, int root, int l, int r)//原理与上方区间增加值一样
{
	if (nl <= l && r <= nr) //同样,访问区间直接包含原区间,直接输出
			return sum[root];
	pushdown(root, l, r);
	int k = (l + r) >> 1;
	LL ans = 0;
	if (nl <= k) ans += query(nl, nr, 2 * root, l, k);
	if (nr >= k + 1) ans += query(nl, nr, 2 * root + 1, k + 1, r);
	return ans;
}

int main()
{
	N = read(), M = read();
	build(1, 1, N);
	for (int i = 1; i <= M; i++)
	{
		int L, R, C;
		Q = read();
		if (Q == 1)
		{
			L = read(), R = read(), C = read();
			update(L, R, C, 1, 1, N);
		}
		if (Q == 2)
		{
			L = read(), R = read();
			write(query(L, R, 1, 1, N));
			putchar('\n');
		}
	}
	//system("pause");
	return 0;;
}
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int p;
long long a[100007];
struct node{
    long long v, mul, add;
}node[400007];

void bt(int root, int l, int r){
    node[root].mul=1;
    node[root].add=0;
    if(l==r){
        node[root].v=a[l];
    }
    else{
        int m=(l+r)/2;
        bt(root*2, l, m);
        bt(root*2+1, m+1, r);
        node[root].v=node[root*2].v+node[root*2+1].v;
    }
    node[root].v%=p;
    return ;
}
void pushdown(int root, int l, int r){
    int m=(l+r)/2;
    node[root*2].v=(node[root*2].v*node[root].mul+node[root].add*(m-l+1))%p;
    node[root*2+1].v=(node[root*2+1].v*node[root].mul+node[root].add*(r-m))%p;
    node[root*2].mul=(node[root*2].mul*node[root].mul)%p;
    node[root*2+1].mul=(node[root*2+1].mul*node[root].mul)%p;
    node[root*2].add=(node[root*2].add*node[root].mul+node[root].add)%p;
    node[root*2+1].add=(node[root*2+1].add*node[root].mul+node[root].add)%p;
    node[root].mul=1;
    node[root].add=0;
    return ;
}

void ud1(int root, int nodedl, int nodedr, int l, int r, long long k){
    if(r<nodedl || nodedr<l){
        return ;
    }
    if(l<=nodedl && nodedr<=r){
        node[root].v=(node[root].v*k)%p;
        node[root].mul=(node[root].mul*k)%p;
        node[root].add=(node[root].add*k)%p;
        return ;
    }
    pushdown(root, nodedl, nodedr);
    int m=(nodedl+nodedr)/2;
    ud1(root*2, nodedl, m, l, r, k);
    ud1(root*2+1, m+1, nodedr, l, r, k);
    node[root].v=(node[root*2].v+node[root*2+1].v)%p;
    return ;
}

void ud2(int root, int nodedl, int nodedr, int l, int r, long long k){
    if(r<nodedl || nodedr<l){
        return ;
    }
    if(l<=nodedl && nodedr<=r){
        node[root].add=(node[root].add+k)%p;
        node[root].v=(node[root].v+k*(nodedr-nodedl+1))%p;
        return ;
    }
    pushdown(root, nodedl, nodedr);
    int m=(nodedl+nodedr)/2;
    ud2(root*2, nodedl, m, l, r, k);
    ud2(root*2+1, m+1, nodedr, l, r, k);
    node[root].v=(node[root*2].v+node[root*2+1].v)%p;
    return ;
}

long long query(int root, int nodedl, int nodedr, int l, int r){
    if(r<nodedl || nodedr<l){
        return 0;
    }
    if(l<=nodedl && nodedr<=r){
        return node[root].v;
    }
    pushdown(root, nodedl, nodedr);
    int m=(nodedl+nodedr)/2;
    return (query(root*2, nodedl, m, l, r)+query(root*2+1, m+1, nodedr, l, r))%p;
}
int main(){
    int n, m;
    scanf("%d%d%d", &n, &m, &p);
    for(int i=1; i<=n; i++){
        scanf("%lld", &a[i]);
    }
    bt(1, 1, n);
    while(m--){
        int chk;
        scanf("%d", &chk);
        int x, y;
        long long k;
        if(chk==1){
            scanf("%d%d%lld", &x, &y, &k);
            ud1(1, 1, n, x, y, k);
        }
        else if(chk==2){
            scanf("%d%d%lld", &x, &y, &k);
            ud2(1, 1, n, x, y, k);
        }
        else{
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}

标记永久化线段树

#include<iostream>
#include<cstdio>
#include<cstring>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 201000
using namespace std;
int n,m;
int sum[N*4],add[N*4];
int a[N];
void build(int l,int r,int rt){
    if(l==r){
        sum[rt]=a[l];return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int rt,int l,int r,int v,int xl,int xr){
    sum[rt]+=v*(xr-xl+1);
    if(l==xl&&r==xr){
        add[rt]+=v; return;
    }
    int mid=(l+r)>>1;
    if(xr<=mid)  update(rt<<1,l,mid,v,xl,xr);
    else{
        if(xl>mid)   update(rt<<1|1,mid+1,r,v,xl,xr);
        else update(rt<<1,l,mid,v,xl,mid),update(rt<<1|1,mid+1,r,v,mid+1,xr);
    }
}
int query(int rt,int ad,int l,int r,int xl,int xr){
    if(xl==l&&xr==r){
        return sum[rt]+ad*(xr-xl+1);
    }  
    int mid=(l+r)>>1;
    if(xr<=mid) return query(rt<<1,ad+add[rt],l,mid,xl,xr);
    else{
        if(xl>mid) return query(rt<<1|1,ad+add[rt],mid+1,r,xl,xr);
        else return query(rt<<1,ad+add[rt],l,mid,xl,mid)+query(rt<<1|1,ad+add[rt],mid+1,r,mid+1,xr);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    pos(i,1,n) scanf("%d",&a[i]);
    build(1,n,1);
    pos(i,1,m){
        int opt;scanf("%d",&opt);
        int x,y;scanf("%d%d",&x,&y);
        if(opt==1){
            int k;scanf("%d",&k);
            update(1,1,n,k,x,y);
        }
        else printf("%d\n",query(1,0,1,n,x,y));
    }
    return 0;
}
//转载自Hallmeow

可持续化线段树

不会

动态加点线段树

//CF915E Physical Education Lessons
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define rr register
typedef long long ll;
const int maxn = 500007 * 30;
const int inf = 0x7f7f7f7f;

inline int read() {
    rr int g = 1, x = 0;
    rr char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') g = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (((x << 2) + x) << 1) + (ch ^ '0'); ch = getchar();}
    return x * g;
}

int n, q;
int sum[maxn], tags[maxn], rs[maxn], ls[maxn], id = 0, rt = 0;

inline void pushdown(int o, int l, int r) {
    if(tags[o] == -1) return ;
    int mid = (l + r) >> 1;
    if(l != r) {
        if(!ls[o]) ls[o] = ++id;
        if(!rs[o]) rs[o] = ++id;
        sum[ls[o]] = tags[o] * (mid - l + 1);
        sum[rs[o]] = tags[o] * (r - mid); 
        tags[ls[o]] = tags[o];
        tags[rs[o]] = tags[o];
    }
    tags[o] = -1;
}

inline void update(int &o, int ql, int qr, int l, int r, int v) {
    if(!o) o = ++id;
    if(ql <= l && r <= qr) {
        sum[o] = v * (r - l + 1);
        tags[o] = v;
        return ;
    }
    pushdown(o, l, r);
    int mid = (l + r) >> 1;
    if(ql <= mid) update(ls[o], ql, qr, l, mid, v);
    if(qr > mid) update(rs[o], ql, qr, mid + 1, r, v);
    sum[o] = sum[ls[o]] + sum[rs[o]];
}

int main() {
    memset(tags, -1, sizeof(tags));
    n = read(), q = read();
    for(int i = 1; i <= q; ++i) {
        int l = read(), r = read(), k = read();
        if(k == 1) update(rt, l, r, 1, n, 1);
        else update(rt, l, r, 1, n, 0);
        printf("%d\n", n - sum[1]);
    }
    return 0;
}

左偏树

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int max_ = 100010;

int n, m;
int ch[max_][2];//表示当前节点儿子的编号
int a[max_], dis[max_]/*树上距离*/, f[max_]/*父亲节点编号*/;

inline int merge(int x,int y){
    if(!x||!y) return x|y;
    if(a[x]>a[y]||(a[x]==a[y]&&x>y)) swap(x,y);//小根堆
    ch[x][1]=merge(ch[x][1],y);
    f[ch[x][1]]=x;
    if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0], ch[x][1]);//左偏树
    dis[x]=dis[ch[x][1]]+1;//左偏树的距离
    return x;
}

inline int getfa(int x){
    while(f[x]/*仍然存在父亲节点*/) x=f[x];
    return x;
}

inline void del(int x){
    a[x]=-1;
    f[ch[x][0]]=f[ch[x][1]]=0;
    merge(ch[x][0],ch[x][1]);
}

int main(){
    scanf("%d %d", &n, &m);
    dis[0]=-1;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= m; ++i){
        int k;
        scanf("%d", &k);
        if(k==1){
            int x, y;
            scanf("%d %d", &x, &y);
            if(a[x]==-1||a[y]==-1) continue;
            if(x==y) continue;
            merge(getfa(x),getfa(y));
        }
        else {
            int x;
            scanf("%d", &x);
            if(a[x]==-1) printf("-1\n");
            else{
                int now=getfa(x);
                printf("%d\n", a[now]);
                del(now);
            }
        }
    }
    return 0;
}

不知道什么东西

//hdu2089 数位DP入门题
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 10001;

int a[maxn];
int dp[maxn][2];

inline int dfs(int pos, int pre, int sta, bool limit) {
	if(pos == -1) return 1;
	if(!limit && dp[pos][sta] != -1) return dp[pos][sta];
	int up = limit ? a[pos] : 9;
	int res = 0;
	for(int i = 0; i <= up; ++i) {
		if(pre == 6 && i == 2) continue;
		if(i == 4) continue;
		res += dfs(pos - 1, i, i == 6, limit && i == a[pos]);
	}
	if(!limit) dp[pos][sta] = res;
	return res;
}

inline int solve(int x) {
	int pos = 0;
	while(x) {
		a[pos++] = x % 10;
		x /= 10;
	}
	return dfs(pos - 1, -1, 0, true);
}

int main() {
	int l, r;
	memset(dp, -1, sizeof(dp));
	while(scanf("%d %d", &l, &r)) {
		if(!l && !r) break;
		printf("%d\n", solve(r) - solve(l - 1));
	}
	return 0;
}

高精度<重载运算符>

const int MAXN = 410;  

struct BigNum  
{  
    int len, s[MAXN];  
    BigNum ()  
    {  
        memset(s, 0, sizeof(s));  
        len = 1;  
    }  
    BigNum (int num) { *this = num; }  
    BigNum (const char *num) { *this = num; }  
    BigNum operator = (const int num)  
    {  
        char s[MAXN];  
        sprintf(s, "%d", num);  
        *this = s;  
        return *this;  
    }  
    BigNum operator = (const char *num)  
    {  
        for(int i = 0; num[i] == '0'; num++) ;  //去前导0  
        len = strlen(num);  
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';  
        return *this;  
    }  
    BigNum operator + (const BigNum &b) const //+  
    {  
        BigNum c;  
        c.len = 0;  
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)  
        {  
            int x = g;  
            if(i < len) x += s[i];  
            if(i < b.len) x += b.s[i];  
            c.s[c.len++] = x % 10;  
            g = x / 10;  
        }  
        return c;  
    }  
    BigNum operator += (const BigNum &b)  
    {  
        *this = *this + b;  
        return *this;  
    }  
    void clean()  
    {  
        while(len > 1 && !s[len-1]) len--;  
    }  
    BigNum operator * (const BigNum &b) //*  
    {  
        BigNum c;  
        c.len = len + b.len;  
        for(int i = 0; i < len; i++)  
        {  
            for(int j = 0; j < b.len; j++)  
            {  
                c.s[i+j] += s[i] * b.s[j];  
            }  
        }  
        for(int i = 0; i < c.len; i++)  
        {  
            c.s[i+1] += c.s[i]/10;  
            c.s[i] %= 10;  
        }  
        c.clean();  
        return c;  
    }  
    BigNum operator *= (const BigNum &b)  
    {  
        *this = *this * b;  
        return *this;  
    }  
    BigNum operator - (const BigNum &b)  
    {  
        BigNum c;  
        c.len = 0;  
        for(int i = 0, g = 0; i < len; i++)  
        {  
            int x = s[i] - g;  
            if(i < b.len) x -= b.s[i];  
            if(x >= 0) g = 0;  
            else  
            {  
                g = 1;  
                x += 10;  
            }  
            c.s[c.len++] = x;  
        }  
        c.clean();  
        return c;  
    }  
    BigNum operator -= (const BigNum &b)  
    {  
        *this = *this - b;  
        return *this;  
    }  
    BigNum operator / (const BigNum &b)  
    {  
        BigNum c, f = 0;  
        for(int i = len-1; i >= 0; i--)  
        {  
            f = f*10;  
            f.s[0] = s[i];  
            while(f >= b)  
            {  
                f -= b;  
                c.s[i]++;  
            }  
        }  
        c.len = len;  
        c.clean();  
        return c;  
    }  
    BigNum operator /= (const BigNum &b)  
    {  
        *this  = *this / b;  
        return *this;  
    }  
    BigNum operator % (const BigNum &b)  
    {  
        BigNum r = *this / b;  
        r = *this - r*b;  
        return r;  
    }  
    BigNum operator %= (const BigNum &b)  
    {  
        *this = *this % b;  
        return *this;  
    }  
    bool operator < (const BigNum &b)  
    {  
        if(len != b.len) return len < b.len;  
        for(int i = len-1; i >= 0; i--)  
        {  
            if(s[i] != b.s[i]) return s[i] < b.s[i];  
        }  
        return false;  
    }  
    bool operator > (const BigNum &b)  
    {  
        if(len != b.len) return len > b.len;  
        for(int i = len-1; i >= 0; i--)  
        {  
            if(s[i] != b.s[i]) return s[i] > b.s[i];  
        }  
        return false;  
    }  
    bool operator == (const BigNum &b)  
    {  
        return !(*this > b) && !(*this < b);  
    }  
    bool operator != (const BigNum &b)  
    {  
        return !(*this == b);  
    }  
    bool operator <= (const BigNum &b)  
    {  
        return *this < b || *this == b;  
    }  
    bool operator >= (const BigNum &b)  
    {  
        return *this > b || *this == b;  
    }  
    string str() const  
    {  
        string res = "";  
        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;  
        return res;  
    }  
};  

istream& operator >> (istream &in, BigNum &x)  
{  
    string s;  
    in >> s;  
    x = s.c_str();  
    return in;  
}  

ostream& operator << (ostream &out, const BigNum &x)  
{  
    out << x.str();  
    return out;  
}