#include<bits/stdc++.h>
#include<windows.h>
#include<conio.h>
using namespace std;
void f2(){
	system("\"C:\\Program Files (x86)\\Mythware\\极域课堂管理系统软件V6.0 2016 豪华版\\studentmain.exe\"");	
}void f(){
	int a=1;
    while(true){
    	int bb;
        if(a==1)bb=MessageBox(NULL,"G1yu is close,start it?","G1yu",1);
		else bb=MessageBox(NULL,"G1yu is start,taskkill it?","G1yu",1);
		if(bb==1){
			if(a==1)thread{f2}.detach();
			else system("taskkill /f /im studentmain.exe");
		}else return ;
		a^=1;
    }
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	system("taskkill /f /im studentmain.exe");
    thread{f}.detach();
    while(true){
        system("shutdown -a 2> nul");
	}return 0;
}

快读快写

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20,stdin),p1 == p2) ? EOF : *p1++)
inline int rd() {
	register int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}char obuf[1 << 20], *p3 = obuf;
#define putchar(x) (p3 - obuf < 1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++ = x)
inline void write(long long x) {
    if(!x){
        putchar('0');
        return;
    }long long len=0,k1=x,c[40];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10^48,k1/=10;
	while(len--)putchar(c[len]);
}

fwrite(obuf, p3 - obuf, 1, stdout);
	p3 = obuf;

#include<bits/stdc++.h>
using namespace std;
int n,cnt,b[10000],p[10000];
string z[10000],ans[10000];
vector<string>pio;
bool check(int i,int j,string a){
    for(int l=0;l<a.size();l++,j++){
        if(z[i][j]!=a[l])return 0;
    }return 1;
}void tab(int a){
    for(int i=1;i<=a;i++)cout<<"    ";
    return ;
}int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pio.push_back("inline");
    pio.push_back("register");
    pio.push_back("sizeof");
    pio.push_back("double");
    pio.push_back("float");
    pio.push_back("signed");
    pio.push_back("else");
    pio.push_back("struct");
    pio.push_back("typedef");
    pio.push_back("bool");
    pio.push_back("return");
    pio.push_back("int");
    pio.push_back("long");
    pio.push_back("short");
    pio.push_back("char");
    pio.push_back("unsigned");
    pio.push_back("string");
    pio.push_back("const");
    pio.push_back("auto");
    pio.push_back("void");
    pio.push_back("using");
    pio.push_back("namespace");
    while(1){
        getline(cin,z[n+1]);
        if(z[n+1]=="end")break;
        n++;
    }system("cls");
    ans[1]="#include<bits/stdc++.h>";
    cnt=2;
    int cen=0,ccc=1;
	int dd=0;
    string t;
    for(int i=1;i<=n;i++){
        bool a=1,bb=1,bbb=1,cc=1,mp=0,pp=0,iif=0,el=0; 
        for(int j=0;j<z[i].size();j++){
			if(z[i][j]=='\t'&&bb&&a)continue;
			if(z[i][j]==' '&&bb&&a)continue;
        	if(el)iif++;
            if(!ccc&&z[i][j-1]=='*'&&z[i][j]=='/'){
                ccc=1;
                continue;
            }if(!ccc)continue;
            if(z[i][j]=='/'&&z[i][j+1]=='*'&&bb){
                ccc=0;continue;
            }if(z[i][j]=='/'&&z[i][j+1]=='/'&&bb)break;if(check(i,j,"include")&&bb){
            	bbb=0;
                break;
            }if(check(i,j,"define")&&bb){
                string aaaaa="";
            	for(int k=0;k<z[i].size();k++){
            		if(z[i][k]=='/'&&z[i][k+1]=='/')break;
            		aaaaa+=z[i][k];
				}ans[++cnt]=aaaaa;
				bbb=0;
                break;
            }if(check(i,j-5,"struct")&&bb){
                string bbbb="";
                for(int k=j+2;z[i][k]!='{'&&z[i].size()>k;k++){
                    if(z[i][k]==' ')continue;
                    bbbb+=z[i][k];
                }pio.push_back(bbbb);
            }for(int k=0;k<pio.size();k++){
                if(check(i,j-pio[k].size()+1,pio[k]))a=0;
                if(check(i,j-pio[k].size(),pio[k]))a=1;
            }if(z[i][j]=='\''||z[i][j]=='\"'){
                bb=(bb+1)%2;
            }if(z[i][j]=='}'&&bb){
            	if(cc==0)cc=1;
            	else b[cnt]=cen,ans[cnt++]=t,t="",cen--;
			}t+=z[i][j];
            if(z[i][j]=='{'&&bb){
				if(t[t.size()-2]=='='||t[t.size()-2]=='[')cc=0;
            	else b[cnt]=cen,ans[cnt++]=t,t="",cen++;
			}
        }if(bbb){
            ans[cnt]+=t;
            b[cnt++]=cen;
        }t="";
    }int lst=0;
    for(int i=1;i<=cnt;i++){
        if(ans[i]=="")continue;
        if(ans[i]=="{"){
        	cout<<'{';
        	continue;
		}if(lst!=0&&(ans[lst]!="}"||ans[lst]=="}"&&ans[i][0]=='}'))cout<<"\n";
        if(ans[lst]!="}"||ans[lst]=="}"&&ans[i][0]=='}')tab(b[i]);
        cout<<ans[i];
        lst=i;
    }return 0;
}

prim & kruskal

prim算法

//Prim算法建议用于全连通图中
//思路：以1号结点为起点，每次去离自己最近的点，以此类推 
#include<bits/stdc++.h>
using namespace std;
int n,vis[5001];//vis是存储每个点是否有被连通，n代表点个数 
double a[5001],b[5001],dis[5001];//a,b代表各个点的坐标，dis是点之间的距离 
double ans;
double chang(double x,double y,double x2,double y2){//勾股定理求两个点距离 
	return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
} 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;//输入 
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		dis[i]=1e12*1.0;
	}dis[1]=0.0;//初始化，以1号结点开始 
	vis[1]=1;
	for(int i=1;i<=n;i++){
		int dian=1;//最短边的点 
		double minn=1e9*1.0;//最短边长度 
		for(int j=1;j<=n;j++){//找最短边 
			if(!vis[j]&&dis[j]<minn){//点未连通过并找到更短边 
				minn=dis[j];//刷新最短边长度和点
				dian=j;
			}
		}vis[dian]=1;//标记为已连通 
		ans+=dis[dian];//答案加上距离 
		for(int j=1;j<=n;j++){//计算结点dian与其他点的距离 
			dis[j]=min(dis[j],chang(a[dian],b[dian],a[j],b[j]));
		}
	}
	
	cout<<fixed<<setprecision(2)<<ans;//输出 
	return 0;
}

kruskal算法

//Kruskal算法建议用于非全连通图中，本题原题 https://www.luogu.com.cn/problem/P3366
#include<bits/stdc++.h>
using namespace std;
int n,m,p[5001],ans;//n是结点个数，m是边个数 
struct pio{
	int x,y,z;
}a[200001];//x,y,z代表x与y之间有一条权值为z的边 
bool cmd(pio b,pio c){//按权值从小到大排序 
	return b.z<c.z;
}int find(int b){//并查集找祖宗 
	if(p[b]==b)return b;
	return p[b]=find(p[b]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;//输入 
	for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
	sort(a+1,a+m+1,cmd);//排序 
	for(int i=1;i<=n;i++)p[i]=i;//开始自己的祖宗是自己 
	for(int i=1;i<=m;i++){//按边权大小考虑 
		int b=find(a[i].x),c=find(a[i].y);//寻找祖宗
		//祖宗一致就不用连，否则就不能保证最小生成树 
		if(b!=c){//祖宗不一致 
			p[c]=b;//连接边 
			ans+=a[i].z;//答案+=边权 
			n--;//未连结点-1 
		}
	}if(n==1)cout<<ans;//图连通有最小生成树 
	else cout<<"orz";//有点没连通，输出orz 
	return 0;
}
/*
无注释版
#include<bits/stdc++.h>
using namespace std;
int n,m,p[5001],ans;
struct pio{
	int x,y,z;
}a[200001];
bool cmd(pio b,pio c){
	return b.z<c.z;
}int find(int b){
	if(p[b]==b)return b;
	return p[b]=find(p[b]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
	sort(a+1,a+m+1,cmd); 
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=1;i<=m;i++){ 
		int b=find(a[i].x),c=find(a[i].y);
		if(b!=c){
			p[c]=b;
			ans+=a[i].z;
			n--;
		}
	}if(n==1)cout<<ans;
	else cout<<"orz";
	return 0;
} 
*/

spfa & Bellman-ford & Dijkstra

Dijkstra优化

floyd

Bellman-ford

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,d[500001]; 
struct pio{
	int u,v,w;
}z[500001]; 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		d[i]=0x7fffffff;
	}d[s]=0;
	for(int i=1;i<=m;i++){
		cin>>z[i].u>>z[i].v>>z[i].w;
	}for(int i=1;i<=n;i++){
		bool flag=0;
		for(int j=1;j<=m;j++){
			int u=z[j].u,v=z[j].v,w=z[j].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				flag=true;
			}
		}if(!flag)break;
	}for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	return 0;
}

Dijkstra

#include<bits/stdc++.h>
using namespace std;
int n,m,s,d[50001],vis[50001];
struct pio{
	int v,w;
};
vector<pio>z[50001]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		z[u].push_back({v,w});
	}for(int i=1;i<=n;i++)d[i]=1e9;
	d[s]=0;
	for(int i=1;i<n;i++){
		int maxn=1e9,t;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&d[j]<maxn){
				maxn=d[j];
				t=j;
			}
		}vis[t]=1;
		for(int j=0;j<z[t].size();j++){
			int v=z[t][j].v,w=z[t][j].w;
			if(d[v]>d[t]+w){
				d[v]=d[t]+w;
			}
		}
	}for(int i=1;i<=n;i++)cout<<(d[i]==1e9?(1<<31)-1:d[i])<<" ";
	
	return 0;
}

floyd

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[101][101]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=1e9;
		}dp[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		dp[u][v]=min(dp[u][v],w); 
		dp[v][u]=min(dp[u][v],w);
	}for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<dp[i][j]<<" ";
		}cout<<"\n";
	}
	return 0;
}

spfa

#include<bits/stdc++.h>
using namespace std;
int n,m,s,vis[100001],d[100001]; 
struct pio{
	int v,w;
};
vector<pio>z[100001];
queue<int>q;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)d[i]=1e9;
	d[s]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		z[u].push_back({v,w}); 
	}vis[s]=1;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0;i<z[u].size();i++){
			int v=z[u][i].v,w=z[u][i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]){
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	return 0;
}

Dijkstra优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,d[500001],vis[500001];
struct pio{
	int v,w;
};
struct node{
	int dis,u;
	bool operator>(const node& a) const { return dis > a.dis; }
};
vector<pio>z[500001]; 
priority_queue<node, vector<node>, greater<node> > q;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		z[u].push_back({v,w});
	}for(int i=1;i<=n;i++)d[i]=1e9;
	d[s]=0;
	q.push({0,s});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int j=0;j<z[u].size();j++){
			int v=z[u][j].v,w=z[u][j].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push({d[v],v});
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	
	return 0;
}

二分图染色

二分图最大匹配

拓扑排序/家谱树

二分图

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,vis[10010],ans;
vector<int>z[10010];
bool dfs(int u,int c){
    vis[u]=c;
    c==1?a++:b++;
    for(int i=0;i<z[u].size();i++){
        if(vis[z[u][i]]==c||(!vis[z[u][i]]&&!dfs(z[u][i],3-c)))return false;
    }return true;
}int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        z[u].push_back(v);
        z[v].push_back(u);
    }for(int i=1;i<=n;i++){
        if(!vis[i]&&!dfs(i,1)){
            cout<<"Impossible";
            return 0;
        }ans+=min(a,b);
        a=0;
        b=0;
    }cout<<ans<<endl;
}

二分图的最大匹配

#include<bits/stdc++.h>
using namespace std;
int n,m,e,vis[1001],match[1001],ans;
vector<int>z[1001];
bool dfs(int x){
	
	for(int i=0;i<z[x].size();i++){
		if(vis[z[x][i]]==0){
			vis[z[x][i]]=1;
			if(match[z[x][i]]==0||dfs(match[z[x][i]])){
				match[z[x][i]]=x;
				return true;
			}	
		}
	}return false;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>e;
	for(int i=1;i<=e;i++){
		int a,b;
		cin>>a>>b;
		z[a].push_back(b);
	}for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(dfs(i))ans++;
	}cout<<ans;
	return 0;
}

拓扑排序

#include<bits/stdc++.h>
using namespace std;
int n,p[101],t=0,h=1; 
vector<int>z[101];
queue<int>q;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		while(1){
			cin>>x;
			if(x==0)break;
			z[i].push_back(x);
			p[x]++;
		}
	}for(int i=1;i<=n;i++){
		if(p[i]==0)q.push(i),cout<<i<<" ";
	}while(!q.empty()){
		int a=q.front();
		q.pop();
		for(int j=0;j<z[a].size();j++){
			p[z[a][j]]--;
			if(p[z[a][j]]==0){
				q.push(z[a][j]);
				cout<<z[a][j]<<" ";
			}
		}
	}
	return 0;
}

缩点

割点 割边

点双 边双

lca

#include<bits/stdc++.h>
using namespace std;
int n,m,s,p[500001],vis[500001],ans[500001];
struct pio{
	int a,b;
};
vector<int>z[500001];
vector<pio>z1[500001];
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]); 
}
void dfs(int x){
	vis[x]=1;
	for(int i=0;i<z[x].size();i++){
		if(!vis[z[x][i]]){
			dfs(z[x][i]);
			p[z[x][i]]=x;
		}
	}
	for(int i=0;i<z1[x].size();i++){
		if(vis[z1[x][i].a]){
			int ans1=find(z1[x][i].a);
			ans[z1[x][i].b]=ans1;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)p[i]=i;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		z[y].push_back(x);
		z[x].push_back(y);
	}for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		z1[x].push_back({y,i});
		z1[y].push_back({x,i});
	}dfs(s);
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n"; 
	return 0;
}

缩点

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10001],dfn[10001],dp[10001],p[10001],id[10001],low[10001],vis[10001],cnt,cmp,ans;
stack<int>s;
vector<int>z[100001];
vector<int>z1[100001];
void dfs(int x){
	dfn[x]=++cnt;
	low[x]=dfn[x]; 
	s.push(x);
	vis[x]=1;
	for(int i=0;i<z[x].size();i++){
		if(!dfn[z[x][i]]){
			dfs(z[x][i]);
			low[x]=min(low[x],low[z[x][i]]);
		}else if(vis[z[x][i]]){
			low[x]=min(low[x],dfn[z[x][i]]);
		} 
	}if(dfn[x]==low[x]){
		while(1){
			int y=s.top();
			s.pop();
			id[y]=x;
			vis[y]=0;
			if(x==y)break;
			a[x]+=a[y];
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		z[x].push_back(y);
	}for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<z[i].size();j++){
			if(id[i]!=id[z[i][j]]){
				p[id[z[i][j]]]++;
				z1[id[i]].push_back(id[z[i][j]]);
			}			
		}
	}queue<int>q;
	for(int i=1;i<=n;i++){
		if(p[i]==0)q.push(i),dp[i]=a[i];
	}while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<z1[u].size();i++){
			p[z1[u][i]]--;
			dp[z1[u][i]]=max(dp[z1[u][i]],dp[u]+a[z1[u][i]]);
			if(p[z1[u][i]]==0)q.push(z1[u][i]);
		}
	}for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
	}cout<<ans;
	return 0;
}

割边

#include<bits/stdc++.h>
using namespace std;
int n,m,dfn[50001],b[500001],low[50001],ans,cnt;
struct pio{
	int a,b;
};
vector<pio>z[50001];
void dfs(int x,int fa){
	dfn[x]=++cnt;
	low[x]=dfn[x]; 
	for(int i=0;i<z[x].size();i++){
		if(!dfn[z[x][i].a]){
			dfs(z[x][i].a,x);
			low[x]=min(low[x],low[z[x][i].a]);
			if(low[z[x][i].a]>dfn[x])b[z[x][i].b]=1;
		}else if(z[x][i].a!=fa){
			low[x]=min(low[x],dfn[z[x][i].a]);
		} 
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y)continue;
		z[x].push_back({y,i});
		z[y].push_back({x,i});
	}for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,0);
		}
	}for(int i=1;i<=m;i++){
		if(b[i]){
            ans++;
        }
	}
    cout<<ans;
	return 0;
}

割点

#include <bits/stdc++.h>
using namespace std;
int dfn[40001],low[40001],cnt,n,m,vis[40001],ans;
vector<int>z[40001];
void dfs(int x,int fa){
	dfn[x]=low[x]=++cnt;
	int c=0;
	for(int i=0;i<z[x].size();i++){
		if(!dfn[z[x][i]]){
			c++;
			dfs(z[x][i],x);
			low[x]=min(low[x],low[z[x][i]]);
			if(low[z[x][i]]>=dfn[x]){
				vis[x]=1;
			}
		}else if(fa!=z[x][i]){
			low[x]=min(low[x],dfn[z[x][i]]);
		}
	}if(fa==0&&c==1)vis[x]=0;
}
int main() {
	cin>>n>>m; 
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x!=y){
			z[x].push_back(y);
			z[y].push_back(x);
		}
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i]){
			ans++;
		}
	}
	cout<<ans<<"\n";
	for(int i=1;i<=n;i++){
		if(vis[i]){
			cout<<i<<" ";
		}
	}
	return 0;
}

边双

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[500001],dfn[500001],zu,b[5000001],low[500001],cnt;
struct pio{
	int a,b;
};
vector<pio>z[500001];
vector<int>ans[500001];
void dfs(int x,int fa){
	dfn[x]=++cnt;
	low[x]=dfn[x]; 
	for(int i=0;i<z[x].size();i++){
		if(!dfn[z[x][i].a]){
			dfs(z[x][i].a,x);
			low[x]=min(low[x],low[z[x][i].a]);
			if(low[z[x][i].a]>dfn[x])b[z[x][i].b]=1;
		}else if(z[x][i].a!=fa){
			low[x]=min(low[x],dfn[z[x][i].a]);
		} 
	}
}void dfs(int x){
	vis[x]=zu;
	if(x)ans[zu].push_back(x);
	for(int i=0;i<z[x].size();i++){
		if(!vis[z[x][i].a]&&!b[z[x][i].b]){
			dfs(z[x][i].a);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x==y)continue;
		z[x].push_back({y,i});
		z[y].push_back({x,i});
	}for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,0);
		}
	}for(int i=1;i<=n;i++){
		if(!vis[i]){
			zu++;
			dfs(i);
		}
	}cout<<zu<<"\n";
	for(int i=1;i<=zu;i++){
		cout<<ans[i].size()<<" ";
		for(int j=0;j<ans[i].size();j++){
			cout<<ans[i][j]<<" ";
		} cout<<"\n";
	}
	return 0;
}

点双

#include <bits/stdc++.h>
using namespace std;
int dfn[500001],zu,low[500001],cnt,n,m,vis[500001];
stack<int>q;
vector<int>z[500001];
vector<int>ans[500001];
void dfs(int x,int fa){
	dfn[x]=low[x]=++cnt;
	int c=0;
	q.push(x);
	for(int i=0;i<z[x].size();i++){
		if(!dfn[z[x][i]]){
			c++;
			dfs(z[x][i],x);
			low[x]=min(low[x],low[z[x][i]]);
			if(low[z[x][i]]>=dfn[x]){
				zu++;
				while(1){
					int y=q.top();
					ans[zu].push_back(y);
					q.pop();
					if(y==z[x][i])break;
				}ans[zu].push_back(x);
			}
		}else if(fa!=z[x][i]){
			low[x]=min(low[x],dfn[z[x][i]]);
		}
	}if(fa==x&&z[x].size()==0)ans[++zu].push_back(x);
}
int main() {
	cin>>n>>m; 
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(x!=y){
			z[x].push_back(y);
			z[y].push_back(x);
		}
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,i);
		}
	}
	cout<<zu<<"\n";
	for(int i=1;i<=zu;i++){
		cout<<ans[i].size()<<" ";
		for(int j=0;j<ans[i].size();j++){
			cout<<ans[i][j]<<" ";
		}cout<<"\n";
	}
	return 0;
}

树状数组

树状数组1

#include<bits/stdc++.h>
using namespace std;
int n,m,z[500001],c[500001];
int low_bit(int x){
	return x&-x;
}int xun(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=low_bit(x);
	}return ans;
}void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=low_bit(x);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>z[i];
		add(i,z[i]);
	}for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(x==2){
			cout<<xun(z)-xun(y-1)<<"\n";
		}else add(y,z);
	}
	return 0; 
}

树状数组2

#include<bits/stdc++.h>
using namespace std;
int n,m,z[500001],c[500001];
int low_bit(int x){
	return x&-x;
}int xun(int x){
	int ans=0;
	while(x){
		ans+=c[x];
		x-=low_bit(x);
	}return ans;
}void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=low_bit(x);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>z[i];
		add(i,z[i]);
		add(i+1,-z[i]);
	}for(int i=1;i<=m;i++){
		int x,y,k,a;
		cin>>a>>x;
		if(a==1){
			cin>>y>>k;
			add(x,k);
			add(y+1,-k);
		}else{
			cout<<xun(x)<<"\n";
		}
	}
	return 0; 
}

线段树

线段树1线段树做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,z[100001],lazy[400001],l[400001],r[400001],sum[400001];
void up(int x){
	sum[x]=sum[x*2]+sum[x*2+1];
}void down(int x){
	sum[x*2]+=(r[x*2]-l[x*2]+1)*lazy[x];
	lazy[x*2]+=lazy[x];
	sum[x*2+1]+=(r[x*2+1]-l[x*2+1]+1)*lazy[x];
	lazy[x*2+1]+=lazy[x];
	lazy[x]=0;
}void build(int x,int y,int k){
	l[x]=y;
	r[x]=k;
	if(y==k){
		sum[x]=z[y];
		return ;
	}int mid=(y+k)/2;
	build(x*2,y,mid);
	build(x*2+1,mid+1,k);
	up(x);
	return ;
}void modify(int x,int l1,int r1,int k){
	if(l1>r[x]||r1<l[x])return ;
	if(l[x]>=l1&&r[x]<=r1){
		sum[x]+=(r[x]-l[x]+1)*k;
		lazy[x]+=k;
		return ;
	}down(x);
	modify(x*2,l1,r1,k);
	modify(x*2+1,l1,r1,k);
	up(x);
	return ;
}int xun(int x,int l1,int r1){
	if(l[x]>r1||r[x]<l1)return 0;
	if(l[x]>=l1&&r[x]<=r1)return sum[x];
	down(x);
	return xun(x*2,l1,r1)+xun(x*2+1,l1,r1);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>z[i];
	}build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt,a,b,c;
		cin>>opt>>a>>b;
		if(opt==1){
			cin>>c;
			modify(1,a,b,c);
		}else cout<<xun(1,a,b)<<"\n";
	}
	return 0;	
} 

线段树1的树状数组做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,z[500001],c[500001],c1[500001];
int low_bit(int x){
	return x&-x;
}int xun(int x){
	int ans=0,t=x;
	while(x){
		ans+=(t+1)*c[x]-c1[x];
		x-=low_bit(x);
	}return ans;
}void add(int x,int v){
	int t=x;
	while(x<=n){
		c[x]+=v;
		c1[x]+=t*v;
		x+=low_bit(x);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>z[i];
		add(i,z[i]);
		add(i+1,-z[i]);
	}for(int i=1;i<=m;i++){
		int x,y,k,a;
		cin>>a>>x>>y;
		if(a==1){
			cin>>k;
			add(x,k);
			add(y+1,-k);
		}else{
			cout<<xun(y)-xun(x-1)<<"\n";
		}
	}
	return 0; 
}

线段树1不向下传递 lazy 做法

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,z[400001],sum[400001],lazy[400001],l1[400001],r1[400001];
void up(int x){
	sum[x]=sum[x*2]+sum[x*2+1];
}void build(int num,int l,int r){
	l1[num]=l;
	r1[num]=r;
	if(l==r){
		sum[num]=z[l];
		return ;
	}int mid=(l+r)/2;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
	up(num);
	return ;
}void modify(int num,int l,int r,int x){
	if(r1[num]<l||l1[num]>r){
		return ;
	}sum[num]+=(min(r1[num],r)-max(l1[num],l)+1)*x;
	if(r1[num]<=r&&l1[num]>=l){
		lazy[num]+=x;
		return ;
	}modify(num*2,l,r,x);
	modify(num*2+1,l,r,x);
}int xun(int num,int l,int r,int x){
	if(r1[num]<l||l1[num]>r){
		return 0;
	}if(r1[num]<=r&&l1[num]>=l){
		return sum[num]+(r1[num]-l1[num]+1)*x;
	}return xun(num*2,l,r,x+lazy[num])+xun(num*2+1,l,r,x+lazy[num]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>z[i];
	build(1,1,n);
	while(m--){
		int a,x,y,k;
		cin>>a>>x>>y;
		if(a==1){
			cin>>k;
			modify(1,x,y,k);
		}else cout<<xun(1,x,y,0)<<"\n";
	}
	return 0;
}

线段树1动态开点

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100001],ml[500001],mr[500001],l[500001],r[500001],sum[500001],la[500001],q[500001],cnt;
void addl(int x){
	ml[x]=++cnt;
	l[cnt]=l[x];
	r[cnt]=(r[x]+l[x])/2;
	sum[cnt]=q[r[cnt]]-q[l[cnt]-1];
}void addr(int x){
	mr[x]=++cnt;
	l[cnt]=(r[x]+l[x])/2+1;
	r[cnt]=r[x];
	sum[cnt]=q[r[cnt]]-q[l[cnt]-1];
}void down(int x){
	if(!ml[x])addl(x);
	if(!mr[x])addr(x);
	sum[ml[x]]+=(r[ml[x]]-l[ml[x]]+1)*la[x];
	sum[mr[x]]+=(r[mr[x]]-l[mr[x]]+1)*la[x];
	la[ml[x]]+=la[x];
	la[mr[x]]+=la[x];
	la[x]=0;
}void up(int x){
	if(!ml[x])addl(x);
	if(!mr[x])addr(x);
	sum[x]=sum[ml[x]]+sum[mr[x]];
}void modify(int x,int l1,int r1,int k){
	if(l1>r[x]||r1<l[x])return ;
	if(l1<=l[x]&&r1>=r[x]){
		sum[x]+=(r[x]-l[x]+1)*k;
		la[x]+=k;
		return ;
	}down(x);
	modify(ml[x],l1,r1,k);
	modify(mr[x],l1,r1,k);
	up(x);
}int xun(int x,int l1,int r1){
//	cout<<x<<" "<<ml[x]<<" "<<mr[x]<<"\n";
	if(l[x]>r1||r[x]<l1)return 0;
	if(l1<=l[x]&&r1>=r[x])return sum[x];
	down(x);
	return xun(ml[x],l1,r1)+xun(mr[x],l1,r1);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		q[i]=q[i-1]+a[i];
	}l[1]=1;
	r[1]=n;
	sum[1]=q[n];
	cnt=1;
	while(m--){
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			modify(1,x,y,k);
		}else cout<<xun(1,x,y)<<"\n";
	}
	return 0;
}

线段树六大操作

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,sum[500001],l[500001],mn[500001],la[500001],lazy[500001],r[500001],mx[500001],a[500001];
void up(int x){
	sum[x]=sum[x*2]+sum[x*2+1];
	mx[x]=max(mx[x*2],mx[x*2+1]);
	mn[x]=min(mn[x*2],mn[x*2+1]);
}void dow(int x){
	if(la[x]!=-1e18){
		la[2*x]=la[x*2+1]=mx[2*x]=mx[2*x+1]=mn[2*x]=mn[2*x+1]=la[x];
		sum[2*x]=1ll*(r[2*x]-l[2*x]+1)*la[x];
		sum[2*x+1]=1ll*(r[2*x+1]-l[2*x+1]+1)*la[x];
		la[x]=-1e18;
		lazy[x*2]=lazy[x*2+1]=0;
	}	
}void down(int x){
	dow(x);
	sum[x*2]+=1ll*(r[x*2]-l[x*2]+1)*lazy[x];
	sum[x*2+1]+=1ll*(r[x*2+1]-l[x*2+1]+1)*lazy[x];
	mx[x*2]+=lazy[x];
	mx[x*2+1]+=lazy[x];
	mn[x*2]+=lazy[x];
	mn[x*2+1]+=lazy[x];
	lazy[x*2]+=lazy[x];
	lazy[x*2+1]+=lazy[x];
	lazy[x]=0;
}void build(int x,int l1,int r1){
	l[x]=l1;
	r[x]=r1;
	la[x]=-1e18;
	if(l1==r1){
		mx[x]=mn[x]=sum[x]=a[l1];
		return ;
	}int mid=(l1+r1)>>1;
	build(x*2,l1,mid);
	build(x*2+1,mid+1,r1);
	up(x);
}void modify1(int x,int l1,int r1,int k){
	if(l[x]>r1||r[x]<l1)return ;
	if(l[x]>=l1&&r[x]<=r1){
		mx[x]+=k;
		mn[x]+=k;
		sum[x]+=1ll*(r[x]-l[x]+1)*k;
		lazy[x]+=k;
		return ; 
	}down(x);
	modify1(x*2,l1,r1,k);
	modify1(x*2+1,l1,r1,k);
	up(x);
}void modify2(int x,int l1,int r1,int k){
	if(l[x]>r1||r[x]<l1)return ;
	if(l[x]>=l1&&r[x]<=r1){
		la[x]=mx[x]=mn[x]=k;
		sum[x]=1ll*(r[x]-l[x]+1)*k;
		lazy[x]=0;
		return ; 
	}down(x);
	modify2(x*2,l1,r1,k);
	modify2(x*2+1,l1,r1,k);
	up(x);
}int xun(int x,int l1,int r1){
	if(l[x]>r1||r[x]<l1)return -1e18;
	if(l[x]>=l1&&r[x]<=r1)return mx[x];
	down(x);
	return max(xun(x*2,l1,r1),xun(x*2+1,l1,r1));
}int xun2(int x,int l1,int r1){
	if(l[x]>r1||r[x]<l1)return 1e18;
	if(l[x]>=l1&&r[x]<=r1)return mn[x];
	down(x);
	return min(xun2(x*2,l1,r1),xun2(x*2+1,l1,r1));
}int xun3(int x,int l1,int r1){
	if(l[x]>r1||r[x]<l1)return 0;
	if(l[x]>=l1&&r[x]<=r1)return sum[x];
	down(x);
	return xun3(x*2,l1,r1)+xun3(x*2+1,l1,r1);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}build(1,1,n);
	while(q--){
		int a,x,y,k;
		cin>>a;
		if(a==1){//l~r +k
			cin>>x>>y>>k;
			modify1(1,x,y,k);
		}if(a==2){//l~r -k
			cin>>x>>y>>k;
			modify1(1,x,y,-k);
		}if(a==3){//l~r =k
			cin>>x>>y>>k;
			modify2(1,x,y,k);
		}if(a==4){//l~r sum
			cin>>x>>y;
			cout<<xun3(1,x,y)<<"\n";
		}if(a==5){//l~r max
			cin>>x>>y;
			cout<<xun(1,x,y)<<"\n";
		}if(a==6){//l~r min
			cin>>x>>y;
			cout<<xun2(1,x,y)<<"\n";
		}
	}
	return 0;
}

线段树2

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100001],q;
struct pio{
	int l,r;
	long long sum,lasy,h;
}z[400001];
void up(int u){
	z[u].sum=z[u*2].sum+z[u*2+1].sum;
	z[u].sum%=m;
}void down(int u){
	z[u*2].sum*=z[u].h;
	z[u*2].sum%=m;
	z[u*2+1].sum*=z[u].h;
	z[u*2+1].sum%=m;
	z[u*2].sum+=(z[u*2].r-z[u*2].l+1)*z[u].lasy;
	z[u*2].sum%=m;
	z[u*2+1].sum+=(z[u*2+1].r-z[u*2+1].l+1)*z[u].lasy;
	z[u*2+1].sum%=m;
	z[u*2].lasy=z[u*2].lasy*z[u].h+z[u].lasy;
	z[u*2].lasy%=m;
	z[u*2+1].lasy=z[u*2+1].lasy*z[u].h+z[u].lasy;
	z[u*2+1].lasy%=m;
	z[u*2].h*=z[u].h;
	z[u*2].h%=m;
	z[u*2+1].h*=z[u].h;
	z[u*2+1].h%=m;
	z[u].lasy=0;
	z[u].h=1;
	
}void build(int u,int l,int r){
	z[u].l=l;
	z[u].r=r;
	z[u].h=1;
	if(l==r){
		z[u].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	up(u);
}void modify1(int u,int l,int r,int x){
	if(z[u].l>r||z[u].r<l)return ;
	if(z[u].l>=l&&z[u].r<=r){
		z[u].sum*=x;
		z[u].sum%=m;
		z[u].lasy*=x;
		z[u].lasy%=m;
		z[u].h*=x;
		z[u].h%=m;
		return ; 
	}
	down(u);
	modify1(u*2,l,r,x);
	modify1(u*2+1,l,r,x);
	up(u);
}
void modify2(int u,int l,int r,int x){
	if(z[u].l>r||z[u].r<l)return ;
	if(z[u].l>=l&&z[u].r<=r){
		z[u].sum+=(z[u].r-z[u].l+1)*x;
		z[u].sum%=m;
		z[u].lasy+=x;
		z[u].lasy%=m;
		return ; 
	}
	down(u);
	modify2(u*2,l,r,x);
	modify2(u*2+1,l,r,x);
	up(u);
}
long long query(int u,int l,int r){
	if(z[u].l>r||z[u].r<l)return 0;
	if(z[u].l>=l&&z[u].r<=r)return z[u].sum;
	down(u);
	return query(u*2,l,r)+query(u*2+1,l,r);
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]%=m;
	build(1,1,n);
	while(q--){
		int a,x,y,k;
		cin>>a>>x>>y;
		if(a==1){
			cin>>k;
			modify1(1,x,y,k);
		}else if(a==2){
			cin>>k;
			modify2(1,x,y,k);
		}else cout<<query(1,x,y)%m<<"\n";
	}
	return 0;
}

线段树扶苏的问题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,l[5000001],la[5000001],lazy[5000001],r[5000001],mx[5000001],a[5000001];
void up(int x){
	mx[x]=max(mx[x*2],mx[x*2+1]);
}void dow(int x){
	if(la[x]!=-1e18){
		la[2*x]=la[x*2+1]=mx[2*x]=mx[2*x+1]=la[x];
		la[x]=-1e18;
		lazy[x*2]=lazy[x*2+1]=0;
	}	
}void down(int x){
	dow(x);
	mx[x*2]+=lazy[x];
	mx[x*2+1]+=lazy[x];
	lazy[x*2]+=lazy[x];
	lazy[x*2+1]+=lazy[x];
	lazy[x]=0;
}void build(int x,int l1,int r1){
	//cout<<x<<" "<<l1<<" "<<r1<<"\n";
	l[x]=l1;
	r[x]=r1;
	la[x]=-1e18;
	if(l1==r1){
		mx[x]=a[l1];
		return ;
	}int mid=(l1+r1)>>1;
	build(x*2,l1,mid);
	build(x*2+1,mid+1,r1);
	up(x);
}void modify1(int x,int l1,int r1,int k){
	if(l[x]>r1||r[x]<l1)return ;
	if(l[x]>=l1&&r[x]<=r1){
		la[x]=mx[x]=k;
		lazy[x]=0;
		return ; 
	}down(x);
	modify1(x*2,l1,r1,k);
	modify1(x*2+1,l1,r1,k);
	up(x);
}void modify2(int x,int l1,int r1,int k){
	if(l[x]>r1||r[x]<l1)return ;
	if(l[x]>=l1&&r[x]<=r1){
		dow(x);
		mx[x]+=k;
		lazy[x]+=k;
		return ; 
	}down(x);
	modify2(x*2,l1,r1,k);
	modify2(x*2+1,l1,r1,k);
	up(x);
}int xun(int x,int l1,int r1){
	//cout<<x<<" "<<l[x]<<" "<<r[x]<<" "<<mx[x]<<"\n"; 
	if(l[x]>r1||r[x]<l1)return -1e18;
	if(l[x]>=l1&&r[x]<=r1)return mx[x];
	down(x);
	return max(xun(x*2,l1,r1),xun(x*2+1,l1,r1));
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}build(1,1,n);
	while(q--){
		int a,x,y,k;
		cin>>a;
		if(a==1){
			cin>>x>>y>>k;
			modify1(1,x,y,k);
		}if(a==2){
			cin>>x>>y>>k;
			modify2(1,x,y,k);
		}if(a==3){
			cin>>x>>y;
			cout<<xun(1,x,y)<<"\n";
		}
	}
	return 0;
}

模板1：区间加，单点询问

#include<bits/stdc++.h>
using namespace std;
int n,a[50001],bl[50001],sum[50001],t[50001],h[50001];
void add(int l,int r,int c){
	for(int i=l;i<=min(r,t[bl[l]]);i++){
		a[i]+=c;
	}if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=r;i++){
			a[i]+=c;
		}
	}for(int i=bl[l]+1;i<=bl[r]-1;i++)sum[i]+=c;
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		if(++temp==1)h[++k]=i;
		if(temp==sqrt(n)||i==n){
			t[k]=i;
			temp=0;
		}cin>>a[i];
		bl[i]=k;
	}for(int i=1;i<=n;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0){
			add(l,r,c);
		}else cout<<sum[bl[r]]+a[r]<<"\n";
	}
	return 0;
}

模板2：区间加，区间查询小于 $k$ 的个数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int>a[1000001];
int q,n,bl[1000001],sum[1000001],t[1000001],h[1000001];
void add(int l,int r,int c){
	for(int i=h[bl[l]];i<=t[bl[l]];i++){
		if(a[i].second>=l&&a[i].second<=r)a[i].first+=c;
	}sort(a+h[bl[l]],a+t[bl[l]]+1);
	if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=t[bl[r]];i++){
			if(a[i].second>=l&&a[i].second<=r)a[i].first+=c;
		}sort(a+h[bl[r]],a+t[bl[r]]+1);
	}for(int i=bl[l]+1;i<=bl[r]-1;i++)sum[i]+=c;
}int xun(int x,int y,int k){
	int ans=0;
	for(int i=h[bl[x]];i<=t[bl[x]];i++){
		if(a[i].second>=x&&a[i].second<=y&&a[i].first+sum[bl[x]]<k)ans++;
	}if(bl[x]!=bl[y]){
		for(int i=h[bl[y]];i<=t[bl[y]];i++){
			if(a[i].second>=x&&a[i].second<=y&&a[i].first+sum[bl[y]]<k)ans++;
		}
	}for(int i=bl[x]+1;i<=bl[y]-1;i++){
		int l=h[i],r=t[i]+1;
		while(l+1<r){
			int mid=(l+r)/2;
			if(a[mid].first+sum[i]<k)l=mid;
			else r=mid;
		}if(a[l].first+sum[i]<k)ans+=l-h[i]+1;
	}return ans;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].first;
		a[i].second=i; 
		if(++temp==1)h[++k]=i;
		if(temp==(int)sqrt(n)||i==n){
			t[k]=i;
			temp=0;
			sort(a+h[k],a+t[k]+1);
		}bl[i]=k;
	}for(int i=1;i<=n;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0){
			add(l,r,c);
		}else cout<<xun(l,r,c*c)<<"\n";
	}
	return 0;
}

模板3：区间求和，区间求比 $k$ 小的最大值

#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int>a[100001];
int n,bl[100001],sum[100001],t[100001],h[100001];
void add(int l,int r,int c){
	for(int i=h[bl[l]];i<=t[bl[l]];i++){
		if(a[i].second>=l&&a[i].second<=r)a[i].first+=c;
	}sort(a+h[bl[l]],a+t[bl[l]]+1);
	if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=t[bl[r]];i++){
			if(a[i].second>=l&&a[i].second<=r)a[i].first+=c;
		}sort(a+h[bl[r]],a+t[bl[r]]+1);
	}for(int i=bl[l]+1;i<=bl[r]-1;i++)sum[i]+=c;
}int xun(int x,int y,int k){
	int maxn=-1e18;
	for(int i=h[bl[x]];i<=t[bl[x]];i++){
		if(a[i].second>=x&&a[i].second<=y&&a[i].first+sum[bl[x]]<k&&a[i].first+sum[bl[x]]>maxn)maxn=a[i].first+sum[bl[x]];
	}if(bl[x]!=bl[y]){
		for(int i=h[bl[y]];i<=t[bl[y]];i++){
			if(a[i].second>=x&&a[i].second<=y&&a[i].first+sum[bl[y]]<k&&a[i].first+sum[bl[y]]>maxn)maxn=a[i].first+sum[bl[y]];
		}
	}for(int i=bl[x]+1;i<=bl[y]-1;i++){
		int l=h[i],r=t[i]+1;
		while(l+1<r){
			int mid=(l+r)/2;
			if(a[mid].first+sum[i]<k)l=mid;
			else r=mid;
		}if(a[l].first+sum[i]<k)maxn=max(maxn,a[l].first+sum[i]);
	}return (maxn==-1e18?-1:maxn);
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].first;
		a[i].second=i;
		if(++temp==1)h[++k]=i;
		if(temp==(int)sqrt(n)||i==n){
			t[k]=i;
			temp=0;
			sort(a+h[k],a+t[k]+1);
		}bl[i]=k;
	}for(int i=1;i<=n;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0){
			add(l,r,c);
		}else cout<<xun(l,r,c)<<"\n";
	}
	return 0;
}

模板4：区间加，区间求和

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[50001],bl[50001],sum2[50001],sum[50001],t[50001],h[50001];
void add(int l,int r,int c){
	for(int i=l;i<=min(r,t[bl[l]]);i++){
		a[i]+=c;
		sum2[bl[l]]+=c;
	}if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=r;i++){
			a[i]+=c;
			sum2[bl[r]]+=c;
		}
	}for(int i=bl[l]+1;i<=bl[r]-1;i++)sum[i]+=c;
}int xun(int l,int r,int c){
	int ans=0;
	for(int i=l;i<=min(r,t[bl[l]]);i++){
		ans+=a[i]+sum[bl[l]];
		ans%=c;
	}if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=r;i++){
			ans+=a[i]+sum[bl[r]];
			ans%=c;
		}
	}for(int i=bl[l]+1;i<=bl[r]-1;i++){
		ans+=sum2[i]%c+(t[i]-h[i]+1)*sum[i]%c;
		ans%=c;
	}return ans;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		if(++temp==1)h[++k]=i;
		if(temp==(int)sqrt(n)||i==n){
			t[k]=i;
			temp=0;
		}cin>>a[i];
		sum2[k]+=a[i];
		bl[i]=k;
	}for(int i=1;i<=n;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(opt==0){
			add(l,r,c);
		}else cout<<xun(l,r,c+1)<<"\n";
	}
	return 0;
}

模板5：区间开方，区间求和

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100001],bl[100001],sum2[100001],sum[100001],t[100001],h[100001];
void add(int l,int r){
	if(sum[bl[l]]){
		for(int i=l;i<=min(r,t[bl[l]]);i++){
			if(a[i]==1||a[i]==0)continue;
			sum2[bl[l]]-=a[i];
			a[i]=sqrt(a[i]);
			sum2[bl[l]]+=a[i];
			if(a[i]==1||a[i]==0)sum[bl[l]]--;
		}
	}if(bl[l]!=bl[r]&&sum[bl[r]]){
		for(int i=h[bl[r]];i<=r;i++){
			if(a[i]==1||a[i]==0)continue;
			sum2[bl[r]]-=a[i];
			a[i]=sqrt(a[i]);
			sum2[bl[r]]+=a[i];
			if(a[i]==1||a[i]==0)sum[bl[r]]--;
		}
	}for(int i=bl[l]+1;i<=bl[r]-1;i++){
		if(!sum[i])continue;
		for(int j=h[i];j<=t[i];j++){
			if(a[j]==1||a[j]==0)continue;
			sum2[i]-=a[j];
			a[j]=sqrt(a[j]);
			sum2[i]+=a[j];
			if(a[j]==1||a[j]==0)sum[i]--;
		}
	}
}int xun(int l,int r){
	int ans=0;
	for(int i=l;i<=min(r,t[bl[l]]);i++){
		ans+=a[i];
	}if(bl[l]!=bl[r]){
		for(int i=h[bl[r]];i<=r;i++){
			ans+=a[i];
		}
	}for(int i=bl[l]+1;i<=bl[r]-1;i++){
		ans+=sum2[i];
	}return ans;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		if(++temp==1)h[++k]=i;
		if(temp==(int)sqrt(n)||i==n){
			t[k]=i;
			temp=0;
		}cin>>a[i];
		if(a[i]!=0&&a[i]!=1)sum[k]++;
		sum2[k]+=a[i];
		bl[i]=k;
	}for(int i=1;i<=n;i++){
		int opt,l,r,c;
		cin>>opt>>l>>r>>c;
		if(l>r)swap(l,r);
		if(opt==0){
			add(l,r);
		}else cout<<xun(l,r)<<"\n";
	}
	return 0;
}

模板6：插入数字，单点询问

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>v;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		v.push_back(a);
	}for(int i=1;i<=n;i++){
		int opt,x,y,k;
		cin>>opt>>x>>y>>k;
		if(opt==0)v.insert(v.begin()+x-1,y);
		else cout<<v[y-1]<<"\n";
	}
	return 0;
}

模板八：区间修改，区间询问某数个数

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100001],bl[100001],sum[100001],t[100001],h[100001];
int xun(int l,int r,int c){
	int ans=0;
	if(sum[bl[l]]==c)ans+=min(r,t[bl[l]])-l+1;
	else if(sum[bl[l]]==1e18){
		for(int i=l;i<=min(r,t[bl[l]]);i++){
			if(a[i]==c)ans++;
			a[i]=c;
		}
	}else{
		for(int i=h[bl[l]];i<=t[bl[l]];i++){
			if(i>=l&&i<=min(r,t[bl[l]]))a[i]=c;
			else a[i]=sum[bl[l]];
		}sum[bl[l]]=1e18;
	}if(bl[l]!=bl[r]){
		if(sum[bl[r]]==c)ans+=r-h[bl[r]]+1;
		else if(sum[bl[r]]==1e18){
			for(int i=h[bl[r]];i<=r;i++){
				if(a[i]==c)ans++;
				a[i]=c;
			}
		}else{
			for(int i=h[bl[r]];i<=t[bl[r]];i++){
				if(i>=h[bl[r]]&&i<=r)a[i]=c;
				else a[i]=sum[bl[r]];
			}sum[bl[r]]=1e18;	
		}	
	}for(int i=bl[l]+1;i<=bl[r]-1;i++){
		if(sum[i]==c)ans+=t[i]-h[i]+1;
		else if(sum[i]==1e18){
			for(int j=h[i];j<=t[i];j++){
				if(a[j]==c)ans++;
				a[j]=c;
			}
		}sum[i]=c;
	}return ans;
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	int temp=0,k=0;
	for(int i=1;i<=n;i++){
		if(++temp==1)h[++k]=i,sum[k]=1e18;
		if(temp==(int)sqrt(n)||i==n){
			t[k]=i;
			temp=0;
		}cin>>a[i];
		bl[i]=k;
	}for(int i=1;i<=n;i++){
		int l,r,c;
		cin>>l>>r>>c;
		cout<<xun(l,r,c)<<"\n";
	}
	return 0;
}

莫队 P3901 模板

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],sq,sum[100001],ans1,l,r;
struct pio{
	int l,r,id;
};
pio z[100001];
string ans[100001];
bool cmd(pio x,pio y){
	if(x.l/sq==y.l/sq)return x.r<y.r;
	return x.l<y.l;
}void del(int x){
	if(--sum[a[x]]==0)ans1--;
}void add(int x){
	if(++sum[a[x]]==1)ans1++;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	sq=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>z[i].l>>z[i].r;
		z[i].id=i;
	}sort(z+1,z+m+1,cmd);
	for(int i=1;i<=m;i++){
		while(l<z[i].l)del(l++);
		while(l>z[i].l)add(--l);
		while(r<z[i].r)add(++r);
		while(r>z[i].r)del(r--);
		if(ans1==z[i].r-z[i].l+1)ans[z[i].id]="Yes\n";
		else ans[z[i].id]="No\n";
	}for(int i=1;i<=m;i++)cout<<ans[i];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int nxt[1000001];
string a,b;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	int j=0;
	for(int i=1;i<=b.size();i++){
		while(j&&b[i]!=b[j]){
			j=nxt[j];
		}if(b[i]==b[j]){
			nxt[i+1]=++j;
		}else nxt[i+1]=0;
	}j=0;
	for(int i=0;i<a.size();i++){
		while(j&&a[i]!=b[j]){
			j=nxt[j];
		}if(a[i]==b[j]){
			j++;
		}if(j==b.size()){
			cout<<i-b.size()+2<<"\n";
		}
	}for(int i=1;i<=b.size();i++){
		cout<<nxt[i]<<" ";
	}
	return 0;
}

manacher

#include<bits/stdc++.h>
using namespace std;
string a,b;
int l,r,ans,z[30000001]; 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a;
	b+='#';
	b+='#';
	for(int i=0;i<a.size();i++){
		b+=a[i];
		b+='#';
	}for(int i=1;i<=b.size();i++){
		if(i<=r){
			z[i]=min(z[l*2-i],r-i+1);
		}while(b[i-z[i]]==b[i+z[i]]){
			z[i]++;
		}if(z[i]+i>r){
			r=z[i]+i-1;
			l=i;
		}ans=max(ans,z[i]);
	}cout<<ans-1;
	return 0;
}

字典树

#include<bits/stdc++.h> 
using namespace std;
int t,n,q,sum[3000001],z[3000001][62],cnt;
void add(string a){
	int p=0;
	for(int i=0;i<a.size();i++){
		int x;
		if(a[i]>='0'&&a[i]<='9')x=a[i]-48;
		if(a[i]>='a'&&a[i]<='z')x=a[i]-87;
		if(a[i]>='A'&&a[i]<='Z')x=a[i]-29;
		if(!z[p][x]){
			z[p][x]=++cnt;
		}p=z[p][x];
		sum[p]++;
	}return ;
}int xun(string a){
	int p=0;
	for(int i=0;i<a.size();i++){
		int x;
		if(a[i]>='0'&&a[i]<='9')x=a[i]-48;
		if(a[i]>='a'&&a[i]<='z')x=a[i]-87;
		if(a[i]>='A'&&a[i]<='Z')x=a[i]-29;
		if(!z[p][x])return 0;
		p=z[p][x];
	}return sum[p];
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		for(int i=0;i<=cnt;i++){
			for(int j=0;j<=61;j++){
				sum[i]=0;
				z[i][j]=0;
			}
		}cnt=0;
		cin>>n>>q;
		for(int i=1;i<=n;i++){
			string a;
			cin>>a;
			add(a);
		}for(int i=1;i<=q;i++){
			string a;
			cin>>a;
			cout<<xun(a)<<"\n";
		}
	}
	return 0; 
}

#include<bits/stdc++.h>
using namespace std;
int in[5000001],son[5000001],tim,out[5000001],fa[5000001],sum[5000001],top[5000001],dep[5000001],n,m,s;
vector<int>z[5000001];
void dfs1(int x,int fath){
	fa[x]=fath;
	dep[x]=dep[fath]+1;
	sum[x]=1;
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]==fath)continue;
		dfs1(z[x][i],x);
		sum[x]+=sum[z[x][i]];
		if(sum[z[x][i]]>sum[son[x]])son[x]=z[x][i];
	}
}void dfs2(int x,int fath){
	in[x]=++tim;
	top[x]=fath;
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]==fa[x])continue;
		if(z[x][i]==son[x])dfs2(z[x][i],fath);
		else dfs2(z[x][i],z[x][i]);
	}out[x]=tim;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		z[x].push_back(y);
		z[y].push_back(x);
	}dfs1(s,0);
	dfs2(s,s);
	while(m--){
		int x,y;
		cin>>x>>y;
		while(top[x]!=top[y]){
			if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
			else y=fa[top[y]];
		}cout<<(dep[x]>=dep[y]?y:x)<<"\n";
	}
	return 0;
}

重链剖分模板

#include<bits/stdc++.h>
using namespace std;
int r1,p,a[5000001],in[5000001],son[5000001],tim,out[5000001],fa[5000001],sum[5000001],top[5000001],dep[5000001],n,m,s;
int l[5000001],r[5000001],lazy[5000001],su[5000001];
vector<int>z[5000001];
void up(int x){
	su[x]=su[x*2]+su[x*2+1];
	su[x]%=p;
}void down(int x){
	su[x*2]=(su[x*2]+(r[x*2]-l[x*2]+1)*lazy[x])%p;
	su[x*2+1]=(su[x*2+1]+(r[x*2+1]-l[x*2+1]+1)*lazy[x])%p;
	lazy[x*2]=(lazy[x*2]+lazy[x])%p;
	lazy[x*2+1]=(lazy[x*2+1]+lazy[x])%p;
	lazy[x]=0;
}int xun(int x,int l1,int r1){
	if(l1<=l[x]&&r1>=r[x])return su[x];
	if(l1>r[x]||r1<l[x])return 0;
	down(x);
	return (xun(2*x,l1,r1)+xun(x*2+1,l1,r1))%p;
}void modify(int x,int l1,int r1,int k){
	if(l1>r[x]||r1<l[x])return ;
	if(l1<=l[x]&&r1>=r[x]){
		su[x]+=(r[x]-l[x]+1)*k;
		su[x]%=p;
		lazy[x]+=k;
		lazy[x]%=p;
		return ;
	}down(x);
	modify(2*x,l1,r1,k);
	modify(2*x+1,l1,r1,k);
	up(x);
}void build(int x,int l1,int r1){
	l[x]=l1;
	r[x]=r1;
	if(l1==r1){
		lazy[x]=0;
		return ;
	}int mid=(l1+r1)>>1;
	build(x*2,l1,mid);
	build(x*2+1,mid+1,r1);
	up(x);
}void dfs1(int x,int fath){
	fa[x]=fath;
	dep[x]=dep[fath]+1;
	sum[x]=1;
	for(int i=0;i<z[x].size();i++){
		
		if(z[x][i]==fath)continue;
		dfs1(z[x][i],x);
		sum[x]+=sum[z[x][i]];
		if(sum[z[x][i]]>sum[son[x]])son[x]=z[x][i];
	}
}void dfs2(int x,int fath){
	in[x]=++tim;
	top[x]=fath;
    modify(1,in[x],in[x],a[x]);
    if(son[x])dfs2(son[x],fath);
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]==fa[x]||z[x][i]==son[x])continue;
		dfs2(z[x][i],z[x][i]);
	}out[x]=tim;
}int lca1(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<=dep[top[y]])swap(x,y);
		ans+=xun(1,in[top[x]],in[x]);
		ans%=p;
		x=fa[top[x]];
	}if(dep[x]>dep[y])swap(x,y);
	ans+=xun(1,in[x],in[y]);
	ans%=p;
	return ans;
}void lca2(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		modify(1,in[top[x]],in[x],k);
		x=fa[top[x]];
	}if(dep[x]>dep[y])swap(x,y);
	modify(1,in[x],in[y],k);
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>r1>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		z[x].push_back(y);
		z[y].push_back(x);
	}dfs1(r1,0);
	build(1,1,n);
	dfs2(r1,r1);
	 
	for(int i=1;i<=m;i++){
		int a,x,y,k;
		cin>>a>>x;
		if(a==1){
			cin>>y>>k;
			lca2(x,y,k%p);
		}if(a==2){
			cin>>y;
			cout<<lca1(x,y)<<"\n";
		}if(a==3){
			cin>>y;
			modify(1,in[x],in[x]+sum[x]-1,y%p);
		}if(a==4){
			cout<<xun(1,in[x],in[x]+sum[x]-1)<<"\n";
		}
	}return 0;
}

差分约束(小K的农场)

#include<bits/stdc++.h>
using namespace std;
int n,m,sum[100001],a[100001],vis[100001],d[100001],ans; 
struct pio{
	int v,w;
};
vector<pio>z[100001];
queue<int>q;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)d[i]=1e9;
	for(int i=1;i<=m;i++){
		int a,x,y,quan; 
		cin>>a>>x>>y;
		if(a==1){
			cin>>quan;
			z[x].push_back({y,-quan}); 
		}else if(a==2){
			cin>>quan;
			z[y].push_back({x,quan});
		}else {
			z[x].push_back({y,0});
			z[y].push_back({x,0});
		}
	}for(int i=1;i<=n;i++)z[0].push_back({i,0});
	vis[0]=1;
	q.push(0);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=0;i<z[u].size();i++){
			int v=z[u][i].v,w=z[u][i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(!vis[v]){
					q.push(v);
					sum[v]++;
					vis[v]=1;
					if(sum[v]>n){
						cout<<"No";
						return 0;
					}
				}
			}
		}
	}cout<<"Yes";
	return 0;
}

树形DP

#include<bits/stdc++.h>
using namespace std;
int n,q,x[6005],dp[6005][2];
vector<int>z[6005];
void dfs(int x){
	for(int i=0;i<z[x].size();i++){
		dfs(z[x][i]);
		dp[x][1]+=dp[z[x][i]][0];
		dp[x][0]+=max(dp[z[x][i]][0],dp[z[x][i]][1]);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>dp[i][1];
	for(int i=1;i<n;i++){
		int l,k;
		cin>>l>>k;
		x[l]=1;
		z[k].push_back(l);
	}for(int i=1;i<=n;i++){
		if(!x[i]){
			dfs(i);
			cout<<max(dp[i][0],dp[i][1]);
		}
	}
	return 0;
}

树形背包

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001];
vector<vector<int>>dp;
vector<int>z[100001];
int dfs(int x){
	int usize=1;
	dp[x][1]=a[x]; 
	for(int i=0;i<z[x].size();i++){
		int vsize=dfs(z[x][i]);
		usize+=vsize;
		for(int j=min(m+1,usize);j>=1;j--){
			for(int k=0;k<j&&k<=vsize;k++){
				dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[z[x][i]][k]);
			}
		}
	}return usize;
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	dp=vector<vector<int>>(n+1,vector<int>(m+2));
	for(int i=1;i<=n;i++){
		int p;
		cin>>p>>a[i];
		z[p].push_back(i);
	}dfs(0);
	cout<<dp[0][m+1];
	return 0;
}

P1725

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,r,a,hh=1,rr=0,dp[200001],q[200001],ans=-2e18;
signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>l>>r>>a;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		while(hh<=rr&&q[hh]+r<i)hh++;
		if(i>=l){
			while(hh<=rr&&dp[i-l]>dp[q[rr]])rr--;
			q[++rr]=i-l;
		}if(hh<=rr)dp[i]=dp[q[hh]]+x;
		else dp[i]=-2e18;
		if(i+r>n)ans=max(ans,dp[i]);
	}cout<<ans;
	return 0;
}

P1776

#include<bits/stdc++.h>
using namespace std;
int n,m,v,w,k,q[40001],q2[40001],t,h,dp[40001];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v>>w>>k;
		int K=min(k,m/w);
		for(int d=0;d<w;d++){
			h=1;
			t=0;
			for(int j=0;j*w+d<=m;j++){
				while(t>=h&&dp[j*w+d]-j*v>q2[t])t--;
				q2[++t]=dp[j*w+d]-j*v;
				q[t]=j;
				if(h<t&&j-q[h]==K+1)h++;
				dp[d+j*w]=q2[h]+j*v;
			}
		}
	}cout<<dp[m];
	return 0;
}

lca

#include<bits/stdc++.h>
using namespace std;
int n,m,p,st[500001][21],dep[500001];
vector<int>z[500001];
void dfs(int x,int fa){
	st[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]!=fa){
			dfs(z[x][i],x);
		}
	}
}int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if((1<<i)<=dep[x]-dep[y])x=st[x][i];
	}if(x==y)return x;
	for(int i=19;i>=0;i--){
		if((1<<i)<=dep[x]&&st[x][i]!=st[y][i]){
			x=st[x][i];
			y=st[y][i];
		}
	}return st[x][0];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>p;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		z[x].push_back(y);
		z[y].push_back(x);
	}dfs(p,0);
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			if((1<<i)>dep[j])continue;
			st[j][i]=st[st[j][i-1]][i-1];
		}
	}while(m--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<"\n";
	}
	return 0;
}

树上差分

#include<bits/stdc++.h>
using namespace std;
int n,m,p,u[500001],v[500001],siz[500001],st[500001][21],dep[500001],a[500001];
vector<int>z[500001];
void dfs(int x,int fa){
	st[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]!=fa){
			dfs(z[x][i],x);
		}
	}
}void dfs2(int x,int fa){
	for(int i=0;i<z[x].size();i++){
		if(z[x][i]!=fa){
			dfs2(z[x][i],x);
			siz[x]+=siz[z[x][i]];
		}
	}
}int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if((1<<i)<=dep[x]-dep[y])x=st[x][i];
	}if(x==y)return x;
	for(int i=19;i>=0;i--){
		if((1<<i)<=dep[x]&&st[x][i]!=st[y][i]){
			x=st[x][i];
			y=st[y][i];
		}
	}return st[x][0];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>u[i]>>v[i];
		z[u[i]].push_back(v[i]);
		z[v[i]].push_back(u[i]);
	}dfs(1,0);
	for(int i=1;i<=19;i++){
		for(int j=1;j<=n;j++){
			if((1<<i)>dep[j])continue;
			st[j][i]=st[st[j][i-1]][i-1];
		}
	}for(int i=1;i<n;i++){
		int x=a[i],y=a[i+1];
		siz[x]++;
		siz[y]++;
		int l=lca(x,y);
		siz[l]--;
		siz[st[l][0]]--;
	}dfs2(1,0);
	for(int i=2;i<=n;i++)siz[a[i]]--;
	for(int i=1;i<=n;i++)cout<<siz[i]<<"\n";
	return 0;
}

欧拉路径模板(单向边)

双向边邻接矩阵

相关：

无序字母对

词链

模板单向

#include<bits/stdc++.h>
using namespace std;
int n,m,du[200005],duu[200005],top[200005],now[200005],stk[200005],cnt,aa,bb;
bool ppp=0; 
vector<int>z[200005];
void dfs(int x){
	for(;top[x]<z[x].size();){
		dfs(z[x][top[x]++]);
	}stk[++cnt]=x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		z[x].push_back(y);
		du[x]++;//出 
		duu[y]++;//入 
	}for(int i=1;i<=n;i++){
		sort(z[i].begin(),z[i].end());
	}for(int i=1;i<=n;i++){
		if(duu[i]+1==du[i]&&!ppp){
			aa++;
			ppp=1;
			dfs(i);
		}if(duu[i]==du[i]+1){
			bb++;
		}if(abs(duu[i]-du[i])>1){
			cout<<"No";
			return 0;
		}
	}if(aa==1&&bb==1||aa==0&&bb==0){
		if(!ppp){
			dfs(1);
		}for(int i=m+1;i>=1;i--){
			cout<<stk[i]<<" ";
		}
	}else {
		cout<<"No\n";
	}return 0;
}

双向邻接矩阵

#include<bits/stdc++.h>
using namespace std;
int n,p[2000],now[2000],stk[3000],a[505][505],nn,nnn=1e9,start,cnt;
bool ppp=0; 
void dfs(int x){
	for(int i=1;i<=nn;i++){
		if(a[x][i]){
			a[x][i]--;
			a[i][x]--;
			dfs(i);
		}
	}stk[++cnt]=x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]++;
		a[y][x]++;
		p[x]++;
		p[y]++;
		nn=max({nn,x,y});
		nnn=min({nnn,x,y});
	}for(int i=nnn;i<=nn;i++){
		if(p[i]%2==1){
			ppp=1;
			cnt=0;
			dfs(i);break;
		}
	}if(!ppp){
		dfs(nnn);
	}for(int i=cnt;i>=1;i--){
		cout<<stk[i]<<"\n";
	}return 0;
}

无序字母对

#include<bits/stdc++.h>
using namespace std;
int ansss,n,p[2000],now[2000],stk[3000],a[505][505],nn,nnn=1e9,start,cnt;
bool ppp=0; 
set<int>ss;
void dfs(int x){
	for(int i=1;i<=nn;i++){
		if(a[x][i]){
			a[x][i]--;
			a[i][x]--;
			dfs(i);
		}
	}stk[++cnt]=x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		char x1,y1;
		cin>>x1>>y1;
		int x=x1,y=y1;
		a[x][y]++;
		a[y][x]++;
		p[x]++;
		p[y]++;
		nn=max({nn,x,y});
		nnn=min({nnn,x,y});
		ss.insert(x);
		ss.insert(y);
	}if(ss.size()>n+1){
		cout<<"No Solution\n";
		return 0;
	}for(int i=nnn;i<=nn;i++){
		if(p[i]%2==1)ansss++;
	}if(ansss>2){
		cout<<"No Solution\n";
		return 0;
	}for(int i=nnn;i<=nn;i++){
		if(p[i]%2==1){
			ppp=1;
			cnt=0;
			dfs(i);break;
		}
	}if(!ppp){
		dfs(nnn);
	}for(int i=cnt;i>=1;i--){
		cout<<char(stk[i]);
	}return 0;
}

相关题单

AT_abl_d

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[300005],dp[300005],mx[12000005];
void modify(int x,int l,int r,int p,int k){
	if(l==r){
		mx[x]=k;
		return ;
	}int mid=(l+r)/2;
	if(p<=mid)modify(x*2,l,mid,p,k);
	else modify(x*2+1,mid+1,r,p,k);
	mx[x]=max(mx[x*2],mx[x*2+1]);
}int xun(int x,int l,int r,int l1,int r1){
	if(l>r1||r<l1)return 0;
	if(l>=l1&&r<=r1)return mx[x];
	int mid=(l+r)/2;
	return max(xun(x*2,l,mid,l1,r1),xun(x*2+1,mid+1,r,l1,r1));
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}for(int i=1;i<=n;i++){
		dp[i]=xun(1ll,1ll,3000005,max(1ll,a[i]-m),a[i]+m)+1;
		modify(1ll,1ll,3000005,a[i],dp[i]);
	}cout<<mx[1];
	return 0;
}

P3431

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500001;
int n,m,k,x[N],y[N],mx[N];
struct pio{
	int x,y,p;
};
bool cmd(pio a,pio b){
	if(a.x!=b.x)return a.x<b.x;
	return a.y<b.y;
}void up(int x){
	mx[x]=max(mx[x*2],mx[x*2+1]);
}void modify(int x,int l1,int r1,int l,int r,int k){
	if(l1==l&&r1==r){
		mx[x]=max(k,mx[x]);
		return ;
	}if(l1>r||r1<l)return ;
	int mid=(l+r)/2;
	modify(x*2,l1,r1,l,mid,k);
	modify(x*2+1,l1,r1,mid+1,r,k);
	up(x);
}int xun(int x,int l1,int r1,int l,int r){
	if(l1>r||r1<l)return 0;
	if(l1<=l&&r1>=r){
		return mx[x];
	}int mid=(l+r)/2;
	return max(xun(x*2,l1,r1,l,mid),xun(x*2+1,l1,r1,mid+1,r));
}pio z[100001];
map<int,int>mm,mp;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>x[i]>>y[i]>>z[i].p;
		z[i]={x[i],y[i],z[i].p};
	}sort(x+1,x+k+1);
	sort(y+1,y+k+1);
	int cnt=0,cntt=0;
	for(int i=1;i<=k;i++){
		if(!mm[x[i]])mm[x[i]]=++cnt;
		if(!mp[y[i]])mp[y[i]]=++cntt;
	}for(int i=1;i<=k;i++){
		z[i]={mm[z[i].x],mp[z[i].y],z[i].p};
//		cout<<z[i].x<<" "<<z[i].y<<" "<<z[i].p<<"\n";
	}sort(z+1,z+k+1,cmd);
	for(int i=1;i<=k;i++){
		int aa=xun(1,1,z[i].y,1,100000);
		aa+=z[i].p;
//		cout<<aa<<" "<<z[i].x<<" "<<z[i].y<<" "<<z[i].p<<"\n";
		modify(1,z[i].y,z[i].y,1,100000,aa); 
	}cout<<mx[1];
	return 0;
}

CF833B

#include<bits/stdc++.h>
using namespace std;
int lst[200001],lstt[200001],n,m,l[200001],r[200001],p[200001],a[200001],sum[200001],lazy[200001],dp[200001];
void up(int x){
	sum[x]=max(sum[x*2],sum[x*2+1]);
}void down(int x){
	sum[x*2]+=lazy[x];
	sum[x*2+1]+=lazy[x];
	lazy[x*2]+=lazy[x];
	lazy[x*2+1]+=lazy[x];
	lazy[x]=0;
}void build(int x,int l1,int r1){
	l[x]=l1;
	r[x]=r1;
	lazy[x]=0;
	if(l1==r1){
		sum[x]=dp[l1-1];
		return;
	}int mid=(l1+r1)/2;
	build(x*2,l1,mid);
	build(x*2+1,mid+1,r1);
	up(x);
}void modify(int x,int l1,int r1,int k){
	if(r[x]<l1||l[x]>r1)return ;
	if(l1<=l[x]&&r1>=r[x]){
		sum[x]+=k;
		lazy[x]+=k;
		return ;		
	}down(x);
	modify(x*2,l1,r1,k);
	modify(x*2+1,l1,r1,k);
	up(x);
}int xun(int x,int l1,int r1){
	if(r[x]<l1||l[x]>r1)return 0;
	if(r[x]<=r1&&l[x]>=l1){
		return sum[x];
	}down(x);
	return max(xun(x*2,l1,r1),xun(x*2+1,l1,r1));
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		lst[i]=lstt[a[i]];
		lstt[a[i]]=i;
	}for(int i=1;i<=m;i++){
		build(1,1,n);
		for(int j=1;j<=n;j++){
			modify(1,lst[j]+1,j,1);
			dp[j]=xun(1,1,j);
//			cout<<dp[j]<<"\n";
		}
	}cout<<dp[n]<<"\n";
	return 0;
}

高斯消元相关提单 线性基相关题单 oi-wiki

高斯消元加法模板

#include<bits/stdc++.h>
using namespace std;
int n;
double z[105][105]; 
int xiao(){
	int h=1,l=1;
	for(;l<=n;l++){
		for(int i=h+1;i<=n;i++){
			if(abs(z[i][l])>abs(z[h][l]))swap(z[i],z[h]);
		}if(abs(z[h][l])<1e-6)continue;
		double a=z[h][l];
		for(int i=l;i<=n+1;i++){
			z[h][i]/=a;
		}for(int i=1;i<=n;i++){
			if(i==h)continue;
			double aa=z[i][l];
			for(int j=l;j<=n+1;j++){
				z[i][j]-=z[h][j]*aa;
			}
		}h++;
	}if(h>n)return 1;
	for(int i=h;i<=n;i++){
		if(abs(z[i][n+1])>1e-6)return -1;
	}return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			cin>>z[i][j];
		}
	}int fl=xiao();
	if(fl==1){
		for(int i=1;i<=n;i++){
			cout<<fixed<<setprecision(2)<<"x"<<i<<"="<<z[i][n+1]<<"\n";
		}
	}else cout<<fl;
	return 0;
}

高斯消元异或模板

#include<bits/stdc++.h>
using namespace std;
int n,m,maxn;
pair<string,int>z[2005]; 
int xiao(){
	int h=1,l=0;
	for(;l<n;l++){
		for(int i=h;i<=m;i++){
			if(z[i].first[l]=='1'){
				swap(z[i],z[h]);
				maxn=max(maxn,i);
				break;
			}
		}if(z[h].first[l]=='0')continue;
		for(int i=1;i<=m;i++){
			if(i==h)continue;
			if(z[i].first[l]=='1'){
				for(int j=0;j<n;j++){
					z[i].first[j]=char((z[i].first[j]^z[h].first[j])+48);
				}z[i].second^=z[h].second;
			}
		}h++;
	}if(h>n)return h;
	return -1;
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		string a;
		int b;
		cin>>a>>b;
		z[i]=(make_pair(a,b));
	}int fl=xiao();
	if(fl==-1){
		cout<<"Cannot Determine";
	}else {
		cout<<maxn<<"\n";
		for(int i=1;i<=n;i++){
			if(z[i].second==0)cout<<"Earth\n";
			else cout<<"?y7M#\n";
		}
	}
	return 0;
}

线性基模板

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[55],p[55],vis[55],ans;
void insert(int x){
	for(int i=50;i>=0;i--){
		if(!(x>>i))continue;
		if(!p[i]){
			p[i]=x;
			break;
		}x^=p[i];
	}
}signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}for(int i=50;i>=0;i--){
		ans=max(ans,ans^p[i]);
	}cout<<ans;
	return 0;
}