【学习笔记】模板综合

有一些还没有写完呢qwq

这里是记录所有学过的模板的（好像还不会背啊）

Floyd

link

给出一张由 $n$ 个点 $m$ 条边组成的无向图。

求出所有点对 $(i,j)$ 之间的最短路径。

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
//Floyd
#include <bits/stdc++.h>
using namespace std;
int n,m,dis[110][110];
void floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		dis[u][v]=dis[v][u]=min(dis[u][v],w);
	}
	for(int i=1;i<=n;i++)dis[i][i]=0;
	floyd();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)printf("%d ",dis[i][j]);
		puts("");
	}
	return 0;
}

缩点

link

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

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
//缩点
#include <bits/stdc++.h>
using namespace std;
const int MAXN=10010,MAXM=100010;
int n,m;
pair <int,int> edge[MAXM];
vector <int> g[MAXN],g1[MAXN];
int dfn[MAXN],low[MAXN],idx,stk[MAXN],top,scc[MAXN],w[MAXN];
bool instk[MAXN];
int indeg[MAXN],dp[MAXN],ans;
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	stk[++top]=u;
	instk[u]=1;
	for(auto v:g[u])
	{
		if(!dfn[v])
			tarjan(v),low[u]=min(low[u],low[v]);
		else if(instk[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		do
		{
			instk[stk[top]]=0;
			scc[stk[top]]=u;
			if(stk[top]!=u)w[u]+=w[stk[top]];
		}while(stk[top--]!=u);
	}
}
void topo()
{
	queue <int> q;
	for(int i=1;i<=n;i++)
		if(i==scc[i]&&indeg[i]==0)
			q.push(i),dp[i]=w[i];
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(auto v:g1[u])
		{
			dp[v]=max(dp[v],dp[u]+w[v]);
			indeg[v]--;
			if(indeg[v]==0)q.push(v);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&edge[i].first,&edge[i].second);
		g[edge[i].first].push_back(edge[i].second);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=m;i++)
	{
		int u=scc[edge[i].first],v=scc[edge[i].second];
		if(u!=v)
			g1[u].push_back(v),indeg[v]++;
	}
	topo();
	for(int i=1;i<=n;i++)
		ans=max(ans,dp[i]);
	printf("%d",ans);
	return 0;
}

ST 表 & RMQ 问题

link

给定一个长度为 $N$ 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。

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
//ST表
#include <bits/stdc++.h>
using namespace std;
int lg[100010],f[100010][30],n,m;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main()
{
	n=read(),m=read();
	lg[1]=0;
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++)
		f[i][0]=read();
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=m;i++)
	{
		int l=read(),r=read(),k=lg[r-l+1];
		printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
	}
	return 0;
}

负环

link

给定一个 $n$ 个点的有向图，请求出图中是否存在从顶点 $1$ 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入的第一行是一个整数 $T$，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 $n$ 和接下来给出边信息的条数 $m$。

接下来 $m$ 行，每行三个整数 $u, v, w$。

  • 若 $w \geq 0$，则表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边，还存在一条从 $v$ 至 $u$ 边权为 $w$ 的边。
  • 若 $w < 0$，则只表示存在一条从 $u$ 至 $v$ 边权为 $w$ 的边。
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
//SPFA
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2010;
struct edge
{
	int v,w;
};
vector <edge> g[MAXN];
int cnt[MAXN],dis[MAXN],n,m;
bool inq[MAXN];
queue <int> q;
void spfa()
{
	while(!q.empty())q.pop();
	memset(cnt,0,sizeof(cnt));
	memset(dis,0x3f,sizeof(dis));
	memset(inq,0,sizeof(inq));
	dis[1]=0;
	inq[1]=1;
	cnt[1]=1;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(auto tmp:g[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				if(!inq[v])
				{
					cnt[v]++;
					if(cnt[v]>n)
					{
						puts("YES");
						return ;
					}
					q.push(v);
					inq[v]=1;
				}
			}
		}
	}
	puts("NO");
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)g[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back({v,w});
			if(w>=0)g[v].push_back({u,w});
		}
		spfa();
	}
}

快速幂

link

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//快速幂
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p;
int qpow(int a,int b)
{
	int ans=1,ba=a;
	while(b)
	{
		if(b&1)ans*=ba;
		ba*=ba;
		ans%=p,ba%=p;
		b>>=1;
	}
	return ans;
}
signed main()
{
	int a,b;
	cin>>a>>b>>p;
	printf("%d^%d mod %d=%d",a,b,p,qpow(a,b)%p);
	return 0;
}

并查集

link

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出 Y ；否则输出 N 。

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
//并查集
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5;
int f[MAXN],n,q;
void init()
{
	for(int i=1;i<=n;i++)
		f[i]=i;
}
int find(int i)
{
	if(f[i]==i)return i;
	return f[i]=find(f[i]);
}
void merge(int i,int j)
{
	f[find(j)]=find(i);
}
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),q=read();
	init();
	while(q--)
	{
		int z=read(),x=read(),y=read();
		if(z==1)merge(x,y);
		else 
			if(find(x)==find(y))printf("Y\n");
			else printf("N\n");
	}
}

割点

link

给出一个 $n$ 个点，$m$ 条边的无向图，求图的割点。

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
//割点
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20010;
int low[MAXN],dfn[MAXN],root,cnt,idx,n,m;
bool cut[MAXN];
vector <int> g[MAXN];
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	int son=0;
	for(auto v:g[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&root!=u)
			{
				cnt+=!cut[u];
				cut[u]=1;
			}
			if(u==root)son++;
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(u==root&&son>=2)
	{
		cnt+=!cut[u];
		cut[u]=1;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			root=i,tarjan(i);
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		if(cut[i])
			printf("%d ",i);
}

最小生成树

link

给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

prim

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
//最小生成树prim
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5010;
struct edge
{
	int v,w;
};
vector<edge> g[MAXN];
bool vis[MAXN];
int n,m,cnt,len,dis[MAXN];
int prim()
{
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	for(int i=1;i<=n;i++)
	{
		int now=-1,minn=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]<minn)
			{
				minn=dis[j];
				now=j;
			}
		}
		if(now==-1)return -1;
		vis[now]=1;
		len+=dis[now];
		cnt++;
		for(int j=0;j<g[now].size();j++)
		{
			int v=g[now][j].v,w=g[now][j].w;
			if(!vis[v]&&w<dis[v])
				dis[v]=w;
		}
	}
	return (cnt==n)?len:-1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back(edge{v,w});
		g[v].push_back(edge{u,w});
	}
	int res=prim();
	if(res==-1)cout<<"orz";
	else cout<<res;
}

kruscal

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
//最小生成树kruscal
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5010;
int f[MAXN],n,m,cnt,len;
struct edge
{
	int u,v,w;
}e[200010];
int find(int i)
{
	if(f[i]==i)return i;
	return f[i]=find(f[i]);
}
void merge(int i,int j)
{
	f[find(j)]=find(i);
}
bool cmp(edge a,edge b)
{
	return a.w<b.w;//!
}
int kruscal()
{
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu==fv)continue;
		merge(e[i].u,e[i].v);
		cnt++;
		len+=e[i].w;
		if(cnt==n-1)return len;
	}
	return -1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[i]=(edge){u,v,w};
	}
	int res=kruscal();
	if(res==-1)cout<<"orz";
	else cout<<len;
	return 0;
}

单源最短路径

lnk

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

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
//单源最短路径
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10010;
struct edge
{
	int v,w;
};
vector <edge> g[MAXN];
struct node
{
	int u,dis;
	bool operator <(const node a)const
	{
		return dis>a.dis;
	}
};
priority_queue <node> q;
int dis[MAXN],n,m,s;
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push((node){s,0});
	while(!q.empty())
	{
		node front=q.top();
		int u=front.u;
		q.pop();
		if(dis[u]!=front.dis)continue;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].v,w=g[u][i].w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push((node){v,dis[v]});
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++)
		if(dis[i]==0x3f3f3f3f)cout<<INT_MAX<<" ";
		else cout<<dis[i]<<" ";
	return 0;
}

LCA

lnk

给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

倍增

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
//倍增LCA
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
const int MAXLOG=25;
int de[MAXN],anc[MAXN][MAXLOG];
vector <int> g[MAXN];
void dfs(int x,int fa)
{
	de[x]=de[fa]+1;
	anc[x][0]=fa;
	for(int i=1;i<MAXLOG;i++)anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++)
	{
		if(g[x][i]!=fa)dfs(g[x][i],x);
	}
}
int lca(int x,int y)
{
	if(de[x]<de[y])swap(x,y);
	for(int i=MAXLOG-1;~i;i--)
	{
		if(de[anc[x][i]]>=de[y])x=anc[x][i];
	}
	if(x==y)return x;
	for(int i=MAXLOG-1;~i;i--)
	{
		if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
	}
	return anc[x][0];
}
int main()
{
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(s,s);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
}

tarjan

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
//tarjan LCA
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int f[MAXN],vis[MAXN],ans[MAXN];
vector <int> g[MAXN];
vector <int> query[MAXN],query_id[MAXN];
int find(int i)
{
	if(f[i]==i)return i;
	return f[i]=find(f[i]);
}
void tarjan(int u)
{
	vis[u]=1;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v])continue;
		tarjan(v);
		f[v]=u;
	}
	for(int i=0;i<query[u].size();i++)
	{
		int v=query[u][i],id=query_id[u][i];
		if(u==v)ans[id]=u;
		if(vis[v]==2)ans[id]=find(v);
	}
	vis[u]=2;
}
int main()
{
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		query[u].push_back(v);
		query[v].push_back(u);
		query_id[u].push_back(i);
		query_id[v].push_back(i);
	}
	tarjan(s);
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}

topo排序

lnk

给出一个DAG，从入读为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
//topo sort
#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[110];
vector <int> g[110];
void dfs(int u)
{
	for(int i=0;i<g[u].size();i++)
		if(!vis[g[u][i]])
			dfs(g[u][i]);
	vis[u]=1;
	cout<<u<<" ";
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int tmp;
		while(cin>>tmp&&tmp)
			g[tmp].push_back(i);
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i);
}

线段树

区间修改（加、乘）、区间查询（和）

link

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//区间修改（加、乘）、区间查询（和）
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int MAXN=1000010;
ll n,q,m,a[MAXN],sum[MAXN<<2],mul_tag[MAXN<<2],add_tag[MAXN<<2];
inline ll ls(int k)
{
	return k<<1;
}
inline ll rs(int k)
{
	return k<<1|1;
}
inline void pushup(ll k)
{
	sum[k]=(sum[ls(k)]+sum[rs(k)])%m;
}
void build(ll l,ll r,ll k)
{
	mul_tag[k]=1;
	add_tag[k]=0;
	if(l==r)
	{
		sum[k]=a[l]%m;
		return;
	}
	ll mid=l+((r-l)>>1);
	build(l,mid,ls(k));
	build(mid+1,r,rs(k));
	pushup(k);
}
inline void pushdown(ll l,ll r,ll k)
{
	ll mid=(l+r)>>1;
	sum[ls(k)]=(sum[ls(k)]*mul_tag[k]+add_tag[k]*(mid-l+1))%m;
	mul_tag[ls(k)]=(mul_tag[ls(k)]*mul_tag[k])%m;
	add_tag[ls(k)]=(add_tag[ls(k)]*mul_tag[k]+add_tag[k])%m;
	sum[rs(k)]=(sum[rs(k)]*mul_tag[k]+add_tag[k]*(r-mid))%m;
	mul_tag[rs(k)]=(mul_tag[rs(k)]*mul_tag[k])%m;
	add_tag[rs(k)]=(add_tag[rs(k)]*mul_tag[k]+add_tag[k])%m;
	mul_tag[k]=1;
	add_tag[k]=0;
}
void update_mul(ll nl,ll nr,ll l,ll r,ll k,ll val)
{
	if(nl<=l&&nr>=r)
	{
		sum[k]=(sum[k]*val)%m;
		mul_tag[k]=(mul_tag[k]*val)%m;
		add_tag[k]=(add_tag[k]*val)%m;
		return;
	}
	pushdown(l,r,k);
	ll mid=l+((r-l)>>1);
	if(nl<=mid)update_mul(nl,nr,l,mid,ls(k),val);
	if(nr>mid)update_mul(nl,nr,mid+1,r,rs(k),val);
	pushup(k);
}
void update_add(ll nl,ll nr,ll l,ll r,ll k,ll val)
{
	if(nl<=l&&nr>=r)
	{
		sum[k]=(sum[k]+val*(r-l+1))%m;
		add_tag[k]=(add_tag[k]+val)%m;
		return;
	}
	pushdown(l,r,k);
	ll mid=l+((r-l)>>1);
	if(nl<=mid)update_add(nl,nr,l,mid,ls(k),val);
	if(nr>mid)update_add(nl,nr,mid+1,r,rs(k),val);
	pushup(k);
}
ll query(ll ql,ll qr,ll l,ll r,ll k)
{
	if(ql<=l&&qr>=r)return sum[k];
	pushdown(l,r,k);
	ll mid=(l+r)>>1,res=0;
	if(ql<=mid)res=(res+query(ql,qr,l,mid,ls(k)))%m;
	if(qr>mid)res=(res+query(ql,qr,mid+1,r,rs(k)))%m;
	return res;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]%=m;
	}
	build(1,n,1);
	while(q--)
	{
		int opt;
		cin>>opt;
		ll x,y,k;
		switch(opt)
		{
			case 1:
				cin>>x>>y>>k;
				k%=m;
				update_mul(x,y,1,n,1,k);
				break;
			case 2:
				cin>>x>>y>>k;
				k%=m;
				update_add(x,y,1,n,1,k);
				break;
			case 3:
				cin>>x>>y;
				cout<<query(x,y,1,n,1)%m<<'\n';
				break;
		}
	}
}

区间修改（加）、区间查询（和）

link

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
81
82
83
84
85
86
87
88
89
90
91
//区间修改（加）、区间查询（和）
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
typedef unsigned long long ll;
ll n,m,a[MAXN],sum[MAXN<<2],tag[MAXN<<2];
inline ll ls(int k)
{
	return k<<1;
}
inline ll rs(int k)
{
	return k<<1|1;
}
inline void pushup(ll k)
{
	sum[k]=sum[ls(k)]+sum[rs(k)];
}
void build(ll l,ll r,ll k)
{
	tag[k]=0;
	if(l==r)
	{
		sum[k]=a[l];
		return ;
	}
	ll mid=l+((r-l)>>1);
	build(l,mid,ls(k));
	build(mid+1,r,rs(k));
	pushup(k);
}
inline void f(ll l,ll r,ll k,ll val)
{
	tag[k]+=val;
	sum[k]+=val*(r-l+1);
}
inline void pushdown(ll l,ll r,ll k)
{
	ll mid=(l+r)>>1;
	f(l,mid,ls(k),tag[k]);
	f(mid+1,r,rs(k),tag[k]);
	tag[k]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll k,ll add)
{
	if(nl<=l&&nr>=r)
	{
		sum[k]+=add*(r-l+1);
		tag[k]+=add;
		return ;
	}
	pushdown(l,r,k);
	ll mid=l+((r-l)>>1);
	if(nl<=mid)update(nl,nr,l,mid,ls(k),add);
	if(nr>mid)update(nl,nr,mid+1,r,rs(k),add);
	pushup(k);
}
inline ll query(ll ql,ll qr,ll l,ll r,ll k)
{
	ll res=0;
	if(ql<=l&&qr>=r)return sum[k];
	pushdown(l,r,k);
	ll mid=(l+r)>>1;
	if(ql<=mid)res+=query(ql,qr,l,mid,ls(k));
	if(qr>mid)res+=query(ql,qr,mid+1,r,rs(k));
	return res;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n,1);
	while(m--)
	{
		int opt;
		cin>>opt;
		ll x,y,k;
		switch(opt)
		{
			case 1:
				cin>>x>>y>>k;
				update(x,y,1,n,1,k);
				break;
			case 2:
				cin>>x>>y;
				cout<<query(x,y,1,n,1)<<'\n';
				break;
		}
	}
	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
//单点修改（加），区间查询（和）
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int n,a[MAXN],q;
int lowbit(int x)
{
	return x&(-x);
}
struct treearray
{
	int c[MAXN];
	void add(int u,int val)
	{
		a[u]+=val;
		for(int i=u;i<=n;i+=lowbit(i))
			c[i]+=val;
	}
	int sum(int u)
	{
		int ans=0;
		for(int i=u;i>0;i-=lowbit(i))
			ans+=c[i];
		return ans;
	}
	void init()
	{
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;i++)
		{
			c[i]+=a[i];
			int j=i+lowbit(i);
			if(j<=n)
				c[j]+=c[i];
		}
	}
}t;
int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	t.init();
	while(q--)
	{
		int opt,u,v;
		cin>>opt>>u>>v;
		if(opt==1)
			t.add(u,v);
		else
			cout<<t.sum(v)-t.sum(u-1)<<'\n';
	}
	return 0;
}

区间修改（加），单点查询（值）

lnk

咕着

字典树

lnk

给定 $n$ 个模式串 $s_1, s_2, \dots, s_n$ 和 $q$ 次询问，每次询问给定一个文本串 $t_i$，请回答 $s_1 \sim s_n$ 中有多少个字符串 $s_j$ 满足 $t_i$ 是 $s_j$ 的前缀。

一个字符串 $t$ 是 $s$ 的前缀当且仅当从 $s$ 的末尾删去若干个（可以为 0 个）连续的字符后与 $t$ 相同。

输入的字符串大小敏感。例如，字符串 Fusu 和字符串 fusu 不同。

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
//字典树
#include<bits/stdc++.h>
using namespace std;
int n,m,idx,cnt[3000010],trie[3000010][65];
map <char,int> mp;
void insert(char *s)
{
	int p=0,len=strlen(s+1);
	for(int i=1;i<=len;i++)
	{
		if(!trie[p][mp[s[i]]])
			trie[p][mp[s[i]]]=++idx;
		p=trie[p][mp[s[i]]],cnt[p]++;
	}
}
int query(char *s)
{
	int p=0,len=strlen(s+1);
	for(int i=1;i<=len;i++)
	{
		if(!trie[p][mp[s[i]]])return 0;
		p=trie[p][mp[s[i]]];
	}
	return cnt[p];
}
char s[3000010];
signed main()
{
	int id=0,t;
	cin>>t;
	for(char i='a';i<='z';i++)mp[i]=++id;
	for(char i='A';i<='Z';i++)mp[i]=++id;
	for(char i='0';i<='9';i++)mp[i]=++id;
	while(t--)
	{
		cin>>n>>m;
		for(int i=0;i<=idx;i++)
		{
			cnt[i]=0;
			for(int j=0;j<=62;j++)
			 	trie[i][j]=0;
		}
		idx=0;
		for(int i=1;i<=n;i++)
		{
			cin>>(s+1);
			insert(s);
		}
		for(int i=1;i<=m;i++)
		{
			cin>>(s+1);
			cout<<query(s)<<'\n';
		}
	}
}

滑动窗口/单调队列

lnk

有一个长为 $n$ 的序列 $a$，以及一个大小为 $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
//单调队列
#include <bits/stdc++.h>
using namespace std;
int n,k;
int maxn[1000010],minn[1000010],a[1000010];
int head1=1,tail1,head2=1,tail2;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        while(head2<=tail2&&a[minn[tail2]]>=a[i])tail2--;
        tail2++,minn[tail2]=i;
        while(i-minn[head2]>=k)head2++;
        if(i>=k)cout<<a[minn[head2]]<<" ";
    }putchar('\n');
    for(int i=1;i<=n;i++)
    {
        while(head1<=tail1&&a[maxn[tail1]]<=a[i])tail1--;
        tail1++,maxn[tail1]=i;
        while(i-maxn[head1]>=k)head1++;
        if(i>=k)cout<<a[maxn[head1]]<<" ";
    }
}

强连通分量

lnk

给定一张 $n$ 个点 $m$ 条边的有向图，求出其所有的强连通分量。

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
//强连通分量
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
vector<int> g[MAXN],ans[MAXN];
int n,m,cnt,f[MAXN],b[MAXN],s[MAXN],len,dfn[MAXN],low[MAXN],idx;
bool instack[MAXN];
void tarjan(int u)
{
	dfn[u]=low[u]=++idx;
	s[++len]=u;
	instack[u]=1;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		cnt++;
		while(s[len]!=u)
		{
			b[s[len]]=cnt;
			instack[s[len]]=0;
			ans[cnt].push_back(s[len]);
			len--;
		}
		b[u]=cnt;
		ans[cnt].push_back(u);
		len--;
		instack[u]=0;
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++)sort(ans[i].begin(),ans[i].end());
	for(int i=1;i<=n;i++)
	{
		if(f[b[i]])continue;
		f[b[i]]=1;
		for(int j=0;j<ans[b[i]].size();j++)printf("%d ",ans[b[i]][j]);
		cout<<endl;
	}
	return 0;
}

边双连通分量

lnk

对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。

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
//边双
#include<bits/stdc++.h> 
using namespace std;
struct e
{
	int next,to;
	bool f;
}edge[4000005];
int idx,cnt=1,dcc,n,m,low[2000005],dfn[2000005],head[2000005];
bool vis[2000005];
vector<int>d[2000005];
void add_edge(int u,int v)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].f=false;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void tarjan(int x,int in)
{
	dfn[x]=low[x]=++idx;
	for(int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(!dfn[y])
		{
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y])edge[i].f=edge[i^1].f=true;
		}
		else if(i!=(in^1))low[x]=min(low[x],dfn[y]);
	} 
}
void dfs(int x)
{
	d[dcc].push_back(x); vis[x]=true;
	for(int i=head[x];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(vis[v]||edge[i].f)continue;
		dfs(v);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			dcc++;
			dfs(i);
		}
	}
	printf("%d\n",dcc);
	for(int i=1;i<=dcc;i++)
	{
		printf("%d ",d[i].size());
		for(int j=0;j<d[i].size();j++)printf("%d ",d[i][j]);
		puts("");
	}
	return 0;
}

点双连通分量

lnk

对于一个 $n$ 个节点 $m$ 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

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
//点双
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int low[MAXN],dfn[MAXN],stk[MAXN];
int n,m,idx,cnt,top;
vector <int> g[MAXN],ans[MAXN];
void tarjan(int u,int fa)
{
	int son=0;
	low[u]=dfn[u]=++idx;
	stk[++top]=u;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(!dfn[v])
		{
			son++;
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				cnt++;
				while(stk[top+1]!=v)
					ans[cnt].push_back(stk[top--]);
				ans[cnt].push_back(u);
			}
		}
		else if(v!=fa)low[u]=min(low[u],dfn[v]);
	}
	if(fa==0&&son==0)
		ans[++cnt].push_back(u);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i])continue;
		top=0;
		tarjan(i,0);
	}
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++)
	{
		printf("%d ",ans[i].size());
		for(auto v:ans[i])printf("%d ",v);
		putchar('\n');
	}
	return 0;
}

线性筛

lnk

如题，给定一个范围 $n$，有 $q$个询问，每次输出第 $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
//线性筛
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8+10;
const int MAXP=6e6+10;
int n,q,cnt=0;
int prime[MAXP];
bool isprime[MAXN];
void getprime()
{
    memset(isprime,true,sizeof(isprime));
    isprime[1]=false;
    for(int i=2;i<=n;++i)
    {
        if(isprime[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    getprime();
    while(q--)
    {
        int k;
        cin>>k;
        cout<<prime[k]<<'\n';
    }
    return 0;
}

KMP

lnk

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
//kmp
#include<bits/stdc++.h>
using namespace std;
char s[100010],t[100010];
int j;
int kmp[100010];
int main()
{
	cin>>s+1>>t+1;
	int ls=strlen(s+1),lt=strlen(t+1);
	for(int i=2;i<=lt;i++)
	{
		while(j&&t[i]!=t[j+1])j=kmp[j];
		if(t[j+1]==t[i])j++;
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=ls;i++)
	{
		while(j>0&&t[j+1]!=s[i])j=kmp[j];
		if(t[j+1]==s[i])j++;
		if(j==lt)
		{
			cout<<i-lt+1<<'\n';
			j=kmp[j];
		}
	}
	for(int i=1;i<=lt;i++)cout<<kmp[i]<<" ";
	return 0;
}
学习笔记
#Floyd #tarjan #ST表 #SPFA #快速幂 #并查集 #最小生成树 #最短路 #LCA #拓扑排序 #线段树 #树状数组 #字典树 #单调队列 #线性筛 #kmp
【学习笔记】模板综合
http://j27egu.github.io/2025/09/24/【学习笔记】模板综合/
作者
j27eGU
发布于
2025年9月24日
许可协议