学习笔记

发布日期: 2022-05-24

更新日期: 2022-07-11

文章字数: 6.5k

阅读次数:

算法模板

1. 链式前向星

#include<iostream>

using namespace std;

int n,m,u,v,tot,head[1001];
bool vis[1001];

struct edge{
	int u,v,next;
}g[1001];

void addedge(int u,int v){
	g[++tot].u=u;
	g[tot].v=v;
	g[tot].next=head[u];
	head[u]=tot;
}

void dfs(int u){
	cout<<u<<" ";
	vis[u]=true;
	for(int i=head[u];i!=-1;i=g[i].next){
		int v=g[i].v;
		if(!vis[v]) dfs(v);
	}
}

int main(){
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;++i){
		cin>>u>>v;
		addedge(u,v);
//		addedge(v,u);
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]) dfs(i);
	}
	return 0;
}

2. 拓扑排序

#include<iostream>//拓扑排序 
#include<vector>
#include<queue>

using namespace std;

int n,m,in[1001];
//in[i]:点i的入度 

vector<int> g[1001];

void tpsort(){//拓扑排序函数 
	queue<int> q;
	for(int i=1;i<=n;++i) 
		if(!in[i]) q.push(i);//将入度为0的点加入queue 
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<g[u].size();++i){//删边 
			int v=g[u][i];
			--in[v];
        if(!in[v]) q.push(v);
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		++in[v];
		g[u].push_back(v);
	}
	tpsort();
	return 0;
}

3. 拓扑排序+判环

#include<iostream>//拓扑排序 
#include<vector>
#include<queue>

using namespace std;

int n,m,in[1001],cnt=0,a[1001];
//in[i]:点i的入度 

vector<int> g[1001];

void tpsort(){//拓扑排序函数 
	queue<int> q;
	for(int i=1;i<=n;++i) 
		if(!in[i]) q.push(i);//将入度为0的点加入queue 
	while(!q.empty()){
		int u=q.front();
		a[++cnt]=u;
		q.pop();
		for(int i=0;i<g[u].size();++i){//删边 
			int v=g[u][i];
			--in[v];
			if(!in[v]) q.push(v); 
		}
	}
	if(cnt==n){
		for(int i=1;i<=cnt;++i) cout<<a[i]<<" ";
	} else {
		cout<<"It has circle."<<endl;
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		++in[v];
		g[u].push_back(v);
	}
	tpsort();
	return 0;
}

4. 普通 $\operatorname{Dijkstra}$：输出 $1$ 到 $n$ 的最短路

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;

struct edge{
	int v,w;
};

int n,m,dis[maxn];
bool vis[maxn];
vector<edge> g[maxn];

void dijkstra(int s){
	memset(dis,inf,sizeof dis);
	dis[1]=0;
	for(int i=1;i<=n;++i){
		int t=d[0],u=0;
		for(int v=1;v<=n;++v){
			if(!vis[v]&&(u==0||dis[u]>dis[v])){
				t=dis[v];
				u=v;
			}
		}
		vis[u]=true;
		for(int j=0;j<(int)g[u].size();++j){
			int v=g[u][j].v;
			int w=g[u][j].w;
			if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((edge{v,w}));
	}
	Dijkstra(1);
	cout<<dis[n]<<endl;
	return 0;
}

5. 普通 $\operatorname{Dijkstra}2$：输出 $s$ 到其他所有点的最短路

#include<iostream>
#include<vector>

using namespace std;

const int maxn=1e5+10;
const int inf=0x3f3f3f3f;

struct edge{
	int v,w;
};

int n,m,s,dis[maxn];
bool vis[maxn];
vector<edge> g[maxn];

void Dijkstra(int s){
	for(int i=1;i<=n;++i){
		vis[i]=false;
		dis[i]=inf;
	}
	dis[s]=0;
	for(int i=1;i<=n;++i){
		int u=0;
		for(int v=1;v<=n;++v){
			if(!vis[v]&&(u==0||dis[u]>dis[v])){
				u=v;
			}
		}
		vis[u]=true;
		for(int j=0;j<(int)g[u].size();++j){
			int v=g[u][j].v;
			int w=g[u][j].w;
			if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
		}
	}
}

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(s);
	for(int i=1;i<=n;++i){
		if(dis[i]==inf) cout<<2147483647<<' ';
		else cout<<dis[i]<<' ';
	}
	return 0;
}

6. $\operatorname{Dijkstra}$：堆优化

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef long long ll;

const ll maxn=2e5+10;
const ll inf=0x3f3f3f3f3f3f3f3f;

struct edge{
	ll v,w;
};

struct node{
	ll u,dis;
	bool operator <(const node &n) const{
		return dis>n.dis;
	}
};

ll n,m,dis[maxn];
bool vis[maxn];
vector<edge> g[maxn];

void Dijkstra(ll s){
	priority_queue<node> q;
	for(ll i=1;i<=n;++i){
		vis[i]=false;
		dis[i]=inf;
	}
	dis[1]=0;
	q.push((node){s,dis[s]});
	while(!q.empty()){
		node no=q.top();
		q.pop();
		ll u=no.u,d=no.dis;
		if(vis[u]) continue;
		vis[u]=true;
		for(ll j=0;j<(ll)g[u].size();++j){
			ll v=g[u][j].v;
			ll w=g[u][j].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push((node){v,dis[v]});
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(ll i=1;i<=m;++i){
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
	}
	Dijkstra(1);
	cout<<dis[n]<<endl;
	return 0;
}

7. 已经死了的 $\operatorname{SPFA}$

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

struct edge{
	int v,w;
};
vector<edge> g[10001];
queue<int> q;
int n,m,d[10001];
bool inq[10001];

void spfa(int s){
	memset(d,127,sizeof d);
	d[s]=0;
	q.push(s);
	inq[s]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=0;i<g[u].size();++i){
			int v=g[u][i].v;
			int w=g[u][i].w;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!inq[v]){
					q.push(v);
					inq[v]=true;
				}
			}
		}
	}
}

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

8. $\operatorname{SPFA}$ 判断负环

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

struct edge{
	int v,w;
};
vector<edge> g[10001];
queue<int> q;
int n,m,d[10001],cnt[10001];
bool inq[10001];

bool spfa(int s){//判断负环 
	memset(d,127,sizeof d);
	d[s]=0;
	q.push(s);
	inq[s]=true;
	++cnt[s];
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=false;
		for(int i=0;i<g[u].size();++i){
			int v=g[u][i].v;
			int w=g[u][i].w;
			if(d[u]+w<d[v]){
				d[v]=d[u]+w;
				if(!inq[v]){
					q.push(v);
					++cnt[v];
					inq[v]=true;
					if(cnt[v]>=n) return true;
				}
			}
		}
	}
	return false;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
	}
	if(spfa(1)) cout<<"Has circle."<<endl;
	else cout<<"Doesn't have circle."<<endl;
	return 0;
}

9. $\operatorname{Floyd}$

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<cstring>
 
using namespace std;
 
const int maxn=310;
const int inf=0x3f3f3f3f;
int n,m,cnt=0;
int d[maxn][maxn];

map<string,int> mp;

void Floyd(){
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
            }
        }
    }
}
 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			d[i][j]=inf;
		}
		d[i][i]=0;
	}
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		d[u][v]=w;
	}
	Floyd();
	return 0;
}

10. $\operatorname{Floyd}$ 输出路径

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<cstring>
 
using namespace std;
 
const int maxn=310;
const int inf=0x3f3f3f3f;
int n,m,cnt=0,q;
int d[maxn][maxn],path[maxn][maxn];

map<string,int> mp;

void Floyd(){
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
            	if(d[i][k]+d[k][j]<d[i][j]){
                	d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
                	path[i][j]=k;
				}
            }
        }
    }
}

void print(int s,int t){
	if(s==t)return;
	if(path[s][t]==0) printf("%d ",s);
	else{
		print(s,path[s][t]);
		print(path[s][t],t);
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			d[i][j]=inf;
		}
		d[i][i]=0;
	}
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		d[u][v]=w;
		path[u][v]=0;
	}
	Floyd();
	for(int i=1;i<=q;++i){
		int a,b;
		scanf("%d%d",&a,&b);
		print(a,b);
		printf("%d\n",b);
	}
	return 0;
}

11. $\operatorname{Hierholzer}$ 输出欧拉路径

#include<iostream>
#include<stack>

using namespace std;

int g[1001][1001],n,m;
stack<int> s;

void Hierholzer(int u){
	for(int i=lb;i<=rb;++i){
		if(g[u][i]){
			g[u][i]--;
			g[i][u]--;
			Hierholzer(i);
		}
	}
	s.push(u);
}

int main(){
	啥也没有
	return 0;
}

12. $\operatorname{Tarjan}$：强连通分量

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<stack>
 
using namespace std;
 
const int maxn=1e4+10;
int n,m,dfn[maxn],low[maxn],scc[maxn],idx=0,c,ans=0;
bool inStack[maxn];
 
vector<int> G[maxn];
stack<int> s;
 
void tarjan(int u) {
    dfn[u]=low[u]=++idx;
    s.push(u);
    inStack[u]=true;
    for(int i=0; i<G[u].size(); i++) {
        int v=G[u][i];
        if(dfn[v]==-1) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else {
            if(inStack[v]==true) {
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(dfn[u]==low[u]) {
        c++;
        int v;
        do {
            v=s.top();
            s.pop();
            scc[v]=c;
            inStack[v]=false;
        } while(u!=v);
    }
}
 
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
    }
    memset(dfn,-1,sizeof dfn);
    for(int i=1;i<=n;++i){
        if(dfn[i]==-1){
            tarjan(i);
        }
    }
    for(int i=1;i<=idx;i++){
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(scc[j]==i) ++cnt;
        }
        if(cnt>1) ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

13. 查找一个图的割点

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<string>
 
using namespace std;
 
int n,dfn[1001],low[1001],idx;
bool iscp[1001],cnt[1001],vis[1001];
vector<int> G[1001];
 
void find_CutPoint(int u,int fa){
    int child=0;
    dfn[u]=low[u]=++idx;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!dfn[v]){
            ++child;
            find_CutPoint(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) iscp[u]=true;
        } else {
            if(dfn[v]<dfn[u]&&v!=fa){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
    if(fa<0&child==1) iscp[u]=false;
}
 
int main(){
    //iscp[i]记录的是i是不是割点 
    return 0;
}

14. 查找桥（无重边）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<string>
#include<stack>//头文件似乎多了亿点点 
 
using namespace std;
 
int n,dfn[1001],low[1001],idx;
bool iscp[1001],cnt[1001],vis[1001];
vector<int> G[1001];

struct edge{
	int u,v;
};
stack<edge> st;
 
void find_Bridge(int u,int fa){
    int child=0;
    dfn[u]=low[u]=++idx;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!dfn[v]){
            ++child;
            find_CutPoint(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) st.push((edge){u,v});
        } else {
            if(dfn[v]<dfn[u]&&v!=fa){
                low[u]=min(low[u],dfn[v]);
            }
        }
    }
}
 
int main(){
    //栈里面存的是桥,注意:不能有重边!!! 
    return 0;
}

15. $\operatorname{Kruskal}$

#include<cstdio>
#include<algorithm>

using namespace std;

struct edge{
	int u,v,w;
	bool operator <(edge e) const{
		return w<e.w;
	}
}a[10001];

int n,m,ans,f[10001],cnt=0;

int find(int u){
	if(f[u]==u)return u;
	return f[u]=find(f[u]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
	for(int i=1;i<=n;i++) f[i]=i;
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++){
		int fu=find(a[i].u);
		int fv=find(a[i].v);
		if(fu!=fv){
			f[fu]=fv;
			ans+=a[i].w;
			++cnt;
		}
		if(cnt==n-1) break;
	}
	printf("%d\n",ans);
}

16. $\operatorname{Prim}$

#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;
int g[1001][1001],d[1001],n,m,ans=0;
bool vis[1001];

void prim(int s){
	memset(d,inf,sizeof(d));
	d[s]=0;
	for(int i=1;i<=n;i++){
		if(i==s) continue;
		int x=0;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&d[j]<d[x]) x=j;
		}
		vis[x]=true;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&g[x][j]<d[j]) d[j]=g[x][j];
		}
	}
}

int main(){
	memset(g,inf,sizeof(g));
	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][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	prim(1);
	for(int i=1;i<=n;i++) ans+=d[i];
	printf("%d\n",ans);
}

17. $\operatorname{Prim}$ 堆优化

#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;
int g[1001][1001],d[1001],n,m,ans=0;
bool vis[1001];

struct point{
	int id,d;
	bool operator <(point v) const{
		return d>v.d;
	}
};
priority_queue<point> q;

void prim(int s){
	memset(d,inf,sizeof(d));
	d[s]=0;
	q.push((point){s,d[s]});
	for(int i=1;i<=n;i++){
		if(i==s) continue;
		int x=q.top().id;
		q.pop();
		vis[x]=true;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&g[x][j]<d[j]){
				d[j]=g[x][j];
				q.push((point){j,d[j]});
			}
		}
	}
}


int main(){
	memset(g,inf,sizeof(g));
	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][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	prim(1);
	for(int i=1;i<=n;i++) ans+=d[i];
	printf("%d\n",ans);
}

18. 线段树：点修改，求最小值

#include<algorithm>
#include<cstdio>

using namespace std;

const int maxn=1e5+1;
const int infinity=0x3f3f3f3f;

int m,n,a[maxn],minv[maxn*4];

void update(int o,int l,int r,int x,int d){
	if(l==r){
		minv[o]=d;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update(o<<1,l,mid,x,d);
	else update((o<<1)+1,mid+1,r,x,d);
	minv[o]=min(minv[o<<1],minv[(o<<1)+1]);
}

int query(int o,int l,int r,int x,int y){
	if(x>r||y<l) return infinity;
	if(x<=l&&r<=y) return minv[o];
	int mid=l+r>>1;
	int v1=query(o<<1,l,mid,x,y);
	int v2=query((o<<1)+1,mid+1,r,x,y);
	return min(v1,v2); 
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		update(1,1,n,i,a[i]);
	}
	for(int i=1;i<=m;++i){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) printf("%d\n",query(1,1,n,x,y));
		else update(1,1,n,x,y);
	}
	putchar('\n');
	return 0;
}

19. 线段树：点修改，求最大子段和

#include<algorithm>
#include<cstdio>

using namespace std;

const int maxn=5e5+1;
const int infinity=0x3f3f3f3f;

int m,n;

struct segment{
	int sum,lmx,rmx,mx;
}a[maxn*4];

void update(int o,int l,int r,int x,int d){
	if(l==r){
		a[o].sum=a[o].lmx=a[o].rmx=a[o].mx=d;
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) update(o<<1,l,mid,x,d);
	else update((o<<1)+1,mid+1,r,x,d);
	a[o].sum=a[o<<1].sum+a[(o<<1)+1].sum;
	a[o].lmx=max(a[o<<1].lmx,a[o<<1].sum+a[(o<<1)+1].lmx);
	a[o].rmx=max(a[(o<<1)+1].rmx,a[(o<<1)+1].sum+a[o<<1].rmx);
	a[o].mx=max(max(a[o<<1].mx,a[(o<<1)+1].mx),a[o<<1].rmx+a[(o<<1)+1].lmx);
}

segment query(int o,int l,int r,int x,int y){
	if(x<=l&&r<=y) return a[o];
	int mid=l+r>>1;
	if(y<=mid) return query(o<<1,l,mid,x,y);
	else if(x>mid) return query((o<<1)+1,mid+1,r,x,y);
	else {
		segment lef=query(o<<1,l,mid,x,y);
		segment rig=query((o<<1)+1,mid+1,r,x,y);
		segment ret;
		ret.sum=lef.sum+rig.sum;
		ret.lmx=max(lef.lmx,lef.sum+rig.lmx);
		ret.rmx=max(rig.rmx,rig.sum+lef.rmx);
		ret.mx=max(max(lef.mx,rig.mx),lef.rmx+rig.lmx);
		return ret;
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		int x;
		scanf("%d",&x);
		update(1,1,n,i,x);
	}
	for(int i=1;i<=m;++i){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1){
			if(x>y) swap(x,y);
			printf("%d\n",query(1,1,n,x,y).mx);
		}
		else update(1,1,n,x,y);
	}
	putchar('\n');
	return 0;
}

20. 线段树：区间修改，求区间和

#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e5+1;
int n,m;
struct segment{
	int sum,lazy;
}t[4*maxn];
inline void downtag(int o,int l,int r,int mid){
	t[o<<1].sum+=t[o].lazy*(mid-l+1);
	t[o<<1|1].sum+=t[o].lazy*(r-mid);
	t[o<<1].lazy+=t[o].lazy;
	t[o<<1|1].lazy+=t[o].lazy;
	t[o].lazy=0;
}
inline void update(int o,int l,int r,int x,int y,int v){
	if(y<l||r<x) return ;
	if(x<=l&&r<=y){
		t[o].lazy+=v;
		t[o].sum+=v*(r-l+1);
		return ;
	}
	int mid=(l+r)>>1;
	downtag(o,l,r,mid);
	update(o<<1,l,mid,x,y,v);
	update(o<<1|1,mid+1,r,x,y,v);
	t[o].sum=t[o<<1].sum+t[o<<1|1].sum;
}
inline int query(int o,int l,int r,int x,int y){
	if(y<l||r<x) return 0;
	if(x<=l&&r<=y) return t[o].sum;
	int mid=(l+r)>>1;
	downtag(o,l,r,mid);
	int ret1=query(o<<1,l,mid,x,y);
	int ret2=query(o<<1|1,mid+1,r,x,y);
	return ret1+ret2;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1,x;i<=n;++i){
		scanf("%lld",&x);
		update(1,1,n,i,i,x);
	}
	for(int i=1,opt,x,y,k;i<=m;++i){
		scanf("%lld%lld%lld",&opt,&x,&y);
		if(opt==1){
			scanf("%lld",&k);
			update(1,1,n,x,y,k);
		} else {
			printf("%lld\n",query(1,1,n,x,y));
		}
	}
	return 0;
}

21. 扫描线：求矩形面积并

#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=1e6+1;
ll n,p[maxn],sum[maxn],tot=0,len,lazy[maxn],ans=0;
struct segment{
	ll y,x1,x2,io;
}l[maxn];
bool cmp(const segment &a,const segment &b){
	return a.y<b.y;
}
ll Discrete(){
	sort(p+1,p+1+tot);
	ll ret=unique(p+1,p+1+tot)-(p+1);
	return ret;
}
void uptag(ll o,ll l,ll r){
	if(lazy[o]) sum[o]=p[r+1]-p[l];
	else sum[o]=sum[o*2]+sum[o*2+1];
	return ;
}
void update(ll o,ll lef,ll rig,ll x,ll y,ll v){
	if(p[rig+1]<=x||p[lef]>=y) return ;
	if(x<=p[lef]&&p[rig+1]<=y){
		lazy[o]+=v;
		uptag(o,lef,rig);
		return ;
	}
	ll mid=(lef+rig)>>1;
	update(o*2,lef,mid,x,y,v);
	update(o*2+1,mid+1,rig,x,y,v);
	uptag(o,lef,rig);
	return ;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1,x1,y1,x2,y2;i<=n;++i){
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		l[++tot]=(segment){y1,x1,x2,1};
		l[++tot]=(segment){y2,x1,x2,-1};
		p[tot-1]=x1,p[tot]=x2;
	}
	sort(l+1,l+1+tot,cmp);
	len=Discrete();
	for(ll i=1;i<tot;++i){
		update(1,1,len-1,l[i].x1,l[i].x2,l[i].io);
		ans+=sum[1]*(l[i+1].y-l[i].y);
	}
	printf("%lld\n",ans);
	return 0;
}

22. 树状数组 $1$：单点修改求区间和

#include<cstdio>

using namespace std;

const int maxn=5e5+1;
int n,m,a[maxn],c[maxn];

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

inline void add(int i,int x){
	while(i<=n){
		c[i]+=x;
		i+=lowbit(i);
	}
}

inline int sum(int i){
	int s=0;
	while(i>0){
		s+=c[i];
		i-=lowbit(i);
	}	
	return s;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		add(i,a[i]);
	}
	for(int i=1;i<=m;++i){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) add(x,y);
		else printf("%d\n",sum(y)-sum(x-1));
	}
	return 0;
}

23. 树状数组 $2$：区间修改求单点值

#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=5e5+10;
ll n,m,a[maxn],c[maxn],cur,lst;
inline void add(ll i,ll x){
	while(i<=n){
		c[i]+=x;
		i+=i&-i;
	}
}
inline ll sum(ll i){
	ll s=0;
	while(i){
		s+=c[i];
		i-=i&-i;
	}
	return s;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&cur);
		add(i,cur-lst);
		lst=cur;
	}
	for(ll i=1;i<=m;++i){
		ll op,x,y,k;
		scanf("%lld%lld",&op,&x);
		if(op==1){
			scanf("%lld%lld",&y,&k);
			add(x,k);
			add(y+1,-k);
		}
		else printf("%lld\n",sum(x));
	}
	return 0;
}

24. 权值线段树题目：普通平衡树

#include<cstdio>
using namespace std;
typedef long long ll;
const ll maxn=1e7+10;
ll n,opt,x,tot=1,root=1;
struct node{
	ll lson,rson,sum;
}T[3000010];
void update(ll &o,ll l,ll r,ll k,ll v){
	if(!o) o=++tot;
	if(l==r){
		T[o].sum+=v;
		return ;
	}
	ll mid=(l+r)>>1;
	if(k<=mid) update(T[o].lson,l,mid,k,v);
	else update(T[o].rson,mid+1,r,k,v);
	T[o].sum=T[T[o].lson].sum+T[T[o].rson].sum;
}
ll query(ll o,ll l,ll r,ll x,ll y){
	if(!o) return 0;
	if(r<x||y<l) return 0;
	if(x<=l&&r<=y) return T[o].sum;
	ll mid=(l+r)>>1;
	ll ret1=query(T[o].lson,l,mid,x,y);
	ll ret2=query(T[o].rson,mid+1,r,x,y);
	return (ret1+ret2);
}
ll Kth(ll o,ll l,ll r,ll k){
	if(l==r) return r;
	ll mid=(l+r)>>1;
	ll lson=T[o].lson;
	ll rson=T[o].rson;
	if(T[lson].sum>=k) return Kth(lson,l,mid,k);
	return Kth(rson,mid+1,r,k-T[lson].sum); 
}
ll Prev(ll x){
	ll k=query(1,-maxn,maxn,-maxn,x-1);
	return Kth(1,-maxn,maxn,k);
}
ll Next(ll x){
	ll k=query(1,-maxn,maxn,-maxn,x)+1;
	return Kth(1,-maxn,maxn,k);
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		scanf("%lld%lld",&opt,&x);
		if(opt==1) update(root,-maxn,maxn,x,1);
		if(opt==2) update(root,-maxn,maxn,x,-1);
		if(opt==3) printf("%lld\n",query(root,-maxn,maxn,-maxn,x-1)+1);
		if(opt==4) printf("%lld\n",Kth(root,-maxn,maxn,x));
		if(opt==5) printf("%lld\n",Prev(x));
		if(opt==6) printf("%lld\n",Next(x));
	}
	return 0;
}

25. 可持久化权值线段树（主席树）模板 $2$

#include<cstdio>
using namespace std;
int n,m,a[200001],tot=0,rt[200001];
struct segment{
	int lson,rson,cnt;
}T[200001*32];
inline void update(int &o,int p,int l,int r,int x){
	o=++tot,T[o]=T[p];
	if(l==r){
		++T[o].cnt;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(T[o].lson,T[p].lson,l,mid,x);
	else update(T[o].rson,T[p].rson,mid+1,r,x);
	T[o].cnt=T[T[o].lson].cnt+T[T[o].rson].cnt;
}
inline int query(int p,int o,int l,int r,int k){
	if(l==r) return l;
	int mid=(l+r)>>1,sum=T[T[o].lson].cnt-T[T[p].lson].cnt;
	if(k<=sum) return query(T[p].lson,T[o].lson,l,mid,k);
	return query(T[p].rson,T[o].rson,mid+1,r,k-sum);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		update(rt[i],rt[i-1],-1000000000,1000000000,a[i]);
	}
	for(int i=1,l,r,k;i<=m;++i){
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",query(rt[l-1],rt[r],-1000000000,1000000000,k));
	}
	return 0;
}

26. 树的重心

//给出边，求所有重心
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
int n,f[50001],ans[50001],tot=0,nowans=inf;
vector<int> g[50001];
void dfs(int u,int fa){
	if(g[u].size()==1&&u!=1) return ;
	int maxf=0;
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v==fa) continue;
		dfs(v,u);
		f[u]+=f[v]+1;
		maxf=max(f[v],maxf);
	}
	int cur=max(n-1-f[u],maxf+1);
	if(cur<nowans) tot=0,ans[++tot]=u,nowans=cur;
	else if(cur==nowans) ans[++tot]=u;
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	sort(ans+1,ans+1+tot);
	for(int i=1;i<=tot;++i) printf("%d ",ans[i]);
	putchar('\n');
	return 0;
}

27. 树的直径

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,d1[100001],d2[100001],res=0;
struct edge{
	int v,w;
};
vector<edge> g[100001];
void dfs(int u,int fa){
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i].v,w=g[u][i].w;
		if(v==fa) continue;
		dfs(v,u);
		if(d1[v]+w>d1[u]) d2[u]=d1[u],d1[u]=d1[v]+w;//更新最长路
		else if(d1[v]+w>d2[u]) d2[u]=d1[v]+w;//更新次长路
	}
	res=max(d1[u]+d2[u],res);//更新答案
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1,u,v,w;i<n;++i){
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
		g[v].push_back((edge){u,w});
	}
	dfs(1,0);
	printf("%d\n",res);
	return 0;
}

28. 最近公共祖先

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=5e5+1;
int n,m,rt,f[maxn][24],dep[maxn];
vector<int> g[maxn];
inline void dfs(int u){
	for(int i=1;i<=20;++i) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v==f[u][0]) continue;
		f[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v);
	}
}
inline int up(int v,int d){
	for(int i=0;d;++i){
		if(d&1) v=f[v][i];
		d>>=1;
	}
	return v;
}
inline int LCA(int u,int v){
	if(dep[u]>dep[v]) swap(u,v);
	v=up(v,dep[v]-dep[u]);
	if(u==v) return u;
	for(int i=20;i>=0;--i){
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}
int main(){
	scanf("%d%d%d",&n,&m,&rt);
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(rt);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));
	}
	return 0;
}

29. 快速幂运算

inline int ksm(int x,int p){
    int ret=1;
    while(p){
        if(p%2) ret=ret*x%mod;
        p>>=1;
        x=x*x%mod;
    }
    return ret%mod;
}

30. 笛卡尔树

P5854

#include<cstdio>
#define int long long
using namespace std;
const int maxn=1e7+1;
int n,a[maxn],st[maxn],top=0,lson[maxn],rson[maxn],rt,res1=0,res2=0;
inline int build_tree(){
	int k=top;
	for(int i=1;i<=n;++i){
		while(k&&a[st[k]]>a[i]) --k;
		if(k) rson[st[k]]=i;
		if(k<top) lson[i]=st[k+1];
		st[++k]=i;
		top=k;
	}
	return st[1];
}
inline void dfs(int u){
	res1^=u*(lson[u]+1ll),res2^=u*(rson[u]+1ll);
	if(lson[u]) dfs(lson[u]);
	if(rson[u]) dfs(rson[u]);
	return ;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	rt=build_tree();
	dfs(rt);
	printf("%lld %lld\n",res1,res2);
	return 0;
}

31. 基环树

1. $\operatorname{tarjan}$

void tarjan(int u,int fa){
	dfn[u]=low[u]=++idx;
	st.push(u);
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v==fa)continue;
		if(dfn[v]==0){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		cnt++;
		int v;
		do{
			v=st.top();
			st.pop();
			scc[v]=cnt;
		} while(u!=v);
	}
	return ;
}

2. 拓扑排序

void tpsort(){
	queue<int> q;
	for(int i=1;i<=n;++i){
		if(in[i]==1) q.push(i);
	}
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=0;i<g[u].size();++i){
			int v=g[u][i];
			if(in[v]>1){
				--in[v];
				if(in[v]==1) q.push(v);
			}
		}
	}
}

3. $\operatorname{dfs}$

void findCircle(int u,int fa){
	vis[u]=1;
	for(int i=0;i<g[u].size();++i){
		int v=g[u][i];
		if(v==fa) continue;
		if(vis[v]){
			flag=true,l=u,r=v;
			continue;
		}
		findCircle(v,u);
	}
}

32. AC 自动机

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
int t,n,en[1000001],idx[1000001][26],tot,nxt[1000001],res=0;
string s,f;
inline void insert(string s){
	int pos=0;
	for(int i=0;i<s.length();++i){
		int cur=s[i]-'a';
		if(!idx[pos][cur]) idx[pos][cur]=++tot;
		pos=idx[pos][cur];
	}
	++en[pos];
	return ;
}
inline void build(){
	queue<int> q;
	for(int i=0;i<26;++i){
		if(idx[0][i]) q.push(idx[0][i]);
	}
	while(!q.empty()){
		int pos=q.front();
		q.pop();
		for(int i=0;i<26;++i){
			if(idx[pos][i]){
				nxt[idx[pos][i]]=idx[nxt[pos]][i];
				q.push(idx[pos][i]);
			} else {
				idx[pos][i]=idx[nxt[pos]][i];
			}
		}
	}
}
inline void find(string t){
	int pos=0;
	for(int i=0;i<t.length();++i){
		int cur=t[i]-'a';
		int k=idx[pos][cur];
		while(k&&en[k]!=-1){
			res+=en[k];
			en[k]=-1;
			k=nxt[k];
		}
		pos=idx[pos][cur];
	}
}
int main(){
	tot=1;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		cin>>s;
		insert(s);
	}
	cin>>f;
	build();
	find(f);
	printf("%d\n",res);
	return 0;
}

33. manacher

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int ans=0,p[22000001];
string s,t;
inline void init(){
	cin>>s;
	t="$#";
	for(int i=0;i<s.length();++i) t+=s[i],t+="#";
	t+="\0";
	return ;
}
inline void manacher(){
	int mx=0,idx;
	for(int i=1;i<t.length();++i){
		if(i<mx) p[i]=min(p[2*idx-i],mx-i);
		else p[i]=1;
		while(t[i-p[i]]==t[i+p[i]]) ++p[i];
		if(mx<i+p[i]) mx=i+p[i],idx=i;
		ans=max(ans,p[i]-1);
	}
	return ;
}
int main(){
	init();
	manacher();
	printf("%d\n",ans);
	return 0;
}

alex_liu

http://example.com/2022/05/24/suan-fa-mo-ban/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 alex_liu !

c++ 学习笔记

CF1684D Traps

2022-06-13 题解

CodeForces c++

搭建 hexo 博客之前要做の事

2022-05-21 blog设置

设置

算法模板

算法模板

1. 链式前向星

2. 拓扑排序

3. 拓扑排序+判环

4. 普通 $\operatorname{Dijkstra}$：输出 $1$ 到 $n$ 的最短路

5. 普通 $\operatorname{Dijkstra}2$：输出 $s$ 到其他所有点的最短路

6. $\operatorname{Dijkstra}$：堆优化

7. 已经死了的 $\operatorname{SPFA}$

8. $\operatorname{SPFA}$ 判断负环

9. $\operatorname{Floyd}$

10. $\operatorname{Floyd}$ 输出路径

11. $\operatorname{Hierholzer}$ 输出欧拉路径

12. $\operatorname{Tarjan}$：强连通分量

13. 查找一个图的割点

14. 查找桥（无重边）

15. $\operatorname{Kruskal}$

16. $\operatorname{Prim}$

17. $\operatorname{Prim}$ 堆优化

18. 线段树：点修改，求最小值

19. 线段树：点修改，求最大子段和

20. 线段树：区间修改，求区间和

21. 扫描线：求矩形面积并

22. 树状数组 $1$：单点修改求区间和

23. 树状数组 $2$：区间修改求单点值

24. 权值线段树 题目：普通平衡树

25. 可持久化权值线段树（主席树）模板 $2$

26. 树的重心

27. 树的直径

28. 最近公共祖先

29. 快速幂运算

30. 笛卡尔树

31. 基环树

1. $\operatorname{tarjan}$

2. 拓扑排序

3. $\operatorname{dfs}$

32. AC 自动机

33. manacher

你的赏识是我前进的动力

24. 权值线段树题目：普通平衡树