快速幂

1
2
3
4
5
6
7
8
9
int qpow(int a,int b,int mod){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}

离散化

1
2
3
4
5
inline int ID(int v) {return lower_bound(b+1,b+len+1,v)-b;}

for(int i=1;i<=n;i++) a[i]=b[i]=gin();
sort(b+1,b+n+1);
len=unique(b+1,b+n+1)-b-1;

ST表

1
2
3
4
5
6
7
8
9
10
11
int n,m,st[N][25],lg[N];

lg[0]=-1;
for(int i=1;i<=n;i++) st[i][0]=gin(),lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[n];j++) for(int i=1;i+(1<<j)-1<=n;i++)
    st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
while(m--) {
    int l=gin(),r=gin();
    int k=lg[r-l+1];
    printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void add(int x,int k) {
    while(x<=n) {
        c[x]+=k;
        x+=x&-x;
    }
}

inline int sum(int x) {
    int res=0;
    while(x) {
        res+=c[x];
        x-=x&-x;
    }
    return res;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void upd(int x,int l,int r,int pos,int d){
    if(l==r){
        sz[x]+=d;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) upd(ls,l,mid,pos,d);
    else upd(rs,mid+1,r,pos,d);
    pushup(x);
}

void clear(int x,int l,int r,int L,int R){
    if(l==r){
        sz[x]=0;
        return ;
    }
    int mid=l+r>>1;
    if(L<=mid) clear(ls,l,mid,L,R);
    if(R> mid) clear(rs,mid+1,r,L,R);
    pushup(x);
}

int ask(int x,int l,int r,int L,int R){
    if(l>R || r<L) return 0;
    if(L<=l&&r<=R) return sz[x];
    int mid=l+r>>1;
    return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
}

int kth(int x,int l,int r,int k){
    if(l==r) return l;
    int mid=l+r>>1,t=sz[rs];
    if(k<=t) return kth(rs,mid+1,r,k);
    else return kth(ls,l,mid,k-t);
}

可持久化

  • 数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int N=1e6+5;
int n,m,idx,a[N],val[N*25],ch[N*25][2],rt[N];

int build(int l,int r) {
    int x=++idx;
    if(l==r) {
        val[x]=a[l];
        return x;
    }
    int mid=l+r>>1;
    ch[x][0]=build(l,mid);
    ch[x][1]=build(mid+1,r);
    return x;
}

int upd(int pre,int l,int r,int pos,int d) {
    int x=++idx;
    ch[x][0]=ch[pre][0],ch[x][1]=ch[pre][1];
    if(l==r) {
        val[x]+=d;
        return x;
    }
    int mid=l+r>>1;
    if(pos<=mid) ch[x][0]=upd(ch[pre][0],l,mid,pos,d);
    else ch[x][1]=upd(ch[pre][1],mid+1,r,pos,d);
    return x;
}

int query(int x,int l,int r,int pos) {
    if(l==r) return val[x];
    int mid=l+r>>1;
    if(pos<=mid) return query(ch[x][0],l,mid,pos);
    else return query(ch[x][1],mid+1,r,pos);
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    n=gin(),m=gin();
    for(int i=1;i<=n;i++) a[i]=gin();
    rt[0]=build(1,n);
    for(int i=1;i<=m;i++) {
        int lst=gin(),op=gin(),x=gin();
        if(op==1) {
            int d=gin();
            rt[i]=upd(rt[lst],1,n,x,d);
        }
        else {
            rt[i]=rt[lst];
            printf("%d\n",query(rt[i],1,n,x));
        }
    }
    return 0;
}
  • 历史区间k大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int N=2e5+5;
int n,m,len,a[N],b[N],tot;
int lc[N<<5],rc[N<<5],rt[N],sum[N<<5];

inline int ID(int v) {return lower_bound(b+1,b+len+1,v)-b;}

int build(int l,int r) {
    int x=++tot;
    if(l==r) return x;
    int mid=l+r>>1;
    lc[x]=build(l,mid);
    rc[x]=build(mid+1,r);
    return x;
}

int upd(int root,int l,int r,int k) {
    int x=++tot;
    lc[x]=lc[root],rc[x]=rc[root],sum[x]=sum[root]+1;
    if(l==r) return x;
    int mid=l+r>>1;
    if(k<=mid) lc[x]=upd(lc[x],l,mid,k);
    else rc[x]=upd(rc[x],mid+1,r,k);
    return x;
}

int query(int u,int v,int l,int r,int k) {
    int mid=l+r>>1;
    int x=sum[lc[v]]-sum[lc[u]];
    if(l==r) return l;
    if(k<=x) return query(lc[u],lc[v],l,mid,k);
    else return query(rc[u],rc[v],mid+1,r,k-x);
}

signed main() {
    n=gin(),m=gin();
    for(int i=1;i<=n;i++) a[i]=b[i]=gin();
    sort(b+1,b+n+1);
    len=unique(b+1,b+n+1)-b-1;
    rt[0]=build(1,len);
    for(int i=1;i<=n;i++) rt[i]=upd(rt[i-1],1,len,ID(a[i]));
    while(m--) {
        int l=gin(),r=gin(),k=gin();
        printf("%d\n",b[query(rt[l-1],rt[r],1,len,k)]);
    }
    return 0;
}
  • 可持久化并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*
每次build和upd增加logn个结点
m次操作
空间O(mlogn)
*/

const int N=2e5+5;
int n,m,idx;
int fa[N*20],lc[N*20],rc[N*20],dep[N*20];
int rt[N];

int build(int l,int r){
    int x=++idx;
    if(l==r){
        fa[x]=l;
        return x;
    }
    int mid=l+r>>1;
    lc[x]=build(l,mid);
    rc[x]=build(mid+1,r);
    return x;
}

int upd(int val,int f,int l,int r,int root){
    int x=++idx;
    if(l==r){
        fa[x]=f;
        dep[x]=dep[root];
        return x;
    }
    lc[x]=lc[root],rc[x]=rc[root];
    int mid=l+r>>1;
    if(val<=mid)
        lc[x]=upd(val,f,l,mid,lc[root]);
    else rc[x]=upd(val,f,mid+1,r,rc[root]);
    return x;
}

int query(int x,int l,int r,int val){
    if(l==r) return x;
    int mid=l+r>>1;
    if(val<=mid)
        return query(lc[x],l,mid,val);
    else return query(rc[x],mid+1,r,val);
}

int find(int ban,int x){
    int f=query(ban,1,n,x);
    if(x==fa[f]) return f;
    return find(ban,fa[f]);
}

signed main(){
    n=gin(),m=gin();
    rt[0]=build(1,n);
    for(int i=1;i<=m;i++){
        int op=gin();
        if(op==1){
            rt[i]=rt[i-1];
            int a=gin(),b=gin();
            int u=find(rt[i],a),v=find(rt[i],b);
            if(fa[u]==fa[v]) continue;
            if(dep[u]>dep[v]) swap(u,v);
            rt[i]=upd(fa[u],fa[v],1,n,rt[i-1]);
            if(dep[u]==dep[v]) dep[v]++;
        }
        else if(op==2){
            int k=gin();
            rt[i]=rt[k];
        }
        else {
        	rt[i]=rt[i-1];
            int a=gin(),b=gin();
            int u=find(rt[i],a),v=find(rt[i],b);
            if(fa[u]==fa[v]) puts("1");
            else puts("0");
        }
    }
    return 0;
}

最短路

  • Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dijkstra(int s) {
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    priority_queue<pi> q;
    q.push({0,s});
    while(!q.empty()) {
        int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=ne[i]) {
            int v=to[i];
            if(dis[v]>dis[u]+we[i]) dis[v]=dis[u]+we[i],q.push({-dis[v],v});
        }
    }
}
  • spfa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void spfa(int s) {
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0,vis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=ne[i]) {
            int v=to[i];
            if(dis[v]>dis[u]+we[i]) {
                dis[v]=dis[u]+we[i];
                if(!vis[v]) q.push(v);
            }
        }
    }
}

最小生成树

  • Kruskal
1
2
3
4
5
6
7
8
9
10
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

void kruskal {
    for(int i=1;i<=m;i++) {
        int x=e[i].x,y=e[i].y;
        int fx=find(x),fy=find(y);
        if(fx==fy) continue;
        fa[x]=y; add(x,y),add(y,x);
    }
}

网络流

  • 最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
bool bfs() {
    for(int i=1;i<=n;i++) dis[i]=-1,cur[i]=head[i];
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=ne[i]) {
            int v=to[i];
            if(cap[i] && dis[v]==-1) dis[v]=dis[u]+1,q.push(v);
        }
    }
    return dis[t]!=-1;
}

int dfs(int u,int f) {
    if(u==t || f==0) return f;
    int flow=0,d;
    for(int& i=cur[u];i;i=ne[i]) {
        int v=to[i];
        if(dis[v]==dis[u]+1 && (d=dfs(v,min(f,cap[i])))) {
            flow+=d,f-=d,cap[i]-=d,cap[i^1]+=d;
            if(f==0) break;
        }
    }
    return flow;
}

ll maxflow(int s,int t) {
    ll flow=0;
    while(bfs()) flow+=dfs(s,inf);
    return flow;
}
  • 费用流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
bool spfa(int s,int t) {
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=ne[i]) {
            int v=to[i];
            if(cap[i] && dis[v]>dis[u]+cost[i]) {
                dis[v]=dis[u]+cost[i];
                if(!vis[v]) q.push(v);
            }
        }
    }
    return dis[t]!=inf;
}

int dfs(int u,int f) {
    if(u==t || f==0) return f;
    vis[u]=1;
    int flow=0,d;
    for(int i=head[u];i;i=ne[i]) {
        int v=to[i];
        if(!vis[v] && dis[v]==dis[u]+cost[i] && (d=dfs(v,min(f,cap[i])))) {
            flow+=d,f-=d,cap[i]-=d,cap[i^1]+=d,res+=d*cost[i];
            if(f==0) break;
        }
    }
    vis[u]=0;
    return flow;
}

ll mcmf(int s,int t) {
    ll flow=0;
    while(spfa(s,t)) flow+=dfs(s,inf);
    return flow;
}

连通性

  • 桥

(u,v)是桥 <=> $dfn[u]<low[v]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int tot=1;
bool bdg[N<<1];

void tarjan(int u,int e) {
    dfn[u]=low[u]=++dfc;
    for(int i=head[u];i;i=ne[i]) {
        v=to[i];
        if(!dfn[v]) {
            tarjan(v,i);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v]) bdg[i]=bdg[i^1]=1; //即桥的判定条件
        }
        else if(i!=(e^1)) low[u]=min(low[u],dfn[v]);
    }
}
  • 割点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool cut[N];

void tarjan(int u,int fa) {
    dfn[u]=low[u]=++dfc;
    int flg=0;
    for(int i=head[u];i;i=ne[i]) {
        int v=to[i];
        if(!dfn[v]) {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]) cut[u]=(u!=rt || ++flg>1); //即割点判定条件
        }
        else if(v!=fa) low[u]=min(low[u],dfn[v]);
    }
}
  • 强连通分量缩点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void tarjan(int u) {
    dfn[u]=low[u]=++dfc;
    st[++top]=u;
    for(int i=head[u];i;i=ne[i]) {
        int v=to[i];
        if(!dfn[v]) {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(!co[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]) {
        col++; int x;
        do {
            x=st[top--];
            co[x]=col;
            scc[col].push_back(x);
        } while(u!=x);
    }
}

signed main {
    ...

    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);

    for(int u=1;u<=n;u++) for(int i=head[u];i;i=ne[i]) {
    int v=to[i];
    if(co[u]==co[v]) continue;
    g[co[u]].push_back(co[v]);
}

    ...
    return 0;
}

树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int N=5e5+5;
int n,m,s,dep[N],fa[N],sz[N],son[N],top[N];
vector<int> g[N];

void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1;
    sz[u]=1;
    for(int v:g[u]) if(v!=f) {
        dfs1(v,u);
        if(sz[v]>sz[son[u]]) son[u]=v;
        sz[u]+=sz[v];
    }
}

void dfs2(int u,int topf) {
    top[u]=topf;
    if(son[u]) dfs2(son[u],topf);
    for(int v:g[u]) if(!top[v]) dfs2(v,v);
}

int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

signed main() {
    #ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    #endif
    n=gin(),m=gin(),s=gin();
    for(int i=1;i<n;i++) {
        int u=gin(),v=gin();
        g[u].push_back(v),g[v].push_back(u);
    }
    dfs1(s,0);
    dfs2(s,s);
    while(m--) {
        int u=gin(),v=gin();
        printf("%d\n",lca(u,v));
    }
    return 0;
}