函数C

long long C(long long n,long long m){
	long long s=1,a=n,b=1;
	rep(i,1,m){
		s=s*a/b;
		a--;
		b++;
	}
	return s;
}

(函数C组合式)

long long qupow(long long a,long long b,long long p){
	long long s=1;
	a%=p;
	while(b){
		if(b%2==1) s=(a*s)%p;
		a*=a;
		b>>=1;
		a%=p;
	}
	return s;
}
long long add(long long n,long long mod){
	long long s=1;
	rep(i,1,n) s=s*i%mod;
	return s;
}
long long C(long long n,long long m){
	return add(n,M)*qupow(add(m,M),M-2,M)%M*qupow(add(n-m,M),M-2,M)%M;
}

(函数C组合式plus+线性乘法逆元+lucas)

long long qupow(long long a,long long b,long long p){
	long long s=1;
	a%=p;
	while(b){
		if(b%2==1) s=(a*s)%p;
		a*=a;
		b>>=1;
		a%=p;
	}
	return s;
}
void init(){
	fac[0]=inv[0]=1;
	rep(i,1,p-1) fac[i]=fac[i-1]*i%p;
	inv[p-1]=qupow(fac[p-1],p-2,p);
	for(int i=p-2;i;--i) inv[i]=inv[i+1]*(i+1)%p;
}
long long C(long long n,long long m){
	if(m>n) return 0;
	return fac[n]*inv[m]%p*inv[n-m]%p;
}
long long lucas(long long n,long long m){
	long long ans=1;
	for(;m;n/=p,m/=p){
		ans=ans*C(n%p,m%p)%p;
	}
	return ans;
}

强连通分量

void tarjan(long long x){
	dfn[x]=low[x]=++num;
	q.push(x);
	for(long long i=0;i<g[x].size();++i){
		long long j=g[x][i];
		if(!dfn[j]){
			tarjan(j);
			low[x]=min(low[x],low[j]);
		}
		else if(!an[j]) low[x]=min(low[x],dfn[j]);
	}
	if(low[x]==dfn[x]){
		an[x]=++s;
		ans[s].push_back(x);
		while(q.size()&&q.top()!=x){
			ans[s].push_back(q.top());
			an[q.top()]=s;
			q.pop();
		}
		q.pop();
	}
}

找桥（割边）

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(long long i=a;i<=b;++i)
using namespace std;
const long long N=2e5+7;
long long a[N],p[N],now[N],son[N],an[N],dfn[N],low[N],t=0,n,m,num,ans;
void put(long long a,long long b){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
}
void tarjan(long long x,long long in){
	dfn[x]=low[x]=++num;
	long long neww=in;
	if(in&1) neww++;
	else neww--;
	for(long long i=now[x];i;i=p[i]){
		long long j=son[i];
		if(!dfn[j]){
			tarjan(j,i);
			low[x]=min(low[x],low[j]);
			if(low[j]>dfn[x]){
				an[i]=1;
				if(i&1) an[i+1]=1;
				else an[i-1]=1;
			}
		}
		else if(i!=neww) low[x]=min(low[x],dfn[j]);
	}
}
int main(){
	cin>>n>>m;
	rep(i,1,m){
		long long u,v;
		cin>>u>>v;
		put(u,v);
		put(v,u);
	}
	rep(i,1,n) if(!dfn[i]) tarjan(i,0);
	for(int i=1;i<=t;i+=2){
		if(an[i]) ans++;
	}
	cout<<ans<<"\n";
	return 0;
}

割点及点双联通分量

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=5e5+7;
int a[N],an[N],dfn[N],low[N],sum[N],t=0,n,m,num,s;
vector<int> g[N],ans[N];
stack<int> q;
void tarjan(int x,int fa,int gen){
	dfn[x]=low[x]=++num;
	q.push(x);
	int flag=0;
	for(int i=0;i<g[x].size();i++){
		int j=g[x][i];
		if(!dfn[j]){
			tarjan(j,x,gen);
			low[x]=min(low[x],low[j]);
			if(low[j]>=dfn[x]){
				flag++;
				ans[++s].push_back(x);
				while(q.size()&&q.top()!=j){
					ans[s].push_back(q.top());
					q.pop();
				}
				ans[s].push_back(j);
				q.pop();
				if(x!=gen||flag>1) an[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[j]);
	}
	if(flag==0&&x==gen){
		ans[++s].push_back(x);
	}
}
int main(){
	cin>>n>>m;
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	rep(i,1,n) if(!dfn[i]) tarjan(i,0,i);
	int ss=0;
	rep(i,1,n){
		if(an[i]) ss++;
	}
	cout<<ss<<"\n";
	rep(i,1,n){
		if(an[i]) cout<<i<<" ";
	}
	return 0;
}

边双连通分量

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(long long i=a;i<=b;++i)
using namespace std;
const long long N=4e6+7;
long long p[N],now[N],son[N],an[N],dfn[N],low[N],sum[N],v[N],t=0,n,m,num,s;
vector<long long> g[N];
void put(long long a,long long b){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
}
void tarjan(long long x,long long in){
	dfn[x]=low[x]=++num;
	long long neww=in;
	if(in&1) neww++;
	else neww--;
	for(long long i=now[x];i;i=p[i]){
		long long j=son[i];
		if(!dfn[j]){
			tarjan(j,i);
			low[x]=min(low[x],low[j]);
			if(low[j]>dfn[x]){
				an[i]=1;
				if(i&1) an[i+1]=1;
				else an[i-1]=1;
			}
		}
		else if(i!=neww) low[x]=min(low[x],dfn[j]);
	}
}
void dfs(long long x,long long u){
	sum[u]++;
	v[x]=u;
	g[u].push_back(x);
	for(long long i=now[x];i;i=p[i]){
		long long j=son[i];
		if(!v[j]&&!an[i]){
			dfs(j,u);
		}
	}
}
int main(){
	cin>>n>>m;
	rep(i,1,m){
		long long u,v;
		cin>>u>>v;
		put(u,v);
		put(v,u);
	}
	rep(i,1,n) if(!dfn[i]) tarjan(i,0);
	rep(i,1,n) if(!v[i]) dfs(i,++s);
	cout<<s<<"\n";
	rep(i,1,s){
		cout<<sum[i]<<" ";
		rep(j,0,g[i].size()-1){
			cout<<g[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

hash

  #include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=1e6+7,M=1e9+7,B=133;
long long p[N],n,ans,num;
char c[N];
map<int,int> q; 
int main(){
	p[0]=1;
	rep(i,1,1e6){
		p[i]=p[i-1]*B%M;
	}
	cin>>n;
	rep(i,1,n){
		scanf("%s",c+1);
		long long l=strlen(c+1);
		num=0;
		rep(i,1,l){
			num=((num*B%M)+(c[i]-'a'+1))%M;
		}
		if(q[num]==0) ans++;
		q[num]=1;
	}
	cout<<ans;
	return 0;
}

hash字符串

#include <bits/stdc++.h>
#define int long long
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=1e6+7,M=1e9+7,B=19260817;
int p[N],sum[N],ans;
string c1,c2;
int check(int l,int r){
	return (sum[r]-sum[l-1]*p[r-l+1]%M+M)%M;
}
signed main(){
	cin>>c1>>c2;
	p[0]=1;
	rep(i,1,c1.size()){
		p[i]=p[i-1]*B%M;
	}
	rep(i,1,c1.size()){
		sum[i]=((sum[i-1]*B%M)+(c1[i-1]))%M;
	}
	int s=0;
	rep(i,1,c2.size()){
		s=((s*B%M)+(c2[i-1]))%M;
	}
	rep(i,1,c1.size()-c2.size()+1){
		if(check(i,i+(c2.size())-1)==s){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

双hash

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=1e6+7,M=1e9+7,B1=133,B2=133;
long long p1[N],p2[N],sum1[N],sum2[N],n,ans,num;
char c[N];
bool check1(long long l1,long long r1,long long l2,long long r2){
	long long l=r1-l1+1;
	return (((sum1[r1]-sum1[l1-1]*p1[l]%M)+M)%M)==(((sum1[r2]-sum1[l2-1]*p1[l]%M)+M)%M);
}
bool check2(long long l1,long long r1,long long l2,long long r2){
	long long l=r1-l1+1;
	return (((sum2[r1]-sum2[l1-1]*p2[l]%M)+M)%M)==(((sum2[r2]-sum2[l2-1]*p2[l]%M)+M)%M);
}
int main(){
	scanf("%s",c+1);
	long long l=strlen(c+1);
	p1[0]=p2[0]=sum1[0]=sum2[0]=1;
	rep(i,1,l){
		p1[i]=p1[i-1]*B1%M;
	}
	rep(i,1,l){
		p2[i]=p2[i-1]*B2%M;
	}
	rep(i,1,l){
		sum1[i]=((sum1[i-1]*B1%M)+(c[i]-'a'+1))%M;
	}
	rep(i,1,l){
		sum2[i]=((sum2[i-1]*B2%M)+(c[i]-'a'+1))%M;
	}
	cin>>n;
	rep(i,1,n){
		long long l1,r1,l2,r2;
		scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
		if(r1-l1!=r2-l2){
			cout<<"No\n";
			continue;
		}
		if(check1(l1,r1,l2,r2)&&check1(l1,r1,l2,r2)) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

AC自动机

class AC{
	private:
		struct node{
			int idx,fail,du,s;
			int son[27];
			void init(){
				memset(son,0,sizeof son);
				idx=fail=du=s=0;
			}
		}s[N];
	public:
		int cnt,ans[N],ids;
		void init(){
			cnt=ids=0;
			memset(ans,0,sizeof ans);
			s[0].init();
		}
		void adg(string c,int &id){
			int u=0;
			rep(i,1,c.size()){
				if(s[u].son[c[i-1]-'a']==0){
					s[u].son[c[i-1]-'a']=++cnt;
					s[cnt].init();
				}
				u=s[u].son[c[i-1]-'a'];
			}
			if(s[u].idx==0){
				s[u].idx=++ids;
			}
			id=s[u].idx;
		}
		void add(){
			queue<int> q;
			rep(i,0,25){
				if(s[0].son[i]!=0) q.push(s[0].son[i]);
			}
			while(q.size()){
				int u=q.front();
				q.pop();
				rep(i,0,25){
					if(s[u].son[i]!=0){
						s[s[u].son[i]].fail=s[s[u].fail].son[i];
						s[s[s[u].fail].son[i]].du++;
						q.push(s[u].son[i]);
					}
					else{
						s[u].son[i]=s[s[u].fail].son[i];
					}
				}
			}
		}
		void tp(){
			queue<int> q;
			rep(i,0,cnt){
				if(s[i].du==0) q.push(i);
			}
			while(q.size()){
				int u=q.front();
				q.pop();
				ans[s[u].idx]=s[u].s;
				int v=s[u].fail;
				s[v].s+=s[u].s;
				s[v].du--;
				if(s[v].du==0){
					q.push(v);
				}
			}
		}
		void find(string c){
			int u=0;
			rep(i,1,c.size()){
				u=s[u].son[c[i-1]-'a'];
				s[u].s++;
			}
			tp();
		}
};

AC自动机（含匹配程度）

class AC{
	private:
		struct node{
			int idx,fail,du,s;
			int son[27];
			void init(){
				memset(son,0,sizeof son);
				idx=fail=du=s=0;
			}
		}s[N];
	public:
		int cnt,ans[N],v[N],ids;
		void init(){
			cnt=ids=0;
			memset(ans,0,sizeof ans);
			memset(v,0,sizeof v);
			s[0].init();
		}
		void adg(string c,int &id){
			int u=0;
			rep(i,1,c.size()){
				if(s[u].son[c[i-1]-'A']==0){
					s[u].son[c[i-1]-'A']=++cnt;
					s[cnt].init();
				}
				u=s[u].son[c[i-1]-'A'];
			}
			if(s[u].idx==0){
				s[u].idx=++ids;
			}
			id=s[u].idx;
		}
		void add(){
			queue<int> q;
			rep(i,0,25){
				if(s[0].son[i]!=0) q.push(s[0].son[i]);
			}
			while(q.size()){
				int u=q.front();
				q.pop();
				rep(i,0,25){
					if(s[u].son[i]!=0){
						s[s[u].son[i]].fail=s[s[u].fail].son[i];
						s[s[s[u].fail].son[i]].du++;
						q.push(s[u].son[i]);
					}
					else{
						s[u].son[i]=s[s[u].fail].son[i];
					}
				}
			}
			int u=0;
			rep(i,1,c[0].size()){
				u=s[u].son[c[0][i-1]-'A'];
				for(int j=u;j&&v[j]==0;j=s[j].fail) v[j]=1;
			}
		}
		void tp(){
			queue<int> q;
			rep(i,0,cnt){
				if(s[i].du==0) q.push(i);
			}
			while(q.size()){
				int u=q.front();
				q.pop();
				ans[s[u].idx]=s[u].s;
				int v=s[u].fail;
				s[v].s+=s[u].s;
				s[v].du--;
				if(s[v].du==0){
					q.push(v);
				}
			}
		}
		void find(string c){
			int u=0;
			rep(i,1,c.size()){
				u=s[u].son[c[i-1]-'A'];
				s[u].s++;
			}
			tp();
		}
		int finds(string c){
			int u=0,ans=0;
			rep(i,1,c.size()){
				u=s[u].son[c[i-1]-'A'];
				if(v[u]) ans=i;
			}
			return ans;
		}
};

最小生成树(prim)

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=1007,M=1e6+7;
struct node{
	int u,v;
}b[M];
int a[N][N],v[N],dp[N][N],f[N],mi[N],n,m,q;
int main(){
	cin>>n>>m>>q;
	rep(i,1,n){
		rep(j,1,n){
			if(i!=j) a[i][j]=INT_MAX;
		}
	}
	rep(i,1,m){
		int u,v,w;
		cin>>u>>v>>w;
		a[u][v]=min(a[u][v],w);
		a[v][u]=a[u][v];
		b[i].u=u;
		b[i].v=v;
	}
	memset(mi,0x3f3f,sizeof mi);
	f[1]=1;
	mi[1]=0;
	rep(i,1,n){
		int k=0;
		rep(j,1,n){
			if(v[j]==0&&mi[j]<mi[k]){
				k=j;
			}
		}
		rep(j,1,n){
			if(v[j]){
				dp[j][k]=max(dp[j][f[k]],a[f[k]][k]);
				dp[k][j]=dp[j][k];
			}
		}
		v[k]=1;
		rep(j,1,n){
			if(v[j]==0&&a[k][j]<mi[j]){
				mi[j]=a[k][j];
				f[j]=k;
			}
		}
	}
	rep(i,1,q){
		int x,y,z1,z2;
		cin>>x>>y;
		z1=b[x].u;
		z2=b[x].v;
		if(dp[z1][z2]>=y) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

最小生成树(krustal)

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=1e6+7;
struct node{
	double x,y;
}d[N];
struct no{
	double n;
	int u,v;
}c[N];
double ans=0;
int a[N],n,m,sum;
bool cmp(no a,no b){
	return a.n<b.n;
}
int find(int x){
	if(a[x]!=x) a[x]=find(a[x]);
	return a[x];
}
int main(){
	while(cin>>n&&n!=0){
		ans=sum=m=0;
		rep(i,1,n){
			cin>>d[i].x>>d[i].y;
		}
		rep(i,1,n){
			rep(j,1,n){
				if(i!=j){
					c[++sum]={sqrt(fabs(d[i].x-d[j].x)*fabs(d[i].x-d[j].x)+fabs(d[i].y-d[j].y)*fabs(d[i].y-d[j].y)),i,j};
				}
			}
			a[i]=i;
		}
		sort(c+1,c+1+sum,cmp);
		int i=1;
		while(m!=n-1){
			int x=c[i].u,y=c[i].v;
			int p=find(x),q=find(y);
			if(p!=q){
				a[p]=q;
				m++;
				ans+=c[i].n;
			}
			i++;
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

并查集

int find(int x){
	if(a[x]!=x) a[x]=find(a[x]);
	return a[x];
}

莫队

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=5e4+7,M=2e2+7;
int n,m,a[N],nn,X[N],b[N],f[N];
long long s,an[N];
struct node{
	int s,l,r;
};
node c[N];
struct ques{
	int l,r,id;
};
ques q[N],qq[N];
void adg(int &l,int &r,int x,int y,int z){
	int d=x?l:r;
	if(x) l+=y;
	else r+=y;
	if(z==0){
		s-=f[a[d]]*f[a[d]];
		f[a[d]]--;
		s+=f[a[d]]*f[a[d]];
	}
	d+=y;
	if(z==1){
		s-=f[a[d]]*f[a[d]];
		f[a[d]]++;
		s+=f[a[d]]*f[a[d]];	
	}
}
bool cmp(ques a,ques bb){
	if(b[a.l]!=b[bb.l]) return b[a.l]<b[bb.l];
	if(b[a.l]&1) return a.r<bb.r;
	return a.r>bb.r;
}
void md(){
	int l=q[1].l,r=q[1].r;
	rep(i,l,r){
		s-=f[a[i]]*f[a[i]];
		f[a[i]]++;
		s+=f[a[i]]*f[a[i]];
	}
	an[q[1].id]=s;
	rep(i,2,m){
		while(l>q[i].l) adg(l,r,1,-1,1);
		while(r<q[i].r) adg(l,r,0,1,1);
		while(l<q[i].l) adg(l,r,1,1,0);
		while(r>q[i].r) adg(l,r,0,-1,0);
		an[q[i].id]=s;
	}
}
int main(){
	cin>>n>>m;
	int t=sqrt(n);
	rep(i,1,n){
		cin>>a[i];
		b[i]=(i-1)/t+1;
		if(c[b[i]].l==0) c[b[i]].l=i;
		c[b[i]].r=i;
		X[i]=a[i];
	}
	sort(X+1,X+1+n);
	nn=unique(X+1,X+1+n)-X-1;
	rep(i,1,n){
		a[i]=lower_bound(X+1,X+1+nn,a[i])-X;
	}
	rep(i,1,m){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
		qq[i]=q[i];
	}
	sort(q+1,q+1+m,cmp);
	md();
	rep(i,1,m){
		long long l=qq[i].l,r=qq[i].r;
		if(an[i]==(r-l+1)) cout<<"0/1\n";
		else{
			long long x=an[i]-(r-l+1),y=(r-l+1)*(r-l);
			int g=__gcd(x,y);
			x/=g;
			y/=g;
			cout<<x<<"/"<<y<<"\n";
		}
	}
	return 0;
}

回滚莫队（只加不减）

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=2e5+7,M=2e2+7;
int n,m,a[N],nn,b[N],f[N],f2[N];
long long X[N];
long long s,an[N];
struct node{
	int s,l,r;
};
node c[N];
struct ques{
	int l,r,id;
};
ques q[N];
void adg(int &l,int &r,int x,int y,int z){
	int d=x?l:r;
	if(x) l+=y;
	else r+=y;
	if(z==0){
		f[a[d]]--;
	}
	d+=y;
	if(z==1){
		f[a[d]]++;
		s=max(s,f[a[d]]*X[a[d]]);
	}
}
bool cmp(ques a,ques bb){
	if(b[a.l]!=b[bb.l]) return b[a.l]<b[bb.l];
	return a.r<bb.r;
}
void md(){
	int l=1,r=0;
	rep(i,1,m){
		if(b[q[i].l]!=b[q[i-1].l]){
			rep(j,l,r){
				f[a[j]]=0;
			}
			l=c[b[q[i].l]].r+1;
			r=c[b[q[i].l]].r;
			s=0;
		}
		if(b[q[i].l]==b[q[i].r]){
			long long ss=0;
			rep(j,q[i].l,q[i].r){
				f2[a[j]]++;
				ss=max(ss,f2[a[j]]*X[a[j]]);
			}
			rep(j,q[i].l,q[i].r){
				f2[a[j]]--;
			}
			an[q[i].id]=ss;
			continue;
		}
		while(r<q[i].r) adg(l,r,0,1,1);
		long long la=s;
		while(l>q[i].l) adg(l,r,1,-1,1);
		while(l<c[b[q[i].l]].r+1) adg(l,r,1,1,0);
		an[q[i].id]=s;
		s=la;
	}
}
int main(){
	cin>>n>>m;
	int t=sqrt(n);
	rep(i,1,n){
		cin>>a[i];
		b[i]=(i-1)/t+1;
		if(c[b[i]].l==0) c[b[i]].l=i;
		c[b[i]].r=i;
		X[++nn]=a[i];
	}
	sort(X+1,X+1+nn);
	nn=unique(X+1,X+1+nn)-X-1;
	rep(i,1,n){
		a[i]=lower_bound(X+1,X+1+nn,a[i])-X;
	}
	rep(i,1,m){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	md();
	rep(i,1,m){
		cout<<an[i]<<"\n";
	}
	return 0;
}

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e3+7,M=3e5+7;
long long n,m,d[N],d2[N],S,T,t=1,t2,p[M],now[N],son[M],val[M],noww[N],nowww[N],h[N],ans;
struct node{
	long long u,v,w1,w2;
};
node a[M];
void put(int a,int b,long long c){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
}
bool bfs(){
	rep(i,1,n+2){
		noww[i]=now[i];
		h[i]=0;
	}
	h[S]=1;
	queue<int> q;
	q.push(S);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]==0){
				h[y]=h[u]+1;
				q.push(y);
				if(y==T) return 1;
			}
		}
	}
	return 0;
}
long long dfs(int x,long long s){
	if(x==T) return s;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(val[i]&&h[y]==h[x]+1){
			long long ss=dfs(y,min(s,val[i]));
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18);
	}
}
int main(){
	cin>>n>>m;
	S=n+1,T=n+2;
	long long ss=0,sss=0,sss2=0;
	rep(i,1,m){
		long long u,v,w1,w2,w;
		cin>>u>>v>>w1>>w2;
		a[i]={u,v,w1,w2};
		w=w2-w1;
		ss+=w1;
		put(u,v,w);
		put(v,u,0);
		d2[u]+=w1;
		d[v]+=w1;
	}
	t2=t;
	rep(i,1,n){
		nowww[i]=now[i];
	}
	rep(i,1,n){
		if(d[i]>d2[i]){
			sss+=d[i]-d2[i];
			put(S,i,d[i]-d2[i]);
			put(i,S,0);
		}
		else if(d[i]<d2[i]){
			sss2+=d2[i]-d[i];
			put(i,T,d2[i]-d[i]);
			put(T,i,0);
		}
	}
	if(sss!=sss2){
		cout<<"NO\n";
		return 0;
	}
	dinic();
	if(ans==sss){
		cout<<"YES\n";
		rep(i,1,m){
			cout<<a[i].w1+val[i*2+1]<<"\n";
		}
	}
	else cout<<"NO\n";
	return 0;
}

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e3+7,M=3e5+7;
long long n,m,S2,T2,d[N],d2[N],S,T,t=1,t2,p[M],now[N],son[M],val[M],noww[N],nowww[N],h[N],ans;
struct node{
	long long u,v,w1,w2;
};
node a[M];
void put(int a,int b,long long c){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
}
bool bfs(){
	rep(i,1,n+2){
		noww[i]=now[i];
		h[i]=0;
	}
	h[S]=1;
	queue<int> q;
	q.push(S);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]==0){
				h[y]=h[u]+1;
				q.push(y);
				if(y==T) return 1;
			}
		}
	}
	return 0;
}
long long dfs(int x,long long s){
	if(x==T) return s;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(val[i]&&h[y]==h[x]+1){
			long long ss=dfs(y,min(s,val[i]));
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18);
	}
}
int main(){
	cin>>n>>m>>S2>>T2;
	S=n+1,T=n+2;
	long long ss=0,sss=0,sss2=0;
	rep(i,1,m){
		long long u,v,w1,w2,w;
		cin>>u>>v>>w1>>w2;
		a[i]={u,v,w1,w2};
		w=w2-w1;
		ss+=w1;
		put(u,v,w);
		put(v,u,0);
		d2[u]+=w1;
		d[v]+=w1;
	}
	t2=t;
	rep(i,1,n+2){
		nowww[i]=now[i];
	}
	put(T2,S2,1e18);
	put(S2,T2,0);
	rep(i,1,n){
		if(d[i]>d2[i]){
			sss+=d[i]-d2[i];
			put(S,i,d[i]-d2[i]);
			put(i,S,0);
		}
		else if(d[i]<d2[i]){
			sss2+=d2[i]-d[i];
			put(i,T,d2[i]-d[i]);
			put(T,i,0);
		}
	}
	if(sss!=sss2){
		cout<<"please go home to sleep\n";
		return 0;
	}
	dinic();
	if(ans!=sss){
		cout<<"please go home to sleep\n";
		return 0;
	}
	ans=val[t2+2];
	t=t2;
	rep(i,1,n+2){
		now[i]=nowww[i];
	}
	S=S2,T=T2;
	dinic();
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=5e5+7,M=5e5+7;
long long n,m,S2,T2,d[N],d2[N],S,T,t=1,t2,p[M],now[N],son[M],val[M],noww[N],nowww[N],h[N],ans;
struct node{
	long long u,v,w1,w2;
};
node a[M];
void put(int a,int b,long long c){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
}
bool bfs(){
	rep(i,1,n+2){
		noww[i]=now[i];
		h[i]=0;
	}
	h[S]=1;
	queue<int> q;
	q.push(S);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]==0){
				h[y]=h[u]+1;
				q.push(y);
				if(y==T) return 1;
			}
		}
	}
	return 0;
}
long long dfs(int x,long long s){
	if(x==T) return s;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(val[i]&&h[y]==h[x]+1){
			long long ss=dfs(y,min(s,val[i]));
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18);
	}
}
int main(){
	cin>>n>>m>>S2>>T2;
	S=n+1,T=n+2;
	long long sss=0,sss2=0;
	rep(i,1,m){
		long long u,v,w1,w2,w;
		cin>>u>>v>>w1>>w2;
		a[i]={u,v,w1,w2};
		w=w2-w1;
		put(u,v,w);
		put(v,u,0);
		d2[u]+=w1;
		d[v]+=w1;
	}
	t2=t;
	rep(i,1,n+2){
		nowww[i]=now[i];
	}
	put(T2,S2,1e18);
	put(S2,T2,0);
	rep(i,1,n){
		if(d[i]>d2[i]){
			sss+=d[i]-d2[i];
			put(S,i,d[i]-d2[i]);
			put(i,S,0);
		}
		else if(d[i]<d2[i]){
			sss2+=d2[i]-d[i];
			put(i,T,d2[i]-d[i]);
			put(T,i,0);
		}
	}
	if(sss!=sss2){
		cout<<"please go home to sleep\n";
		return 0;
	}
	dinic();
	if(ans!=sss){
		cout<<"please go home to sleep\n";
		return 0;
	}
	long long ss=val[t2+2];
	t=t2;
	rep(i,1,n+2){
		now[i]=nowww[i];
	}
	S=T2,T=S2;
	ans=0;
	dinic();
	cout<<ss-ans;
	return 0;
}

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e3+7,M=3e5+7,INF=1e18;
long long n,m,b[N],S2,T2,d[N],d2[N],S,T,t=1,vis[N],p[M],now[N],son[M],val[M],coss[M],noww[N],h[N],ans,ans2;
struct node{
	long long u,v,w1,w2,c;
};
node a[M];
void put(int a,int b,long long c,long long d){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
	coss[t]=d;
}
bool bfs(){
	rep(i,1,n+3){
		noww[i]=now[i];
		vis[i]=0;
		h[i]=1e18;
	}
	h[S]=0;
	queue<int> q;
	q.push(S);
	bool flag=0;
	while(q.size()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		if(u==T) flag=1;
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]>h[u]+coss[i]){
				h[y]=h[u]+coss[i];
				if(vis[y]==0){
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
	return flag;
}
long long dfs(int x,long long s,long long &sss){
	if(x==T) return s;
	vis[x]=1;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(vis[y]==0&&val[i]&&h[y]==h[x]+coss[i]){
			long long ss=dfs(y,min(s,val[i]),sss);
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			sss+=coss[i]*ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	vis[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18,ans2);
	}
}
int main(){
	cin>>n;
	S2=1,T2=n+1;
	S=n+2,T=n+3;
	long long ss=0,sss=0,sss2=0;
	rep(i,1,n){
		cin>>b[i];
		rep(j,1,b[i]){
			long long y,z;
			cin>>y>>z;
			a[++ss]={i,y,1,INF,z};
		}
		a[++ss]={i,T2,0,INF,0};
	}
	rep(i,1,ss){
		long long u=a[i].u,v=a[i].v,w1=a[i].w1,w2=a[i].w2,c=a[i].c,w;
		w=w2-w1;
		put(u,v,w,c);
		put(v,u,0,-c);
		ans2+=c*w1;
		d2[u]+=w1;
		d[v]+=w1;
	}
	put(T2,S2,1e18,0);
	put(S2,T2,0,0);
	rep(i,1,n+1){
		if(d[i]>d2[i]){
			sss+=d[i]-d2[i];
			put(S,i,d[i]-d2[i],0);
			put(i,S,0,0);
		}
		else if(d[i]<d2[i]){
			sss2+=d2[i]-d[i];
			put(i,T,d2[i]-d[i],0);
			put(T,i,0,0);
		}
	}
	dinic();
	cout<<ans2<<"\n";
	return 0;
}

最大流(dinic)

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e3+7,M=2e4+7;
long long n,m,S,T,t=1,p[M],now[M],son[M],val[N],noww[M],h[N],ans;
void put(int a,int b,long long c){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
}
bool bfs(){
	rep(i,1,n){
		noww[i]=now[i];
		h[i]=0;
	}
	h[S]=1;
	queue<int> q;
	q.push(S);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]==0){
				h[y]=h[u]+1;
				q.push(y);
				if(y==T) return 1;
			}
		}
	}
	return 0;
}
long long dfs(int x,long long s){
	if(x==T) return s;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(val[i]&&h[y]==h[x]+1){
			long long ss=dfs(y,min(s,val[i]));
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18);
	}
}
int main(){
	cin>>m>>n;
	S=1,T=n;
	rep(i,1,m){
		long long u,v,w;
		cin>>u>>v>>w;
		put(u,v,w);
		put(v,u,0);
	}
	dinic();
	cout<<ans<<"\n";
	return 0;
}

费用流（最小费用最大流）

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=5e3+7,M=1e5+7;
long long n,m,d,S,T,t=1,p[M],now[N],son[M],val[M],coss[M],noww[N],h[N],vis[N],ans,ans2;
void put(int a,int b,long long c,long long d){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
	coss[t]=d;
}
bool bfs(){
	rep(i,1,n){
		noww[i]=now[i];
		vis[i]=0;
		h[i]=1e18;
	}
	h[S]=0;
	queue<int> q;
	q.push(S);
	bool flag=0;
	while(q.size()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		if(u==T) flag=1;
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]>h[u]+coss[i]){
				h[y]=h[u]+coss[i];
				if(vis[y]==0){
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
	return flag;
}
long long dfs(int x,long long s,long long &sss){
	if(x==T) return s;
	vis[x]=1;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(vis[y]==0&&val[i]&&h[y]==h[x]+coss[i]){
			long long ss=dfs(y,min(s,val[i]),sss);
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			sss+=coss[i]*ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	vis[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18,ans2);
	}
}
int main(){
	cin>>n>>m>>S>>T;
	rep(i,1,m){
		long long u,v,w,cw;
		cin>>u>>v>>w>>cw;
		put(u,v,w,cw);
		put(v,u,0,-cw);
	}
	dinic();
	cout<<ans<<" "<<ans2<<"\n";
	return 0;
}

  void mul(long long *a,int b){
	long long s=0;
	rep(i,1,a[0]){
		a[i]=a[i]*b+s;
		s=a[i]/B;
		a[i]%=B;
	}
	while(s) a[++a[0]]=s,s/=B;
}

void div(long long *a,int b){
	long long s=0;
	for(int i=a[0];i>=1;i--){
		long long aa=a[i];
		a[i]=(s+a[i])/b;
		s=(s+aa)%b*B;
	}
	while(a[0]!=1&&a[a[0]]==0) a[0]--;
}

void sub(long long *a,long long *b){
	long long s=0;
	rep(i,1,a[0]){
		a[i]-=s;
		if(a[i]<b[i]){
			s=1;
			a[i]+=B;
		}
		else{
			s=0;
		}
		a[i]-=b[i];
	}
	while(a[0]!=1&&a[a[0]]==0) a[0]--;
}

void add(long long *a,long long *b){
	long long s=0;
	rep(i,1,max(a[0],b[0])){
		a[i]=a[i]+b[i]+s;
		s=a[i]/B;
		a[i]%=B;
	}
	while(s) a[++a[0]]=s,s/=B;
}

判断素数

bool sushu(long long x){
	if(x<=1) return 0;
	long long t=sqrt(x);
	rep(i,2,t){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}

快速幂

long long qupow(long long a,long long b,long long p){
	long long s=1;
	a%=p;
	while(b){
		if(b%2==1) s=(a*s)%p;
		a*=a;
		b>>=1;
		a%=p;
	}
	return s;
}

欧拉筛

void ola(int nn){
	rep(i,2,nn){
		if(v[i]==0) ans[++s]=i;
		for(int j=1;j<=s&&ans[j]*i<=nn;++j){
			v[ans[j]*i]=1;
			if(i%ans[j]==0) break;
		}
	}
}

欧拉扩展

long long bds(long long a,long long b,long long c,long long &xx,long long &yy){
	if(b==0){
		xx=c/a;
		yy=0;
		return a;
	}
	long long nx,ny;
	long long f=bds(b,a%b,c,nx,ny);
	xx=ny;
	yy=nx-a/b*ny;
	return f;
}
void mod_t(long long a,long long b,long long n){
	long long d,x,y;
	d=bds(a,n,b,x,y);
	if(b%d){
		cout<<-1;
		return;
	}
	long long t=n/d;
	if(t<0) t=-t;
	x=(x%t+t)%t;
	cout<<x;
	// rep(i,1,d){
	// 	cout<<x+(i-1)*b/d<<"\n";
	// }
}

扩展BSGS魔法对数（第一类高次同余方程）

long long exBSGS(long long a,long long b,long long n){
	a%=n;
	b%=n;
	if(b==1||n==1) return 0;
	if(a==b) return 1;
	map<int,pair<long long,long long> > q;
	long long f=n,nn=n;
	rep(i,1,s){
		if(nn%ans[i]==0){
			f=f/ans[i]*(ans[i]-1);
			while(nn%ans[i]==0) nn/=ans[i];
		}
	}
	if(nn!=1){
		f=f/nn*(nn-1);
	}
	long long t=sqrt(2*f),anss=-1;
	if(t*t!=2*f) t++;
	rep(i,0,t){
		if(qupow(a,i,n)==b) return i;
	}
	if(b==0){
		return -1;
	}
	rep(i,1,t){
		long long pp=qupow(a,t*i,n);
		if(q.count(pp)==0) q[pp].first=t*i;
		else if(q[pp].second==0) q[pp].second=t*i;
	}
	rep(i,0,t){
		long long pp=b*qupow(a,i,n)%n;
		if(q.count(pp)){
			if(q[pp].first&&qupow(a,q[pp].first-i,n)%n==b){
				if(anss==-1) anss=q[pp].first-i;
				else anss=min(anss,q[pp].first-i);
			}
			if(q[pp].second!=0&&qupow(a,q[pp].second-i,n)%n==b){
				if(anss==-1) anss=q[pp].second-i;
				else anss=min(anss,q[pp].second-i);
			}
		}
	}
	return anss;
}

原根

long long Oroot(long long n){
	s=0;
	long long tt=sqrt(n-1),nn=n-1;
	rep(i,2,tt){
		if(nn%i==0){
			ans[++s]=i;
			while(nn%i==0) nn/=i;
		}
	}
	if(nn!=1){
		ans[++s]=nn;
	}
	rep(a,1,n){
		bool flag=1;
		rep(j,1,s){
			if(qupow(a,(n-1)/ans[j],n)==1){
				flag=0;
				break;
			}
		}
		if(flag) return a;
	}
	return -1;
}

魔法开根（第二类高次同余方程）

long long mod_sq(long long k,long long b,long long n){
  if(b==0) return 0;
	long long O=Oroot(n);
	long long m=exBSGS(O,b,n);
	long long y=mod_t(k,m,n-1);
	if(y==-1){
		return -1;
	}
	return qupow(O,y,n);
}

矩阵运算

struct mat{
	vector<vector<long long> > s;
	long long n,m;
	mat(long long x,long long y){
		n=x;
		m=y;
		s.resize(n+1);
		fill(s.begin(),s.end(),vector<long long>(m+1,0) );
	}
	friend mat operator+(const mat &a,const mat &b){
		mat sss={a.n,a.m};
		rep(i,0,a.n){
			rep(j,0,a.m){
				sss.s[i][j]=(a.s[i][j]+b.s[i][j])%M;
			}
		}
		return sss;
	}
	friend mat operator-(const mat &a,const mat &b){
		mat sss={a.n,a.m};
		rep(i,0,a.n){
			rep(j,0,a.m){
				sss.s[i][j]=(a.s[i][j]-b.s[i][j]+M)%M;
			}
		}
		return sss;
	}
	friend mat operator*(const mat &a,const mat &b){
		mat sss={a.n,b.m};
		rep(i,0,a.n){
			rep(j,0,a.m){
				rep(k,0,b.m){
					sss.s[i][k]=(sss.s[i][k]+a.s[i][j]*b.s[j][k]%M)%M;
				}
			}
		}
		return sss;
	}
	friend mat operator^(const mat &a,const long long &b){
		mat sss={a.n,a.m},aa=a;
		rep(i,0,a.n) sss.s[i][i]=1;
		long long bb=b;
		while(bb){
			if(bb%2==1) sss=(sss*aa);
			aa=aa*aa;
			bb>>=1;
		}
		return sss;
	}
};

高斯消元

bool eli(vector<vector<double> > &a,int n){
	bool f=1;
	int iii=1;
	rep(i,1,n){
		int id=iii;
		rep(j,iii+1,n){
			if(fabs(a[id][i])<fabs(a[j][i])){
				id=j;
			}
		}
		if(fabs(a[id][i])<M){
			f=0;
			continue;
		}
		if(id!=iii) swap(a[id],a[iii]);
		double s=a[iii][i];
		rep(j,1,n){
			if(j==iii) continue;
			s=a[j][i]/a[iii][i];
			rep(k,i,n+1){
				a[j][k]-=a[iii][k]*s;
			}
		}
		iii++;
	}
	return f;
}

高斯消元（异或）

bool eli(vector<vector<int> > &a,int n){
	bool f=1;
	int iii=1;
	rep(i,1,n){
		int id=iii;
		rep(j,iii+1,n){
			if(abs(a[j][i])==1){
				id=j;
			}
		}
		if(abs(a[id][i])==0){
			continue;
		}
		if(id!=iii) swap(a[id],a[iii]);
		rep(j,1,n){
			if(j==iii) continue;
			if(a[j][i]==0) continue;
			rep(k,i,n+1){
				a[j][k]^=a[iii][k];
			}
		}
		iii++;
	}
	rep(i,1,n){
		bool ff=1;
		rep(j,1,n){
			if(a[i][j]){
				ff=0;
				break;
			}
		}
		if(ff&&a[i][n+1]){
			f=0;
			break;
		}
	}
	iii--;
	ans=qupow(2,n-iii,M);
	return f;
}

链式前向星

void put(int a,int b){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
}

拓扑排序

void tp(){
	long long ans=0,s=0;
	queue<int> q;
	rep(i,1,n){
		if(t[i]==0){
			d[i]=100;
			q.push(i);
			s++;
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<g[x].size();++i){
			int j=g[x][i];
			if(t[j]){
				t[j]--;
				d[j]=max(d[j],d[x]+1);
				if(t[j]==0){
					q.push(j);
					s++;
				}
			}
		}
	}
	if(s!=n){
		cout<<"Poor Xed";
	}
	else{
		rep(i,1,n){
			ans+=d[i];
		}
		cout<<ans;
	}
}

树状数组

class fenwicktree{
	private:
		vector<long long> c;
		long long n;
		int lowbit(int x){
			return (x&-x);
		}
	public:
		fenwicktree(int x){
			n=x;
			c.resize(n+1);
			fill(c.begin(),c.end(),0);
		}
		void put(long long x,long long num){
			while(x<=n){
				c[x]+=num;
				x+=lowbit(x);
			}
		}
		long long sum(long long x){
			long long ans=0;
			while(x){
				ans+=c[x];
				x-=lowbit(x);
			}
			return ans;
		}
};

二分图判断（dfs染色）

bool coldfs(int x,int col){
	color[x]=col;
	for(int i=0;i<g[x].size();i++){
		int j=g[x][i];
		if(color[j]==col) return 0;
		if(color[j]==0){
			if(coldfs(j,col%2+1)==0) return 0;
		}
	}
	return 1;
}

lca

int lca(int x,int y){
	if(h[x]<h[y]){
		swap(x,y);
	}
	for(int i=19;i>=0;i--){
		if(h[f[x][i]]>=h[y]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

kmp

int n,m,nx[N],s[N];
char a[N],b[N];
void nxt(){
	nx[1]=0;
	int j=0;
	rep(i,2,m){
		while(j&&b[j+1]!=b[i]) j=nx[j];
		if(b[j+1]==b[i]) j++;
		nx[i]=j;
	}
}
void kmp(){
	nxt();
	int j=0;
	rep(i,1,n){
		while(j&&b[j+1]!=a[i]) j=nx[j];
		if(b[j+1]==a[i]) j++;
		s[i]=j;
	}
}

扩展kmp（z函数）

int n,m,p[N],s[N],ans;
char a[N],b[N];
void nxt(){
	int mid=0,r=0;
	p[1]=m;
	rep(i,2,m){
		if(i>r) p[i]=0;
		else p[i]=min(r-i+1,p[i-mid+1]);
		while(i+p[i]<=m&&b[i+p[i]]==b[p[i]+1]) p[i]++;
		if(i+p[i]-1>r){
			r=i+p[i]-1;
			mid=i;
		}
	}
}
void kkp(){
	nxt();
	int mid=0,r=0;
	rep(i,1,n){
		if(i>r) s[i]=0;
		else s[i]=min(r-i+1,p[i-mid+1]);
		while(i+s[i]<=n&&a[i+s[i]]==b[s[i]+1]) s[i]++;
		if(i+s[i]-1>r){
			r=i+s[i]-1;
			mid=i;
		}
	}
}

分块

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=1e6+7;
long long n,m,a[N],b[N],ans;
struct node{
	long long s,l,r;
};
node c[N];
int main(){
	cin>>n;
	int t=sqrt(n);
	rep(i,1,n){
		cin>>a[i];
		b[i]=(i-1)/t+1;
		c[b[i]].s=0;
		if(c[b[i]].l==0) c[b[i]].l=i;
		c[b[i]].r=i;
	}
	rep(i,1,n){
		long long id,u,v,x;
		cin>>id>>u>>v>>x;
		if(id==0){
			rep(j,1,b[n]){
				if(c[j].l>=u&&c[j].r<=v){
					c[j].s+=x;
				}
				else if(c[j].l<u&&c[j].r>v){
					rep(k,u,v){
						a[k]+=x;
					}
					break;
				}
				else if(c[j].l<u&&c[j].r>=u){
					rep(k,u,c[j].r){
						a[k]+=x;
					}
				}
				else if(c[j].l<=v&&c[j].r>v){
					rep(k,c[j].l,v){
						a[k]+=x;
					}
				}
			}
		}
		else{
			cout<<a[v]+c[b[v]].s<<"\n";
		}
	}
	return 0;
}

线性基

class linear_basis{
	private:
		bool flag;
		long long n;
		vector<long long> bas;
	public:
		linear_basis(long long siz){
			flag=0;
			n=siz;
			bas.resize(siz+1);
			fill(bas.begin(),bas.end(),0);
		}
		void adg1(long long x){
			for(int i=n;i>=0;i--){
				if(x&(1ll<<i)){
					if(bas[i]==0){
						bas[i]=x;
						return;
					}
					else x^=bas[i];
				}
			}
			flag=1;
		}
		bool check(long long x){
			for(int i=n;i>=0;i--){
				if(x&(1ll<<i)){
					if(bas[i]==0){
						return 0;
					}
					else x^=bas[i];
				}
			}
			return 1;
		}
		long long Max(){
			long long ans=0;
			for(int i=n;i>=0;i--){
				ans=max(ans,ans^bas[i]);
			}
			return ans;
		}
		long long Min(){
			if(flag) return 0;
			rep(i,0,n){
				if(bas[i]!=0) return bas[i];
			}
		}
		long long finds(long long x){
			if(flag){
				if(x==1) return 0;
				x--;
			}
			vector<long long> ans;
			rep(i,0,n){
				for(long j=i-1;j>=0;j--){
					if(bas[i]&(1ll<<j)) bas[i]^=bas[j];
				}
				if(bas[i]) ans.push_back(bas[i]);
			}
			if(x>=(1ll<<(ans.size()))) return -1;
			long long s=0;
			for(int i=0;i<ans.size();i++){
				if(x&(1ll<<i)) s^=ans[i];
			}
			return s;
		}
		friend linear_basis operator+(const linear_basis &a,const linear_basis &b){
			linear_basis s=a;
			rep(i,0,b.n){
				if(b.bas[i]){
					s.adg1(b.bas[i]);
				}
			}
			return s;
		}
};