zzx2024

UID: 46086, 注册于 2024-2-20 17:12:05, 最后登录于 2025-9-11 20:47:24, 最后活动于 2025-9-11 20:47:24.

解决了 102 道题目，RP: 246.38 (No. 9)

♂

个人简介

AT and Code

代码模板

单/双/异或/后缀数组 hash

单hash:

#include<bits/stdc++.h>
#define lson k<<1
#define rson k<<1|1
#define int long long
using namespace std;
const int N=1e6+115;
string a,b;int ans=0;
unsigned long long aa[N],bb[N],g[N];
int na,nb;
int base=233331,mod=998244353;
unsigned long long calc(int x,int y)
{
	return (aa[y]-aa[x-1]*g[y-x+1]%mod+mod)%mod;
}
signed main()
{
	cin>>a>>b;
	na=a.size(),nb=b.size();
	a=' '+a;
	b=' '+b;
	g[0]=1;
	for(int i=1;i<=na;i++)
		aa[i]=(aa[i-1]*base+a[i])%mod,g[i]=(g[i-1]*base)%mod;
	for(int i=1;i<=nb;i++)
		bb[i]=(bb[i-1]*base+b[i])%mod;
	int sum=0;
	for(int i=1;i<=na-nb+1;i++)
	{
		if(calc(i,i+nb-1)==bb[nb])
		{
			sum++;
		}
	}
	cout<<sum<<endl;
	return 0;
}
/*
zyzyzyz
zyz

*/

双hash

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
gp_hash_table<unsigned long long,bool> mp;
const int N=1e7+1;
string a,b;int ans=0;
unsigned long long aa[N],bb[N],g[N],g2[N];
int na,nb,k;
int base=233331,mod=998244353,mod2=1e9+7,base2=137;
unsigned long long calc(int x,int y)
{
	return (aa[y]-aa[x-1]*g[y-x+1]%mod+mod)%mod;
}
unsigned long long calc2(int x,int y)
{
	return (bb[y]-bb[x-1]*g2[y-x+1]%mod2+mod2)%mod2;
}
signed main()
{
	cin>>na>>k;
	cin>>a;
	a=' '+a;
	g[0]=1;
	g2[0]=1;
	for(int i=1;i<=na;i++)
		aa[i]=(aa[i-1]*base+a[i])%mod,g[i]=(g[i-1]*base)%mod;
	for(int i=1;i<=na;i++)
		bb[i]=(bb[i-1]*base2+a[i])%mod2,g2[i]=(g2[i-1]*base2)%mod2;
	int sum=0;
	for(int i=1;i<=na-k+1;i++)
	{
		int k1=calc(i,i+k-1),k2=calc2(i,i+k-1);
		if(!mp[(k1<<30)+k2])sum++;
		mp[(k1<<30)+k2]=1;
	}
	cout<<sum<<endl;
	return 0;
}
/*
5 3
ababa
*/

后缀数组：（Hash+二分）

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+114;
int na;
unsigned long long ga[N],aa[N];
string a;
int base=137;
inline unsigned long long calc(int x,int y)
{
	return (aa[y]-aa[x-1]*ga[y-x+1]);
}
int sa[N];
bool cmp(int x,int y)
{
	int l=0,r=min(na-x,na-y);
	int ans=-1;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(calc(x,x+mid)==calc(y,y+mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	if(ans==min(na-x,na-y))return x>y;
	return a[x+ans+1]<a[y+ans+1];
}
int main()
{
	cin>>a;
	na=a.size();
	a=' '+a;
	ga[0]=1;
	for(int i=1;i<=na;i++)
		aa[i]=(aa[i-1]*base+a[i]),ga[i]=ga[i-1]*base,sa[i]=i;
	stable_sort(sa+1,sa+1+na,cmp);
	for(int i=1;i<=na;i++)printf("%d\n",sa[i]);
	return 0;
}
//注意卡常！！！！

异或hash：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+114;
int n,q;
mt19937 rd(time(0));
int a[N],b[N],suma[N],sumb[N];
map<int,int> c;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],c[a[i]]=rd();
	for(int j=1;j<=n;j++)cin>>b[j],c[b[j]]=rd();
	for(int i=1;i<=n;i++)a[i]=c[a[i]];
	for(int i=1;i<=n;i++)b[i]=c[b[i]];
	c.clear();
	for(int i=1;i<=n;i++)
	{
		if(!c[a[i]])suma[i]=suma[i-1]^a[i];
		else suma[i]=suma[i-1];
		c[a[i]]++;
	}
	c.clear();
	for(int i=1;i<=n;i++)
	{
		if(!c[b[i]])sumb[i]=sumb[i-1]^b[i];
		else sumb[i]=sumb[i-1];
		c[b[i]]++;
	}
	cin>>q;
	while(q--)
	{
		int x,y;cin>>x>>y;
		if(suma[x]==sumb[y])cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

可持久化线段树（主席树）

#include<bits/stdc++.h>
#define int long long
#define debug(a) cout<<#a<<':'<<a<<endl;
using namespace std;
const int N=100114,M=32;
int n,m,a[N],sum[N*M],lc[N*M],rc[N*M],cnt,b[N],rt[N],p;
void build(int &k,int l,int r)
{
	k=++cnt;
	sum[k]=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(lc[k],l,mid);
	build(rc[k],mid+1,r);
}
int jia(int k,int l,int r)
{
	int xin=++cnt;
	lc[xin]=lc[k],rc[xin]=rc[k],sum[xin]=sum[k]+1;
	if(l==r)return xin;
	int mid=l+r>>1;
	if(p<=mid)lc[xin]=jia(lc[k],l,mid);
	else rc[xin]=jia(rc[k],mid+1,r);
	return xin;
}
int xunwen(int u,int v,int l,int r,int k)
{
	int x=sum[lc[v]]-sum[lc[u]];
	if(l==r)return l;
	int mid=l+r>>1;
	if(k<=x)return xunwen(lc[u],lc[v],l,mid,k);
	else return xunwen(rc[u],rc[v],mid+1,r,k-x);
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	int q=unique(b+1,b+1+n)-b-1;
	build(rt[0],1,q);
	for(int i=1;i<=n;i++)
	{
		p=lower_bound(b+1,b+1+q,a[i])-b;
		rt[i]=jia(rt[i-1],1,q);
	}
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		cout<<b[xunwen(rt[x-1],rt[y],1,q,z)]<<endl;
	}
	return 0;
}

C(n,m)的求法

暴力

int C(int n,int m)
{
	int ans=1;
	for(int i=n-m+1;i<=n;i++)ans*=i;
	int sum=1;
	for(int i=m;i>=1;i--)sum*=i;
	ans/=sum;
	return ans;
}

预处理

d[1][1]=1;
rep(i,2,n+1)rep(j,1,i)
{
	if(j==1 || j==i)d[i][j]=1;
	else
	{
		d[i][j]=d[i-1][j]+d[i-1][j-1];
		d[i][j]%=mod;
	}
}
e[1][1]=1;
rep(i,2,n+1)rep(j,1,i)
{
	e[i][j]=d[i+1][j+1];
	e[i][j]%=mod;
}

优化

int C(int n,int m)
{
	int ans=1;
	int t=n;
	int b=1;
	for(int i=1;i<=m;i++)
	{
		ans=ans*t/b;
		t--;b++;
	}
	return ans;
}

超快速

int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=(a*res)%p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return res;
}
void ff()
{
	fac[0]=1;
	for(int i=1;i<=100000;i++)fac[i]=fac[i-1]*i%mod;
}
int C(int n,int m)
{
	return (fac[n]*qpow(fac[n-m],mod-2,mod)%mod*qpow(fac[m],mod-2,mod)%mod)%mod;
}

快速幂

int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=(a*res)%p;
		a*=a;
		a%=p;
		b>>=1;
	}
	return res;
}

((qpow(m,n+1,mod)-1+mod)%mod*qpow(m-1,mod-2,mod)%mod-1+mod)%mod//等比数列求和公式

扩欧

扩欧
void ojld(int a,int b)
{
	if(b==0)
	{
		jx=1,jy=0;
		return;
	}
	ojld(b,a%b);
	int tx=jx;
	jx=jy;
	jy=tx-a/b*jy;
}

鼠据生成：

#include<bits/stdc++.h>
using namespace std;
char a[10];
int top;
void ddd(int x)
{
	top=0;
	a[top]='c';
	a[++top]='c';
	string s="";
	while(x)
	{
		s+=(x%10)+'0';
		x/=10;
	}
	reverse(s.begin(),s.end());
	for(int i=0;i<s.size();i++)
	{
		a[++top]=s[i];
	}
	a[++top]='.';
	a[++top]='o';
	a[++top]='u';
	a[++top]='t';
}
int main()
{
	for(int i=1;i<=800;i++)
	{
		freopen("c1.out","r",stdin);
		ddd(i);
		freopen(a,"w",stdout);
		for(int j=1;j<=800;j++)
		{
			int x;
			cin>>x;
			if(i==j)
			{
				cout<<x<<endl;
				break;
			}
		}
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}

tarjan

//tarjan
#include<bits/stdc++.h>
typedef long long ll;
//#define int long long
using namespace std;
const int N=1e5+114;
int n,m,dfn[N],low[N],tot,ans;
vector<int> adj[N],what[N];
stack<int> st;
int flag[N];
void tarjan(int u)
{
	dfn[u]=low[u]=++tot;
	st.push(u);
	for(auto it : adj[u])
	{
		if(!dfn[it])
		{
			tarjan(it);
			low[u]=min(low[u],low[it]);
		}
		else if(!flag[it])
		{
			low[u]=min(low[u],dfn[it]);
		}
	}
	if(dfn[u]==low[u])
	{
		ans++;
		flag[u]=ans;
		what[ans].push_back(u);
		while(st.top()!=u)
		{
			flag[st.top()]=ans;
			what[ans].push_back(st.top());
			st.pop();
		}
		st.pop();
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjan(i);
		}
	}
	int ab=0;
	for(int i=1;i<=ans;i++)
	{
		if(what[i].size()>1)ab++;
	}
    cout<<ab;
	return 0;
}


//求割点
//tarjan
#include<bits/stdc++.h>
typedef long long ll;
#define int long long
using namespace std; //A
const int N=1e5+114;
int n,m,dfn[N],low[N],tot,ans,sbsb,hi;
vector<int> adj[N],what[N];
set<int> anss;
stack<int> st;
int flag[N];
void tarjan(int u,int fa)
{
	dfn[u]=low[u]=++tot;
	st.push(u);int son=0;
	for(auto it : adj[u])
	{
		if(!dfn[it])
		{
			son++;
			tarjan(it,u);
			low[u]=min(low[u],low[it]);
			if(low[it]>=dfn[u] && it!=fa && hi!=u && !(anss.count(u)))
			{
				sbsb++;
				anss.insert(u);
			}
		}
		else
		{
			low[u]=min(low[u],dfn[it]);
		}
	}
	if(hi==u && son>=2)
	{
		sbsb++;
		anss.insert(u);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			hi=i;
			tarjan(i,0);
		}
	}
	cout<<sbsb<<endl;
	for(auto it: anss)
	{
		cout<<it<<' ';
	}
	return 0;
}
//求割边（有重边时）
#include<bits/stdc++.h>
using namespace std;
const int N=30114;
int n,m;
vector<int> adj[N];
int low[N],dfn[N],flag[N],tot,idx;
void tarjan(int u,int fa)
{
	bool sb=0;
	low[u]=dfn[u]=++idx;
	for(auto it:adj[u])
	{
		if(!dfn[it])
		{
			tarjan(it,u);
			low[u]=min(low[u],low[it]);
			if(low[it]>dfn[u])
			{
				tot++;
				flag[it]=1;
			}
		}
		else
		{
			if(it!=fa || sb)
			{
				low[u]=min(low[u],dfn[it]);
			}
			else sb=1;
		}
	}
}
int main()
{
	while(cin>>n>>m && !(n==0 && m==0))
	{
		for(int i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		tarjan(1,-1);
		cout<<tot<<endl;
		for(int i=1;i<=n;i++)adj[i].clear();
		memset(low,0,sizeof low);
		memset(dfn,0,sizeof dfn);
		tot=0;
	}
	return 0;
}

//边双连通分量（可以用上面的代码改一下）
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,dfn[2000010],low[2000010],bel[2000010],ecc;
int shijian;
stack<int> st;
vector<int> adj[4000001];
int head[2000001],ans=1;
struct node
{
	int nxt,v;
}e[4000001];
bool flag[4000001];
int jj;
void add(int x,int y)
{
	e[++ans].v=y;
	e[ans].nxt=head[x];
	head[x]=ans;
}
void tarjan(int u,int edg)
{
	st.push(u);
	dfn[u]=low[u]=++shijian;
	for(int i=head[u];i!=-1;i=e[i].nxt)
	{
		int t=e[i].v;
		if(!dfn[t])
		{
			tarjan(t,i);
			low[u]=min(low[u],low[t]);
			if(low[t]>dfn[u])
			{
				flag[i]=flag[i^1]=1;
			}
		}
		else if(i!=(edg^1))//所以不要走到他的父亲节点去了，解释在下面
		{
			low[u]=min(low[u],dfn[t]);
		}
	}
}
void dfs(int u)
{
	bel[u]=ecc;
	adj[ecc].push_back(u);
	for(int i=head[u];i!=-1;i=e[i].nxt)
	{
		int t=e[i].v;
		if(bel[t] || flag[i])continue;
		dfs(t);
	}
}
int main()
{
	//freopen("name.in","r",stdin);
	//freopen("name.out","w",stdout);
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		//✔✘▓※
		int x,y;
		cin>>x>>y;//解释
		add(x,y);//如果ans=3
		add(y,x);//那么这一行执行完后ans=4
		//他们是相对的
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])tarjan(i,0);
	}
	for(int i=1;i<=n;i++)
	{
		if(!bel[i])
		{
			ecc++;
			dfs(i);
		}
	}
	cout<<ecc<<endl;
	for(int i=1;i<=ecc;i++)
	{
		cout<<adj[i].size();
		for(int j=0;j<adj[i].size();j++)cout<<" "<<adj[i][j];
		cout<<endl;
	}
	return 0;
}

//点双连通分量
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,dfn[500010],low[500010],bel[500010],abab;
int shijian;
stack<int> st;
vector<int> ans[1000001];
vector<int> adj[500010];
bool flag[1000001],vis[1000001];
int jj;
void tarjan(int u,int fa)
{
    st.push(u);
    dfn[u]=low[u]=++shijian;
    if(fa==0 && adj[u].size()==0)
    {
        ans[++abab].push_back(u);
        return;
    }
    for(int i=0;i<adj[u].size();i++)
    {
        int t=adj[u][i];
        if(!dfn[t])
        {
            tarjan(t,u);
            low[u]=min(low[u],low[t]);
            if(low[t]>=dfn[u])
            {
                abab++;
                while(st.top()!=t)
                {
                    ans[abab].push_back(st.top());
                    st.pop();
                }
                ans[abab].push_back(t);
                st.pop();
                ans[abab].push_back(u);
            }
        }
        else if(t!=fa)
        {
            low[u]=min(low[u],dfn[t]);
        }
    }
}
int main()
{
    //freopen("name.in","r",stdin);
    //freopen("name.out","w",stdout);
    cin>>n>>m;//K
    for(int i=1;i<=m;i++)
    {
        //✔✘▓※
        int x,y;
        cin>>x>>y;
        if(x == y) continue;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i,0);
        while(!st.empty())st.pop();
    }
    cout<<abab<<endl;
    for(int i=1;i<=abab;i++)
    {
        cout<<ans[i].size();
        for(int j=0;j<ans[i].size();j++)cout<<" "<<ans[i][j];
        cout<<endl;
    }
    return 0;
}

树的重心

//树的重心
#include<bits/stdc++.h>
using namespace std;
const int N=20114;
int n;
vector<int> adj[N];
int siz[N],msz[N];
void dfs(int u,int fa)
{
    siz[u]=1;
    for(auto it : adj[u])
    {
        if(it==fa)continue;
        dfs(it,u);
        siz[u]+=siz[it];
        msz[u]=max(msz[u],siz[it]);
    }
    msz[u]=max(msz[u],n-siz[u]);
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1,0);
    bool flag=0;
    for(int i=1;i<=n;i++)
    {
        if(msz[i]<=n/2)
        {
            flag=1;
            cout<<i<<endl;
        }
    }
    if(!flag)cout<<"NONE";
    return 0;
}

树状数组

struct Tree_Array
{
	int tree[N]={0};
	int lowbit(int x){return (x&-x);}
	void add(int u,int k){for(;u<=n+Q;u+=lowbit(u))tree[u]+=k;}
	int ask(int x){int sum=0;for(;x;x-=lowbit(x))sum+=tree[x];return sum;}
}tr;

离散化

#include<bits/stdc++.h>//I
#define inf 0x3f3f3f3f
using namespace std;
int n,b[100001],maxn;
int l[100001],r[100001],g[300001],cnt;
int main()
{
    cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];g[++cnt]=l[i],g[++cnt]=r[i];
	}
	sort(g+1,g+1+cnt);
	for(int i=1;i<=n;i++)
	{
		int lll=lower_bound(g+1,g+1+cnt,l[i])-g;
		int rrr=lower_bound(g+1,g+1+cnt,r[i])-g;
		b[lll]++;
		b[rrr+1]--;
	}
	int maxnn=0;
	for(int i=1;i<=cnt;i++)b[i]+=b[i-1],maxnn=max(maxnn,b[i]);
	cout<<maxnn<<endl;
    return 0;
}

二维差分

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,k,b[3001][3001],a[3001][3001];
int main()
{
    cin>>n;
	while(n--)
	{
		int l,r,ll,rr;
		cin>>l>>ll>>r>>rr;
		if(ll<l)swap(l,ll);
		if(rr<r)swap(r,rr);
		l++,r++;
		b[l][r]++;
		b[l][rr+1]--;
		b[ll+1][r]--;
		b[ll+1][rr+1]++;
	}
	int c=0;
	for(int i=1;i<=100;i++)
	{
		for(int j=1;j<=100;j++)
		{
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
			if(a[i][j]>=1)c++;
		}
	}
	cout<<c;
    return 0;
}

线段树

//线段树

//我现在的模板
#include<bits/stdc++.h>
#define int long long
#define debug(a) cout<<#a<<':'<<a<<endl;
using namespace std;
const int N=100005;
int n,k,a[N],maxn,minn;
struct
{
	int mx,mn;
}tr[N*4];
void build(int num,int l,int r)
{
	if(l==r)
	{
		tr[num]={a[l],a[r]};
		return;
	}
	int mid=l+r>>1;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
	tr[num].mx=max(tr[num*2].mx,tr[num*2+1].mx);
	tr[num].mn=min(tr[num*2].mn,tr[num*2+1].mn);
}
void qunwen(int num,int l,int r,int x,int y)
{
	if(x<=l && r<=y)
	{
		maxn=max(maxn,tr[num].mx);
		minn=min(minn,tr[num].mn);
		return;
	}
	int mid=l+r>>1;
	if(mid>=x)qunwen(num*2,l,mid,x,y);
	if(mid<y)qunwen(num*2+1,mid+1,r,x,y);
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=k;i<=n;i++)
	{
		maxn=-1e9,minn=1e9;
		qunwen(1,1,n,i-k+1,i);
		cout<<maxn<<' '<<minn<<endl;
	}
	return 0;
}
//以前的模板
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;
const int maxn = 5e5 + 5;
int a[maxn], n, m;

struct node { // 线段树的结点
	int l,r;
	ll val;
} tree[maxn << 2];

void build(int k, int l, int r) { // 建树
	tree[k].l=l,tree[k].r=r;
	if(l==r)tree[k].val=a[l];
	else
	{
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		tree[k].val=tree[lson].val+tree[rson].val;
	}
}

void update(int k, int id, int val) { // a[id] += val
	if(tree[k].l==tree[k].r && tree[k].l==id)
	{
		tree[k].val=a[id]+val;
		a[id]+=val;
		return;
	}
	int mid=tree[k].l+tree[k].r>>1;
	if(id<=mid)update(lson,id,val);
	else update(rson,id,val);
	tree[k].val=tree[lson].val+tree[rson].val;
}

ll query(int k, int l, int r) { // 查询 a[l...r] 的区间和
	int tl=tree[k].l,tr=tree[k].r;
	if(tl>=l && tr<=r)return tree[k].val;
	int mid=tl+tr>>1;
	ll ans=0;
	if(mid>=l)ans=ans+query(lson,l,r);
	if(mid+1<=r)ans=ans+query(rson,l,r);
	return ans;
}

int main() {
	cin>>n>>m;
	for(int i = 1; i <= n; ++i) cin>>a[i];
	// 初始化建树
	build(1,1,n);
	while(m--) {
		int op, x, y;
		cin>>op>>x>>y;
		if(op == 1) {
			update(1, x, y);
		} else {
			cout<<query(1, x, y)<<'\n';
		}
	}
	return 0;
}
//加lazy
#include <bits/stdc++.h>
#define lson k << 1
#define rson k << 1 | 1
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
ll a[maxn], n, m;

struct node {//O
	int l, r;
	ll sum, lazy; // lazy 惰性标记
} tree[maxn << 2];

void build(int k, int l, int r) { // 建树
	tree[k].l=l,tree[k].r=r;
	tree[k].lazy=0;
	if(l==r)tree[k].sum=a[l];
	else
	{
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		tree[k].sum=tree[lson].sum+tree[rson].sum;
	}
}

void pushdown(int k) { // 将 k 的 lazy 标记下传
	if(tree[k].lazy)
	{
		tree[lson].sum+=tree[k].lazy*(tree[lson].r-tree[lson].l+1);
		tree[rson].sum+=tree[k].lazy*(tree[rson].r-tree[rson].l+1);
		tree[lson].lazy+=tree[k].lazy;
		tree[rson].lazy+=tree[k].lazy;
		tree[k].lazy=0;
	}
}

void update(int k, int l, int r, int val) { // a[l...r] += val
	int tl=tree[k].l,tr=tree[k].r;
	if(l<=tl && tr<=r)
	{
		tree[k].sum+=val*(tr-tl+1);   //他是一个区间啊
		tree[k].lazy+=val;
		return;
	}
	pushdown(k);
	int mid=tree[k].l+tree[k].r>>1;
	if(mid>=l)update(lson,l,r,val);
	if(mid+1<=r)update(rson,l,r,val);
	tree[k].sum=tree[lson].sum+tree[rson].sum;
} 
ll query(int k, int l, int r) { // 查询 a[l...r] 的和
	int tl=tree[k].l,tr=tree[k].r;
	if(tl>=l && tr<=r)return tree[k].sum;
	pushdown(k);
	int mid=tl+tr>>1;
	ll ans=0;
	if(mid>=l)ans=ans+query(lson,l,r);
	if(mid+1<=r)ans=ans+query(rson,l,r);
	return ans;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= n; ++i) cin>>a[i];
	build(1, 1, n);
	while(m--) {
		int op, x, y, val;
		cin>>op>>x>>y;
		if(op == 1) {
			cin>>val;
			update(1, x, y, val);
		} else {
			cout<<query(1, x, y)<<'\n';
		}
	}
	return 0;
}

严格次小生成树

//严格次小生成树
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
const int N=1e6+114,M=3e6+114;
int n,m,fa[N];
struct node
{
    int x,z;
};
vector<node> adj[N];
struct nod
{
    int x,y,z;
}edge[M];
bool cmp(nod x,nod y)
{
    return x.z<y.z;
}
int dep[N],tiao[N][51],fir[N][51],sec[N][51];
bool flag[N];
void dfs(int u,int fa,int de)
{
    dep[u]=de;
    for(auto it:adj[u])
    {
        if(it.x==fa)continue;
        tiao[it.x][0]=u;
        fir[it.x][0]=it.z;
        sec[it.x][0]=-inf;
        dfs(it.x,u,de+1);
    }
}
int lca(int xx,int yy)
{
	if(dep[xx]<dep[yy])swap(xx,yy);
	for(int i=50;i>=0;i--)
	{
		if(dep[tiao[xx][i]]>=dep[yy])
		{
			xx=tiao[xx][i];
		}
	}
	if(xx==yy)return xx;
	for(int i=50;i>=0;i--)
	{
		if(tiao[xx][i]!=tiao[yy][i])
		{
			xx=tiao[xx][i];
			yy=tiao[yy][i];
		}
	}
	return tiao[xx][0];
}
int find(int x)
{
    if(fa[x]==x)return fa[x];
    return fa[x]=find(fa[x]);
}
int qunwen(int x,int y,int cost)
{
    int ret=0;
    for(int i=50;i>=0;i--)
    {
        if(dep[tiao[x][i]]>=dep[y])
        {
            if(cost==fir[x][i])ret=max(ret,sec[x][i]);
            else ret=max(ret,fir[x][i]);
            x=tiao[x][i];
        }
    }
    return ret;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};
    }
    sort(edge+1,edge+1+m,cmp);
    int sum=0,ans=0;
    for(int i=1;i<=m;i++)
    {
        int x=edge[i].x,y=edge[i].y;
        int xx=find(x),yy=find(y);
        if(xx==yy)continue;
        adj[x].push_back({y,edge[i].z});
        adj[y].push_back({x,edge[i].z});
        ans++;
        sum+=edge[i].z;
        fa[xx]=yy;
        flag[i]=1;
        if(ans==n-1)break;
    }
    dfs(1,0,0);
	for(int j=1;j<=50;j++)
	{
		for(int i=1;i<=n;i++)
		{
			tiao[i][j]=tiao[tiao[i][j-1]][j-1];
			int temp[4]={fir[i][j-1],sec[i][j-1],fir[tiao[i][j-1]][j-1],sec[tiao[i][j-1]][j-1]};
			sort(temp,temp+4);
			fir[i][j]=temp[3];
			sec[i][j]=temp[2];
			if(fir[i][j]==sec[i][j])sec[i][j]=temp[1];
		}
	}
    ans=inf;
    for(int i=1;i<=m;i++)
    {
        if(!flag[i])
        {
            int x=edge[i].x;
            int y=edge[i].y;
            int lcaa=lca(x,y);
            int tttt=max(qunwen(x,lcaa,edge[i].z),qunwen(y,lcaa,edge[i].z));
            ans=min(ans,sum+edge[i].z-tttt);
        }
    }
    cout<<ans;
    return 0;
}

树链剖分

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,root;
const int N=500005;
vector<int> adj[N];
int dep[N],fa[N],son[N],top[N],siz[N];
void dfs1(int x)
{
	siz[x]=1;
	for(auto it:adj[x])
	{
		if(it==fa[x])continue;
		fa[it]=x;
		dep[it]=dep[x]+1;
		dfs1(it);
		if(siz[son[x]]<siz[it])son[x]=it;
		siz[x]+=siz[it];
	}
}
void dfs2(int x)
{
	if(!son[x])return;
	top[son[x]]=top[x];
	dfs2(son[x]);
	for(auto it:adj[x])
	{
		if(fa[x]==it || it==son[x])continue;
		top[it]=it;
		dfs2(it);
	}
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
signed main()
{
	cin>>n>>m>>root;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dep[root]=1;
	dfs1(root);
	top[root]=root;
	dfs2(root);
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		printf("%d\n",lca(x,y));
	}
	return 0;
}

同余最短路&&跳楼机

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+114;
int h,x,y,z,dis[N],s;
struct node
{
	int x,z;
};
struct nod
{
	int x,z;
};
vector<nod> adj[N];
bool operator <(node x,node y){return x.z>y.z;}
bool flag[N];
void dij()
{
	priority_queue<node> q;
	q.push({s,0});
	memset(flag,0,sizeof flag);
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	while(!q.empty())
	{
		node t=q.top();
		q.pop();
		if(flag[t.x])continue;
		flag[t.x]=1;
		for(auto it:adj[t.x])
		{
			if(dis[it.x]>dis[t.x]+it.z)
			{
				dis[it.x]=dis[t.x]+it.z;
				if(!flag[it.x])q.push({it.x,dis[it.x]});
			}
		}
	}
}
signed main()
{
	cin>>h>>x>>y>>z;
	if(x==1 || y==1 || z==1)
	{
		cout<<h<<endl;
		return 0;
	}
	h--;
	for(int i=0;i<x;i++)
	{
		adj[i].push_back({(i+y)%x,y});
		adj[i].push_back({(i+z)%x,z});
	}
	s=0;
	dij();
	int sum=0;
	for(int i=0;i<=x-1;i++)
		if(h>=dis[i])sum+=(h-dis[i])/x+1;
	cout<<sum<<endl;
	return 0;
}
//不开long long见祖宗

圆方树

#include<bits/stdc++.h>
using namespace std;
const int N=2000001,M=700001;
int n,m,dfn[M],low[M],abab;
int shijian;
stack<int> st;
vector<int> ans[N];
vector<int> adj[M];
int top[N],son[N],dep[N],siz[N],fa[N];
void add_ans(int u,int v)
{
	ans[u].push_back(v);
	ans[v].push_back(u);
}
void tarjan(int u)
{
	st.push(u);
	dfn[u]=low[u]=++shijian;
	for(int i=0;i<adj[u].size();i++)
	{
		int t=adj[u][i];
		if(!dfn[t])
		{
			tarjan(t);
			low[u]=min(low[u],low[t]);
			if(low[t]==dfn[u])
			{
				abab++;
				add_ans(u,abab);
				while(st.top()!=t)
				{
					add_ans(st.top(),abab);
					st.pop();
				}
				add_ans(t,abab);
				st.pop();
			}
		}
		else
			low[u]=min(low[u],dfn[t]);
	}
}
void dfs1(int u,int f)
{
	dep[u]=dep[f]+1;
	fa[u]=f;
	siz[u]=1;
	for(auto v:ans[u])
	{
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
 	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	if(!son[u])return;
	dfs2(son[u],tp);
	for(auto v:ans[u])
		if(v!=fa[u] && v!=son[u])
			dfs2(v,v);
}
int lca(int x,int y)
{
	while (top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y])return x;
	return y;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("P4320_2.in","r",stdin);
//	freopen("ssssssssssss.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	abab=n;
	tarjan(1);
	dfs1(1,0);
	dfs2(1,1);
	int q;
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<((dep[x]+dep[y]-dep[lca(x,y)]*2)>>1)+1<<endl;
	}
	return 0;
}
/*
5 5
1 2
1 3
1 4
3 4
4 5
1
4 3
*/

支配树

没环

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=65540;
int n,in[N],dep[N];//拓扑序
vector<int> adj[N],fan[N],shu[N];
int tiao[N][25],siz[N];
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[tiao[x][i]]>=dep[y])
		{
			x=tiao[x][i];
		}
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(tiao[x][i]!=tiao[y][i])
		{
			x=tiao[x][i];
			y=tiao[y][i];
		}
	}
	return tiao[x][0];
}
void topu112(int s)
{
	queue<int> q;
	q.push(s);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(auto it:adj[t])
		{
			if(fan[it].size()<2 && !tiao[it][0])
			{
				shu[t].push_back(it);
				tiao[it][0]=t;
				for(int i=1;i<=20;i++)
				{
					tiao[it][i]=tiao[tiao[it][i-1]][i-1];
				}
				dep[it]=dep[t]+1;
			}
			else if(!tiao[it][0])
			{
				int t=fan[it][0],tt=fan[it][1];
				int anss=lca(t,tt);
				for(int i=2;i<fan[it].size();i++)
				{
					anss=lca(anss,fan[it][i]);
				}
				shu[anss].push_back(it);
				tiao[it][0]=anss;
				for(int i=1;i<=20;i++)
				{
					tiao[it][i]=tiao[tiao[it][i-1]][i-1];
				}
				dep[it]=dep[anss]+1;
			}
			in[it]--;
			if(!in[it])q.push(it);
		}
	}
}
void dfs(int u)
{
	siz[u]=1;
	for(auto it:shu[u])
	{
		dfs(it);
		siz[u]+=siz[it];
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int ssss;
		cin>>ssss;
		while(ssss!=0)
		{
			adj[ssss].push_back(i);
			fan[i].push_back(ssss);
			in[i]++;
			cin>>ssss;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(!in[i])
		{
			adj[0].push_back(i);
			fan[i].push_back(0);
			in[i]++;
		}
	}
	topu112(0);
	dfs(0);
	for(int i=1;i<=n;i++)
	{
		cout<<siz[i]-1<<endl;
	}
	return 0;
}

LCA

int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[tiao[x][i]]>=dep[y])
		{
			x=tiao[x][i];
		}
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--)
	{
		if(tiao[x][i]!=tiao[y][i])
		{
			x=tiao[x][i];
			y=tiao[y][i];
		}
	}
	return tiao[x][0];
}

二叉树前、中、后序遍历：

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> adj[1000001];
void xian(int x)
{
    cout<<x<<' ';
    if(adj[x][0]!=0)xian(adj[x][0]);
    if(adj[x][1]!=0)xian(adj[x][1]);
}
void zhong(int x)
{
    if(adj[x][0]!=0)zhong(adj[x][0]);
    cout<<x<<' ';
    if(adj[x][1]!=0)zhong(adj[x][1]);
}
void hou(int x)
{
    if(adj[x][0]!=0)hou(adj[x][0]);
    if(adj[x][1]!=0)hou(adj[x][1]);
    cout<<x<<' ';
}
int main()
{
    // freopen("filename.in", "r", stdin);
    // freopen("filename.out", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        adj[i].push_back(x);
        adj[i].push_back(y);
    }
    xian(1);
    cout<<endl;
    zhong(1);
    cout<<endl;
    hou(1);
    cout<<endl;
    return 0;
}

dij:

struct nod
{
	int x,z;
};
bool operator <(nod xx,nod yy)
{
	return xx.z>yy.z;
}
vector<nod> adj[200100];
int dis[1000001];
bool flag[1000001];
void sb(int s)
{
	priority_queue<nod> q;
	q.push({s,0});
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0;
	while(!q.empty())
	{
		nod t=q.top();
		q.pop();
	//	cout<<t.x<<endl;
		if(flag[t.x])
			continue;
		flag[t.x]=true;
		for(int i=0;i<adj[t.x].size();i++)
		{
			nod tt=adj[t.x][i];
			if(!flag[tt.x]&&dis[tt.x]>t.z+tt.z)
			{
				dis[tt.x]=t.z+tt.z;
				q.push({tt.x,dis[tt.x]});
			}
		}
	}
}

floyd:

void floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(f[i][j]>f[i][k]+f[k][j])
					f[i][j]=f[i][k]+f[k][j];
}

快读快写：

#define getchar_unlocked() getchar()
inline int read() {int x=0,ff=1;char ch=getchar_unlocked();while(ch<48||ch>57) {if(ch==45)ff=-1;ch=getchar_unlocked();}while(ch>=48&&ch<=57) x=(x<<3)+(x<<1)+(ch^48),ch=getchar_unlocked();return x*ff;}
void write(int x){if(!x){putchar('0');return;}int 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]);}
//n=read(),write(n)无换行，应该为write(anss[i]),cout<<endl;

欧拉筛

bool prime[10000000];
int pri[1000000],tot;
void ols(int n)
{
	prime[0]=prime[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!prime[i])
		{
			pri[++tot]=i;
		}
		for(int j=1;j<=tot && i*pri[j]<=n;j++)
		{
			prime[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
}

单调队列&&优化DP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+114;
int n,m,a[N],dp[N];
deque<int> q;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	dp[0]=0;
	q.push_back(0);
	for(int i=1;i<=n;i++)
	{
		while(!q.empty() && q.front()<i-m)
			q.pop_front();
		int ttt=q.front();
		dp[i]=dp[ttt]+a[i];
		while(!q.empty() && dp[i]<dp[q.back()])
			q.pop_back();
		q.push_back(i);
	}
	int minn=1e9;
	for(int i=n-m+1;i<=n;i++)minn=min(minn,dp[i]);
	cout<<minn;
	return 0;
}

斜率优化DP

将dp方程简化成一次函数（y=ax+b）的形式便可用斜率优化它。

维护上凸包：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+114;
int n,A,B,C;
int c[N];
int s[N];
int f[N];
int q[N];
int l,r;
int cc(int x){return x*x;}
int X(int k)
{
	return s[k];
}
int Y(int k)
{
	return f[k]+A*cc(s[k])-B*s[k];
}
int slove(int x,int y)
{
	return 1.0*(Y(x)-Y(y))/(X(x)-X(y));
}
signed main()
{
	cin>>n>>A>>B>>C;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+c[i];
	l=r=0;
	for(int i=1;i<=n;i++)
	{
		while(l<r && slove(q[l+1],q[l])>2*s[i]*A)
			l++;
		f[i]=f[q[l]]+A*cc(s[i]-s[q[l]])+B*(s[i]-s[q[l]])+C;
		while(l<r && slove(i,q[r])>slove(q[r],q[r-1]))
			r--;
		q[++r]=i;
	}
	cout<<f[n]<<endl;
	return 0;
}

维护下凸包就：

		while(l<r && slove(q[l+1],q[l])<2*s[i]*A)
			l++;
		f[i]=f[q[l]]+A*cc(s[i]-s[q[l]])+B*(s[i]-s[q[l]])+C;
		while(l<r && slove(i,q[r])<slove(q[r],q[r-1]))
			r--;

二分图的最大匹配

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+114;
int n,m,path[N],use[N],a[N][N];
bool dfs(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(a[u][i] && !use[i])
		{
			use[i]=1;
			if(!path[i] || dfs(path[i]))
			{
				path[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	cin>>n>>m;
	int x,y;
	while(cin>>x>>y)
	{
		a[x][y]=1;
	}
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		memset(use,0,sizeof use);
		if(dfs(i))
		{
			sum++;
		}
	}
	cout<<sum;
	return 0;
}

火车头

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

RMQ

void pre()
{
	int x=log2(n);
	for(int i=1;i<=x;i++)
		for(int j=1;j+s[i]-1<=n;j++)
			mx[j][i]=__gcd(mx[j][i-1],mx[j+s[i-1]][i-1]);
}
int rmq(int a,int b)
{
	int x=log2(b-a+1);
	return max(mx[a][x],mx[b-s[x]+1][x]);
}

kmp && 扩展kmp

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+114;
int T,na,nb,nxt[N];
string a,b;
signed main()
{
	//cin>>T;
	//while(T--)
	//{
		cin>>a>>b;
		na=a.size(),nb=b.size();
		a=' '+a;
		b=' '+b;
		int j=0;
		for(int i=2;i<=nb;i++)
		{
			while(j && b[i]!=b[j+1])j=nxt[j];
			if(b[j+1]==b[i])j++;
			nxt[i]=j;
		}
		j=0;int ans=0;
		for(int i=1;i<=na;i++)
		{
			while(j && a[i]!=b[j+1])j=nxt[j];
			if(b[j+1]==a[i])j++;
			if(j==nb)
			{
				ans++;
				j=nxt[j];
			}
		}
		cout<<ans<<endl;
	//}
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e7+114;
int n,ext[N],nxt[N];
void qiunxt(string s)
{
	int l=0,p=0,k=1;
	int n=s.size();
	nxt[0]=n;
	int pp=0;
	while(pp+1<n && s[pp]==s[pp+1])pp++;
	nxt[1]=pp;
	for(int i=2;i<n;i++)
	{
		p=k+nxt[k]-1;
		l=nxt[i-k];
		if(i+l<=p)
		{
			nxt[i]=l;
		}
		else
		{
			int j=max(0ll,p-i+1);
			while(i+j<n && s[i+j]==s[j])j++;
			nxt[i]=j;
			k=i;
		}
	}
}
void qiuext(string s,string ss)
{
	int l=0,p=0,k=0;
	int n=s.size(),m=ss.size();
	int pp=0;
	while(pp<n && pp<m && s[pp]==ss[pp])pp++;
	ext[0]=pp;
	for(int i=1;i<n;i++)
	{
		p=k+ext[k]-1;
		l=nxt[i-k];
		if(i+l<=p)
		{
			ext[i]=l;
		}
		else
		{
			int j=max(0ll,p-i+1);
			while(i+j<n && j<m && s[i+j]==ss[j])j++;
			ext[i]=j;
			k=i;
		}
	}
}
signed main()
{
	string s,ss;
	cin>>s>>ss;
	qiunxt(ss);
	qiuext(s,ss);
	int x=0;
	for(int i=0;i<ss.size();i++)
		x=x^((i+1)*(nxt[i]+1));
	cout<<x<<endl;
	x=0;
	for(int i=0;i<s.size();i++)
		x=x^((i+1)*(ext[i]+1));
	cout<<x<<endl;
	return 0;
}

扩展kmp讲解

欧拉函数

int phi(int n)
{
	int ans=n;
	for (int i=2;i*i<=n;i++)
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			while(n%i==0)n/=i;
		}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}

分块

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+114;
int n,a[N],bl[N],tag[N];
int blo;
vector<int> adj[N];
void re(int x)
{
	adj[x].clear();
	for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++)
		adj[x].push_back(a[i]);
	sort(adj[x].begin(),adj[x].end());
}
void add(int x,int y,int z)
{
	for(int i=x;i<=min(bl[x]*blo,y);i++)
		a[i]+=z;
	if(bl[x]!=bl[y])
		for(int i=(bl[y]-1)*blo+1;i<=y;i++)
			a[i]+=z;
	for(int i=bl[x]+1;i<bl[y];i++)
		tag[i]+=z;
	re(bl[x]);
	re(bl[y]);
}
signed main()
{
	cin>>n;
	blo=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		bl[i]=(i-1)/blo+1;
		adj[bl[i]].push_back(a[i]);
	}
	for(int i=1;i<=bl[n];i++)
		sort(adj[i].begin(),adj[i].end());
	int q=n;
	while(q--)
	{
		int op,l,r,c;
		cin>>op>>l>>r>>c;
		if(op==0)
			add(l,r,c);
		else
		{
			int ans=0;
			for(int i=l;i<=min(bl[l]*blo,r);i++)
				if(a[i]+tag[bl[i]]<c*c)
					ans++;
			if(bl[l]!=bl[r])
				for(int i=(bl[r]-1)*blo+1;i<=r;i++)
					if(a[i]+tag[bl[i]]<c*c)
						ans++;
			for(int i=bl[l]+1;i<bl[r];i++)
			{
				int tt=c*c-tag[i];
				ans+=lower_bound(adj[i].begin(),adj[i].end(),tt)-adj[i].begin();
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

莫队

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+114;
int n,m,a[N],b[N],blo,cnt[N],ans,anss[N];
int read(){int x=0,p=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*p;}
struct node
{
	int l,r,id;
}q[N];
bool cmp(node x,node y)
{
	if(x.l/blo==y.l/blo)
		return x.r<y.r;
	return x.l<y.l;
}
void jia(int p)
{
	if(cnt[p]==0)ans++;
	cnt[p]++;
}
void jian(int p)
{
	if(cnt[p]==1)ans--;
	cnt[p]--;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	n=read();
	blo=sqrt(n);
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=a[i];
	sort(b+1,b+1+n);
	int sum=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+sum,a[i])-b;
	m=read();
	for(int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l>q[i].l)jia(a[--l]);
		while(r<q[i].r)jia(a[++r]);
		while(l<q[i].l)jian(a[l++]);
		while(r>q[i].r)jian(a[r--]);
		anss[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)printf("%d\n",anss[i]);
	return 0;
}

带修莫队：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+114;
int n,m,a[N],b[N],blo,cnt[N],ans,anss[N],cntr,cntp;
int read(){int x=0,p=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-')p=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*p;}
struct node
{
	int l,r,t,id;
}q[N];
struct nod
{
	int l,r;
}qq[N];
bool cmp(node x,node y)
{
	if(x.l/blo==y.l/blo)
	{
		if(x.r/blo==y.r/blo)
			return x.t<y.t;
		return x.r<y.r;
	}
	return x.l<y.l;
}
void jia(int p)
{
	if(cnt[p]==0)ans++;
	cnt[p]++;
}
void jian(int p)
{
	if(cnt[p]==1)ans--;
	cnt[p]--;
}
void upd(int i,int x)
{
	if(q[i].l<=qq[x].l && qq[x].l<=q[i].r)
	{
		jian(a[qq[x].l]);
		jia(qq[x].r);
	}
	swap(a[qq[x].l],qq[x].r);
	//因为修改后的下一次到这个修改操作一定相反(即修改该位置->还原该位置->修改该位置...如此循环)只需交换即可
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	blo=pow(n,0.666);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		char op;
		cin>>op;
		int l,r;
		cin>>l>>r;
		if(op=='Q')q[++cntp]={l,r,cntr,cntp};
		else qq[++cntr]={l,r};
	}
	sort(q+1,q+1+cntp,cmp);
	int l=1,r=0,t=0;
	for(int i=1;i<=cntp;i++)
	{
		while(l>q[i].l)jia(a[--l]);
		while(r<q[i].r)jia(a[++r]);
		while(l<q[i].l)jian(a[l++]);
		while(r>q[i].r)jian(a[r--]);
		while(t<q[i].t)upd(i,++t);
		while(t>q[i].t)upd(i,t--);
		anss[q[i].id]=ans;
	}
	for(int i=1;i<=cntp;i++)printf("%d\n",anss[i]);
	return 0;
}

网络流：

最大流

#include<bits/stdc++.h>
#define inf 1e9
#define int long long
#define getchar_unlocked() getchar()
inline int read() {int x=0,ff=1;char ch=getchar_unlocked();while(ch<48||ch>57) {if(ch==45)ff=-1;ch=getchar_unlocked();}while(ch>=48&&ch<=57) x=(x<<3)+(x<<1)+(ch^48),ch=getchar_unlocked();return x*ff;}
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int M=5e6+114,N=1e5+114;
int n,m,cur[N],head[N],etot=1,d,ANS;
int st,en,dis[N];
struct node
{
	int to,w,nxt;
}edge[M];
void add(int x,int y,int z)
{
	etot++;edge[etot]={y,z,head[x]};head[x]=etot;
	etot++;edge[etot]={x,0,head[y]};head[y]=etot;
}
bool bfs()
{
	rep(i,st,en)
		cur[i]=head[i],dis[i]=0;
	queue<int> q;q.push(st);dis[st]=1;
	while(!q.empty())
	{
		int t=q.front();q.pop();
		for(int i=head[t];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(edge[i].w && !dis[v])
			{
				dis[v]=dis[t]+1;
				q.push(v);
			}
		}
	}
	if(!dis[en])
		return 0;
	else return 1;
}
int dfs(int u,int m)
{
	if(u==en)return m;
	int flo=0;
	for(int &i=cur[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(edge[i].w && dis[v]==dis[u]+1)
		{
			int vv=edge[i].w;int tt=dfs(v,min(m,vv));
			edge[i].w-=tt,edge[i^1].w+=tt;
			m-=tt;flo+=tt;
			if(m==0)break;
		}
	}
	if(!flo)dis[u]=-1;
	return flo;
}
int wdf()
{
	int ans=0;
	while(bfs())
		ans+=dfs(st,inf);
	return ans;
}
int id(int x,int y){return (x-1)*m+y;}
signed main()
{
	cin>>n>>m;
	st=0,en=n*m+2*n*(m-1)+2*(n-1)*m+1;
	int cnt=n*m;
	rep(i,1,n)rep(j,1,m)
	{
		int x=read();ANS+=x;
		add(st,id(i,j),x);
	}
	rep(i,1,n)rep(j,1,m)
	{
		int x=read();ANS+=x;
		add(id(i,j),en,x);
	}
	rep(i,1,n-1)rep(j,1,m)
	{
		int x=read();ANS+=x;++cnt;
		add(st,cnt,x);
		add(cnt,id(i,j),inf);
		add(cnt,id(i+1,j),inf);
	}
	rep(i,1,n-1)rep(j,1,m)
	{
		int x=read();ANS+=x;++cnt;
		add(cnt,en,x);
		add(id(i,j),cnt,inf);
		add(id(i+1,j),cnt,inf);
	}
	rep(i,1,n)rep(j,1,m-1)
	{
		int x=read();ANS+=x;++cnt;
		add(st,cnt,x);
		add(cnt,id(i,j),inf);
		add(cnt,id(i,j+1),inf);
	}
	rep(i,1,n)rep(j,1,m-1)
	{
		int x=read();ANS+=x;++cnt;
		add(cnt,en,x);
		add(id(i,j),cnt,inf);
		add(id(i,j+1),cnt,inf);
	}
	cout<<ANS-wdf()<<endl;
	return 0;
}

费用流:

#include<bits/stdc++.h>
#define int long long
#define inf 1e9
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int M=1e5+2,N=5e3+1;
int n,m,t[N],st,en,head[N],cur[N],etot=1,vis[N],dis[N],maxliu,maxfei;
struct node
{
    int to,w,nxt,cont;
}edge[M];
void add(int x,int y,int z,int w)
{
    edge[++etot]={y,z,head[x],w};head[x]=etot;
    edge[++etot]={x,0,head[y],-w};head[y]=etot;
}
bool bfs()
{
    rep(i,st,en)cur[i]=head[i],vis[i]=0,dis[i]=inf;
    queue<int> q;q.push(st);dis[st]=0;vis[st]=1;
    while(!q.empty())
    {
        int t=q.front();q.pop(),vis[t]=0;
        for(int i=head[t];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(edge[i].w && dis[to]>dis[t]+edge[i].cont)
            {
                dis[to]=dis[t]+edge[i].cont;
                if(!vis[to])
                    vis[to]=1,q.push(to);
            }
        }
    }
    return (dis[en]==inf?0:1);
}
int dfs(int u,int m)
{
    if(u==en)return m;vis[u]=1;int flo=0;
    for(int &i=cur[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(!vis[to] && dis[to]==dis[u]+edge[i].cont && edge[i].w)
        {
            int t=dfs(to,min(m,edge[i].w));maxfei+=t*edge[i].cont;
            edge[i].w-=t,edge[i^1].w+=t;flo+=t;m-=t;if(m==0)break;
        }
    }
    vis[u]=0;
    if(!flo)dis[u]=-1;
    return flo;
}
int dinic()
{
    maxliu=0;
    while(bfs())maxliu+=dfs(st,inf);
    return maxliu;
}

BSGS && exBSGS

已知 $a,p$ 互素，求解同余方程：

a^x\equiv b(\operatorname{mod}\ p)

因为 $a,p$ 互素，所以可以在模 $p$ 意义下执行关于 $a$ 的乘法、除法运算。

$令x=kt-m$ ,其中 $t=\left\lceil\sqrt{p}\right\rceil,0\leq k\leq t$ , 则有 $a^kt- m\equiv b(\bmod\ p)$ ,即 $a^kt\equiv$ $a^mb({\mathrm{mod~}}p)$ 。

对于所有的 $m\in[0,t-1]$ ，把 $a^mb({\mathrm{mod}}p)$ 的结果存入 $Hash$ 表。

接着枚举 $k\in[0,t]$ ,计算 $a^{kt}({\mathrm{mod}}p)$ ，并在Hash表中查找是否有对应的 $m$ 值。若有，即找到了满足条件的 $k$ 和 $m$ 。

时间复杂度 $O(\sqrt{p})$ ，这种算法称为 $Baby\ Step\ Giant\ Step$ 。

ex BSGS :

同一般 BSGS 做法进行根号平衡，设 $t = \lceil \sqrt{2\varphi(p)} \rceil$ ， $x = pt - q (0 \le q < t)$ ，考虑对原式进行变形：

a^{pt - q} \equiv b \pmod{p}

a^{pt} \equiv ba^q \pmod{p}

注意到两步间并非等价变形，后者是前者的必要条件。预先将 $a^{pt} (0 \le p \le t)$ 的值存入散列表，之后枚举 $a^q$ 并在散列表中查询 $ba^q$ 的值是否存在。若存在，则所对应的 $pt - q$ 即为 $x$ 的一个可能值，代入原式可知是否确实能成为 $x$ 。

事情至此尚未解决，这是由于 $a^{pt}$ 的值可能出现重复。对于重复的值，仅前两个出现的位置可能成为答案。查询时两值均进行检验即可。

时间复杂度为 O( $\sqrt{\varphi(p)}$ )。

然后是正确性证明。

首先证明答案上界。前文设 $t = \lceil \sqrt{2\varphi(p)} \rceil$ ，意味着 $2\varphi(p)$ 是答案的上界。事实上确实如此。根据扩展欧拉定理 $a^x \equiv a^{x \mod \varphi(p) + \varphi(p)} \pmod{p}$，若 $x > 2\varphi(p)$ ，必然有 $x \mod \varphi(p) + \varphi(p)$ 是更优的答案。上界得证。

之后证明仅保留前两个相等的值的正确性。由扩展欧拉定理，形象化地说， $a^x$ 的值形成了一个 $\rho$ 形，即在经过长度不超过 $\varphi(p)$ 的非循环数后进入长度不超过 $\varphi(p)$ 的循环节。若一个值出现多次，则它的每一次出现均在循环节上。由于 $q < t$ ，某一个值第二次出现时对应的 $a^{pt - q}$ 必然大于第一次出现时对应的 $a^{pt}$ ，这意味着只有第一次出现某一个值时 $a^{pt - q}$ 才可能在非循环数中。由于在循环节中得到的答案不会产生差异，取前两次必定能考虑到答案的所有情况。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define int long long
using namespace std;
#define getchar_unlocked() getchar()
inline int read() {int x=0,ff=1;char ch=getchar_unlocked();while(ch<48||ch>57) {if(ch==45)ff=-1;ch=getchar_unlocked();}while(ch>=48&&ch<=57) x=(x<<3)+(x<<1)+(ch^48),ch=getchar_unlocked();return x*ff;}
void write(int x){if(!x){putchar('0');return;}int 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]);}
unordered_map<int,int> mp_BSGS;
gp_hash_table<int,int> mp_ex_BSGS[2];
int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)res=(a*res)%p;
		a*=a;a%=p;
		b>>=1;
	}
	return res;
}
int phi(int x)
{
	int ans=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			ans=ans/i*(i-1);
			while(x%i==0)x/=i;
		}
	}
	if(x>1)ans=ans/x*(x-1);
	return ans;
}
int BSGS(int xx,int yy,int p)
{
	mp_BSGS.clear();
	yy%=p;xx%=p;
	if(xx==yy && xx==0)return 1;
	if(yy==1)return 0;
	int t=sqrt(p)+1;
	for(int i=0;i<=t;i++)
		mp_BSGS[qpow(xx,i,p)*yy%p]=i;
	bool flag=0;int xxx=1e18;
	int a=qpow(xx,t,p);
	for(int i=1;i<=t;i++)
	{
		if(mp_BSGS[qpow(a,i,p)] && i*t-mp_BSGS[qpow(a,i,p)]>=0)
		{
			flag=1;
			xxx=min(xxx,i*t-mp_BSGS[qpow(a,i,p)]);
		}
	}
	if(xxx!=1e18 && xxx>0)return xxx;
	else return -1;
}
int ex_BSGS(int xx,int yy,int p)
{
	mp_ex_BSGS[1].clear();mp_ex_BSGS[0].clear();
	xx%=p,yy%=p;
	if(p==1 || yy==1) return 0;
	int t=ceil(sqrt(2*phi(p)));
	for(int i=0;i<=t;i++)
	{
		int tt=qpow(xx,t*i,p);
		if(!mp_ex_BSGS[0][tt])mp_ex_BSGS[0][tt]=i;
		else mp_ex_BSGS[1][tt]=i;
	}
	int res=qpow(2,50,1000000000000000000);
	for(int i=0;i<t;i++)
	{
		int tt=(qpow(xx,i,p)*yy)%p;
		if(mp_ex_BSGS[0][tt] && qpow(xx,mp_ex_BSGS[0][tt]*t-i,p)==yy)res=min(res,mp_ex_BSGS[0][tt]*t-i);
		if(mp_ex_BSGS[1][tt] && qpow(xx,mp_ex_BSGS[1][tt]*t-i,p)==yy)res=min(res,mp_ex_BSGS[1][tt]*t-i);
	}
	return res==qpow(2,50,1000000000000000000)?-1:res;
}
signed main()
{
	int xx,yy,p;
	while(1)
	{
		xx=read(),p=read(),yy=read();
		if(xx+p+yy==0)break;
		int t=ex_BSGS(xx,yy,p);
		if(t==-1)printf("No Solution\n");
		else write(t),printf("\n");
	}
	return 0;
}

求逆元：

逆元是什么？

ax\equiv 1(\bmod\,\,p)

求 $x$ 。

通过费马小定理求解逆元（前提 $p$ 是质数， $a,p$ 互质）。

int qpow(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)res=(a*res)%p;
		a*=a;a%=p;
		b>>=1;
	}
	return res;
}

qpow(a,p-2,p);

通过扩展~~欧里几得~~求逆元（前提 $a,p$ 互质）：

将

ax\equiv 1(\bmod\,\,p)

转化成

ax+py=1

void exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int tx=x;x=y,y=tx-y*(a/b);
}

x=y=0;
exgcd(a,p);

扩展：

如果要求 $ax+by=c$ 呢？

根据裴蜀定理， $gcd(a,b) | c$ 时才有解。

那么通过扩展~~欧里几得~~得到了最小的满足 $ax+by=gcd(a,b)$ 的 $x$ ，然后将 $x\cdot \frac{c}{gcd(a,b)}$ ，就可以得到最小解啦。

通过线性求逆元：

首先我们有一个 $1^{-1}=1(\bmod \ p)$

然后设 $p=k*i+r$ ， $1<r<i$ 再将这个式子放到 $(\bmod\ p)$ 意义下就会得到:

k*i+r\equiv0(modp)

然后乘上 $i^ {-1}$ ， $r^ {-1}$ 就可以得到:

k* r^ {-1} + i^ {-1} \equiv0(modp)

i^ {-1} =-k* r^ {-1} (modp)

$$i^ {-1} \equiv-[ \frac {p}{i} ]* (p\ \bmod\ i)^ {-1} (\bmod\ p) $$

于是，我们就可以从前面推出当前的逆元了。

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

中国剩余定理（CRT）

对于同余方程组 $x\equiv a_i({\mathrm{mod}}m_i)\left(i=1...n\right)$ ,若 $m_i$ 两两互素, 则 $x$ 在 $\bmod\ M,(M=m_1m_2...m_n)$ 下有唯一解。

中国剩余定理同时也给出了构造解的方法，令 $M=m_1m_2...m_n,M_i=\frac M{m_i}$ ,显然

$(M_{i},m_{i})=1$ ,所以 $M_i$ 关于模 $m_i$ 的逆元存在。

把逆元设为 $t_i$ ,于是有：

$$M_it_i\equiv1\pmod{m_i},M_it_i\equiv0\pmod{m_j}(j\neq i) $$

进一步：

$$a_iM_it_i\equiv a_i(\operatorname{mod}m_i),a_iM_it_i\equiv0\pmod{m_j}\:(j\neq i) $$

解为

x\equiv\sum_{i=1}^na_iM_it_i\pmod M

const int N=100;
int n,a[N],m[N],M=1,dM[N],dMM[N];
int x,y;
void exgcd(int a,int b)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int tx=x;x=y,y=tx-y*(a/b);
}
signed main()
{
	n=read();
	rep(i,1,n)m[i]=read(),a[i]=read(),M*=m[i];
	rep(i,1,n)dM[i]=M/m[i],x=y=0,exgcd(dM[i],m[i]),dMM[i]=x;
	int x=0;
	rep(i,1,n)
	{
		x+=a[i]*dM[i]*dMM[i];
		x=(x%M+M)%M;
	}
	write(x);
	return 0;
}

决策单调性优化dp:

#include<bits/stdc++.h>
#define int long long
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int N=2e5+114;
int n,L,c[N],sum[N],f[N],top,now=1;
int w(int i,int j){return (j-i-1+sum[j]-sum[i]-L)*(j-i-1+sum[j]-sum[i]-L);}
struct node{int l,r,x;}stk[N];
int findx(int i)
{
	int l=stk[top].l,r=stk[top].r;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(f[i]+w(i,mid)<f[stk[top].x]+w(stk[top].x,mid))
			r=mid-1;
		else l=mid+1;
	}
	return l;
}
signed main()
{
	cin>>n>>L;
	for(int i=1;i<=n;i++)cin>>c[i],sum[i]=sum[i-1]+c[i];
	stk[++top]={1,n,0};
	for(int i=1;i<=n;i++)
	{
		f[i]=f[stk[now].x]+w(stk[now].x,i);
		while(i<stk[top].l && f[i]+w(i,stk[top].l)<f[stk[top].x]+w(stk[top].x,stk[top].l))
			top--;
		int u=findx(i);
		stk[top].r=u-1;
		if(u<=n)stk[++top]={u,n,i};
		if(i>=stk[now].r)now++;
	}
	cout<<f[n];
	return 0;
}

AC自动机：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+114;
int n;
struct node
{
	int fail;
	int chr[26];
	int ed;
}trie[N];
int cnt=0;
void trie_build(string s)
{
	int len=s.size();
	int now=0;
	for(int i=0;i<len;i++)
	{
		int sb=s[i]-'a';
		if(!trie[now].chr[sb])
			trie[now].chr[sb]=++cnt;
		now=trie[now].chr[sb];
	}
	trie[now].ed++;
}
void Get_fail()
{
	queue<int> q;
	for(int i=0;i<26;i++)
	{
		if(trie[0].chr[i])
		{
			trie[trie[0].chr[i]].fail=0;
			q.push(trie[0].chr[i]);
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(trie[u].chr[i])
			{
				trie[trie[u].chr[i]].fail=trie[trie[u].fail].chr[i];
				q.push(trie[u].chr[i]);
			}
			else trie[u].chr[i]=trie[trie[u].fail].chr[i];
		}
	}
}
//Fail指针的实质含义是什么呢？
//如果一个点i的Fail指针指向j。那么root到j的字符串是root到i的字符串的一个后缀。
int AC_query(string s)
{
	int len=s.size();
	int now=0,ans=0;
	for(int i=0;i<len;i++)
	{
		now=trie[now].chr[s[i]-'a'];
		for(int t=now;t && trie[t].ed!=-1;t=trie[t].fail)
		{
			ans+=trie[t].ed;
			trie[t].ed=-1;
		}
	}
	return ans;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(trie,0,sizeof trie);
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			string s;
			cin>>s;
			trie_build(s);
		}
		string s;
		cin>>s;
		Get_fail();
		cout<<AC_query(s)<<endl;
	}
	return 0;
}

线性基

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000;
int a[N+1],tmp[N+1];
struct node{int x,z;}cs[N+1];
bool flag=0;//判断是否能构成0
void insert(int x)
{
	for(int i=N;i>=0;i--)
	{
		if(x&(1ll<<i))
		{
			if(!a[i]){a[i]=x;return;}
			else x^=a[i];
		}
	}
	flag=1;
}
bool check(int x)
{
	for(int i=N;i>=0;i--)
	{
		if(x&(1ll<<i))
		{
			if(!a[i])return 0;
			x^=a[i];
		}
	}
	return 1;
}
int qmax(int res=0)
{
	for(int i=N;i>=0;i--)
		res=max(res,(res^a[i]));
	return res;
}
int qmin()
{
	if(flag)return 0;
	for(int i=0;i<=N;i++)
		if(a[i])return a[i];
	return -1;
}
int query(int k)
{
	k-=flag;
	if(!k)return 0;
	int res=0,ans=0;
	for(int i=0;i<=N;i++)
	{
		for(int j=i-1;j>=0;j--)
			if(a[i] & (1ll<<j))a[i]^=a[j];
		if(a[i])tmp[++ans]=a[i];
	}
	if(k>=(1ll<<ans))return -1;
	for(int i=1;i<=ans;i++)if(k&(1ll<<i))res^=tmp[i];
	return res;
}
bool cmp(node x,node y){return x.z<y.z;}
signed main()
{
	int n;
	cin>>n;int ans=0;
	for(int i=1;i<=n;i++)
		cin>>cs[i].x>>cs[i].z;
	sort(cs+1,cs+1+n,cmp);
	for(int i=n;i>=1;i--)
	{
		if(!check(cs[i].x))ans+=cs[i].z;
		insert(cs[i].x);
	}
	cout<<ans;
	return 0;
}

FHQ_Treap:

#include<bits/stdc++.h>
#define lint long long
using namespace std;
const int N=2e5+114;
int n;
struct Treap
{
	int tot=0,root=0;
	struct node
	{
		int l,r,s,v,k;//左端点，右端点，子树大小，权值，随机大小（堆）
	}tr[N];
	void pushup(int u){tr[u].s=tr[tr[u].l].s+tr[tr[u].r].s+1;}
	pair<int,int> Treap_split(int p,int k)//按点的个数分裂
	//p是当前节点，k是要分给左儿子的节点个数，pair指的是分裂后的左儿子，右儿子
	{
		if(!p)return make_pair(0,0);
		if(k<=tr[tr[p].l].s)
		{
			auto u=Treap_split(tr[p].l,k);
			tr[p].l=u.second;
			pushup(p);
			u.second=p;
			return u;			
		}
		auto u=Treap_split(tr[p].r,k-tr[tr[p].l].s-1);
		tr[p].r=u.first;
		pushup(p);
		u.first=p;
		return u;
	}
	pair<int,int> Treap_val(int p,int v)//按值分裂k，把小于v的子树拆出来
	{
		if(!p)return make_pair(0,0);
		if(tr[p].v<v)
		{
			auto u=Treap_val(tr[p].r,v);
			tr[p].r=u.first;
			pushup(p);
			u.first=p;
			return u;
		}
		auto u=Treap_val(tr[p].l,v);
		tr[p].l=u.second;
		pushup(p);
		u.second=p;
		return u;
	}
	int merge(int x,int y)//合并子树
	{
		if(!x || !y)return x+y;
		if(tr[x].k>tr[y].k)
		{
			tr[x].r=merge(tr[x].r,y);
			pushup(x);
			return x;
		}
		tr[y].l=merge(x,tr[x].l);
		pushup(y);
		return y;
	}
	int find(int x,int v)
	{
		if(!x)return 0;
		if(v<tr[x].v)return find(tr[x].l,v);
		if(v>tr[x].v)return find(tr[x].r,v);
		return x;
	}
	int add(int x){tr[++tot]=node{0,0,1,x,rand()};return tot;}//新建节点
	void insert(int v)//加入v
	{
		auto [x,y]=Treap_val(root,v);
		int t=add(v);
		x=merge(x,t);
		root=merge(x,y);
	}
	void del(int v)//删除v值对应的点，有多个v只会删一个，而且是最小的
	{
		auto [x,y]=Treap_val(root,v);
		auto [z1,z2]=Treap_split(y,1);
		root=merge(x,z2);
	}
	int rk(int v)//输出v值对应的排名。如果有多个v，输出最小的那个，如果没有v，输出大于v的排名
	{
		auto [x,y]=Treap_val(root,v);
		int t=tr[x].s+1;
		root=merge(x,y);
		return t;
	}
	int getk(int k)//得到排名第k的值是多少，不用考虑rk那么多情况，没找到就是0
	{
		auto x=Treap_split(root,k-1);
		auto y=Treap_split(x.second,1);
		int o=y.first;
		root=merge(x.first,merge(y.first,y.second));
		return tr[o].v;
	}
	int prev(int v)//查前驱，用查排名和查第几实现。
	{
		return getk(rk(v)-1);
	}
	int nextv(int v)
	{
		return getk(rk(v+1));
	}
}FHQ_Treap;
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		if(a==1)FHQ_Treap.insert(b);
		else if(a==2)FHQ_Treap.del(b);
		else if(a==3)cout<<FHQ_Treap.rk(b)<<endl;
		else if(a==4)cout<<FHQ_Treap.getk(b)<<endl;
		else if(a==5)cout<<FHQ_Treap.prev(b)<<endl;
		else cout<<FHQ_Treap.nextv(b)<<endl;
	}
	return 0;
}

通过的题目
P1000

P1010

P1047

P1059

P1066

P1070

P1096

P1135

P1221

P1280

P1355

P1443

P1511

P1565

P1597

P1693

P1711

P1735

P1855

P1911

P2081

P2084

P2127

P2245
P2424

P2442

P2673

P3620

P2726

P2756

P2795

P3140

P3156

P3315

P3437

P3504

P3675

P3670

P3894

P3916

P3931

P3940

P3942

P4819

P4974

P5610

P5614

P5615
P5618

P5620

P5624

P5625

P5626

P5636

P5637

P5638

P5639

P5640

P5641

P5642

P5645

P5649

P5659

P5668

P6072

P6073

P9288

P9401

P8121

M011

M012

M029
M030

P9400

P6449

P6450

P6454

P6457

P6462

P6465

P6466

P10836

P10843

P10844

P10906

y0004

y0009

y0005

P11165

P11166

P11167

y0006

P11169

y0008

y1019

y1023
最近活动

图论: 28
字符串: 25
动态规划: 21
KMP: 16
字符串哈希: 14
斜率优化: 13
最大流: 7
网络流: 7
费用流: 6
单调队列/单调栈优化: 6
模板: 6
算法基础: 4
二分: 4
决策单调性: 3
数据结构: 3
二分图最大匹配: 3
最小费用最大流: 3
数学: 3
二分图最小点覆盖: 3
最小割: 3

zzx2024

个人简介

代码模板

暴力

预处理

优化

超快速

没环

通过的题目

最近活动

题目标签

状态

开发

支持