【CSP-S 2019模板复习2】

虽然 $mathrm{Stargazer}$ 很大可能要退役了

但还是把复习的模板汇总一个吧

虽然显然有些 $csp$ 根本不可能考

可持久化平衡树

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readchar(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch))s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=500005;
char xxx;
namespace treap{
	cs int inf=2147483647;
	cs int M=N*70;
	int siz[M],val[M],key[M],tot,lc[M],rc[M];
	inline int copy(int r1){
		if(!r1)return 0;
		int u=++tot;key[u]=rand(),lc[u]=lc[r1],rc[u]=rc[r1],val[u]=val[r1],siz[u]=siz[r1];
		return u;
	}
	inline int newnode(int k){
		int u=++tot;key[u]=rand(),val[u]=k,siz[u]=1;
		return u;
	}
	inline void pushup(int u){
		siz[u]=siz[lc[u]]+siz[rc[u]]+1;
	}
	inline void split(int u,int &r1,int &r2,int k){
		if(!u){r1=r2=0;return;}
		if(val[u]<=k){
			r1=copy(u);split(rc[u],rc[r1],r2,k),pushup(r1);
		}
		else r2=copy(u),split(lc[u],r1,lc[r2],k),pushup(r2);
	}
	inline void merge(int &u,int r1,int r2){
		if(!r1||!r2){u=copy(r1+r2);return;}
		if(key[r1]<key[r2]){
			u=copy(r2),merge(lc[u],r1,lc[r2]);
		}
		else u=copy(r1),merge(rc[u],rc[r1],r2);
		pushup(u);
	}
	inline void insert(int &rt,int k){
		int u=newnode(k);
		int r1=0,r2=0;
		split(rt,r1,r2,k);
		merge(r1,r1,u);
		merge(rt,r1,r2);
	}
	inline void delet(int &rt,int k){
		int r1=0,r2=0,r3=0;
		split(rt,r1,r2,k-1);
		split(r2,r2,r3,k);
		merge(r2,lc[r2],rc[r2]);
		merge(r1,r1,r2);
		merge(rt,r1,r3);
	}
	inline int getrk(int &rt,int k){
		int r1=0,r2=0;
		split(rt,r1,r2,k-1);
		int res=siz[r1]+1;
		merge(rt,r1,r2);
		return res;
	}
	inline int findk(int u,int k){
		if(k<=siz[lc[u]])return findk(lc[u],k);
		if(siz[lc[u]]+1==k)return val[u];
		return findk(rc[u],k-siz[lc[u]]-1);
	}
	inline int pre(int &rt,int k){
		int r1=0,r2=0,res;
		split(rt,r1,r2,k-1);
		if(!siz[r1])res=-inf;
		else res=findk(r1,siz[r1]);
		merge(rt,r1,r2);
		return res;
	}
	inline int nxt(int &rt,int k){
		int r1=0,r2=0,res;
		split(rt,r1,r2,k);
		if(!siz[r2])res=inf;
		else res=findk(r2,1);
		merge(rt,r1,r2);
		return res;
	}
}
char yyy;
int n,rt[N];
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	cout<<(&yyy-&xxx)/1024/1024<<'
';
	#endif
	n=read();
	for(int i=1;i<=n;i++){
		int v=read();
		rt[i]=rt[v];
		int op=read(),x=read();
		switch(op){
			case 1:treap::insert(rt[i],x);break;
			case 2:treap::delet(rt[i],x);break;
			case 3:cout<<treap::getrk(rt[i],x)<<'
';break;
			case 4:cout<<treap::findk(rt[i],x)<<'
';break;
			case 5:cout<<treap::pre(rt[i],x)<<'
';break;
			case 6:cout<<treap::nxt(rt[i],x)<<'
';break;
		}
	}
}

SAM

空间开到 $2n$

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(!isalpha(ch))ch=gc();
	while(isalpha(ch))s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1000005;
char xxx;
namespace Sam{
	cs int N=::N*2;
	int tot=1,last=1;
	int nxt[N][26],fa[N],len[N],siz[N];
	inline void insert(int c){
		int cur=++tot,p=last;last=cur;
		len[cur]=len[p]+1,siz[cur]=1;
		for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=cur;
		if(!p)fa[cur]=1;
		else{
			int q=nxt[p][c];
			if(len[p]+1==len[q])fa[cur]=q;
			else{
				int clo=++tot;
				fa[clo]=fa[q],len[clo]=len[p]+1;
				memcpy(nxt[clo],nxt[q],sizeof(nxt[q]));
				for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=clo;
				fa[q]=fa[cur]=clo;
			}
		}
	}
	int rk[N],buc[N];
	ll ans;
	inline void buc_sort(){
		for(int i=1;i<=tot;i++)buc[len[i]]++;
		for(int i=1;i<=tot;i++)buc[i]+=buc[i-1];
		for(int i=tot;i;i--)rk[buc[len[i]]--]=i;
		for(int i=tot;i;i--){
			int u=rk[i];
			siz[fa[u]]+=siz[u];
			if(siz[u]>1)chemx(ans,1ll*siz[u]*len[u]);
		}
		cout<<ans;
	}
}
char s[N];
int n;
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=readstring(s);
	for(int i=1;i<=n;i++)Sam::insert(s[i]-'a');
	Sam::buc_sort();
}

AC自动机

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch))s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=200005;
namespace Ac{
	int nxt[N][26],fail[N],tot,ed[N];
	inline void insert(char *s,int l,int id){
		int p=0;
		for(int i=1;i<=l;i++){
			int c=s[i]-'a';
			if(!nxt[p][c])nxt[p][c]=++tot;
			p=nxt[p][c];
		}
		ed[id]=p;
	}
	inline void buildfail(){
		queue<int> q;
		for(int i=0;i<26;i++){
			if(nxt[0][i])q.push(nxt[0][i]);
		}
		while(!q.empty()){
			int p=q.front();q.pop();
			for(int c=0;c<26;c++){
				int v=nxt[p][c];
				if(!v)nxt[p][c]=nxt[fail[p]][c];
				else fail[v]=nxt[fail[p]][c],q.push(v);
			}
		}
	}
	int val[N];
	inline void run(char *s,int l){
		int p=0;
		for(int i=1;i<=l;i++){
			int c=s[i]-'a';
			while(p&&!nxt[p][c])p=fail[p];
			p=nxt[p][c];
			val[p]++;
		}
	}
	vector<int> e[N];
	void dfs1(int u){
		for(int &v:e[u]){
			dfs1(v),val[u]+=val[v];
		}
	}
	inline void calc(){
		for(int i=1;i<=tot;i++)e[fail[i]].pb(i);
		dfs1(0);
	}
}
int n;
char s[2000005];
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=read();
	for(int i=1;i<=n;i++){
		int len=readstring(s);
		Ac::insert(s,len,i);
	}
	Ac::buildfail();
	int len=readstring(s);
	Ac::run(s,len);
	Ac::calc();
	for(int i=1;i<=n;i++)cout<<Ac::val[Ac::ed[i]]<<'
';
}

$Pam$

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch))s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=500005;
namespace Pam{
	int nxt[N][26],s[N],fa[N],len[N],tot,last,cnt,dep[N];
	inline void init(){
		fa[0]=1,len[1]=-1,tot=1,s[0]=-1;
	}
	inline int find(int p,int k){
		while(s[k-len[p]-1]!=s[k])p=fa[p];
		return p;
	}
	inline int insert(int c){
		s[++cnt]=c;
		int p=find(last,cnt);
		if(!nxt[p][c]){
			fa[++tot]=nxt[find(fa[p],cnt)][c];
			nxt[p][c]=tot,len[tot]=len[p]+2,dep[tot]=dep[fa[tot]]+1;
		}
		last=nxt[p][c];
		return dep[last];
	}
}
char s[N];
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	Pam::init();
	int n=readstring(s);
	int last=0;
	for(int i=1;i<=n;i++){
		last=Pam::insert((s[i]-97+last)%26);
		cout<<last<<" ";
	}
	
}

$DDP$

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=100005;
cs int inf=1e9;
struct mat{
	int a[2][2];
	mat(){memset(a,0,sizeof(a));}
	friend inline mat operator *(cs mat &a,cs mat &b){
		mat c;
		c.a[0][0]=max(a.a[0][0]+b.a[0][0],a.a[0][1]+b.a[1][0]);
		c.a[0][1]=max(a.a[0][0]+b.a[0][1],a.a[0][1]+b.a[1][1]);
		c.a[1][0]=max(a.a[1][0]+b.a[0][0],a.a[1][1]+b.a[1][0]);
		c.a[1][1]=max(a.a[1][0]+b.a[0][1],a.a[1][1]+b.a[1][1]);
		return c;
	}
};
int v[N];
vector<int> e[N];
int siz[N],son[N],fa[N],top[N],but[N],in[N],dep[N],idx[N],dfn;
int n,m,f[N][2];
mat val[N];
inline void calc(int u){
	int f0=0,f1=v[u];
	for(int &v:e[u]){
		if(v==fa[u]||v==son[u])continue;
		f0+=max(f[v][1],f[v][0]),f1+=f[v][0];
	}
	val[u].a[0][0]=f0,val[u].a[0][1]=f1,val[u].a[1][0]=f0,val[u].a[1][1]=-inf;
}
namespace Seg{
	#define lc (u<<1)
	#define rc ((u<<1)|1)
	#define mid ((l+r)>>1)
	mat s[N<<2];
	void build(int u,int l,int r){
		if(l==r){
			calc(idx[l]),s[u]=val[idx[l]];
			return;
		}
		build(lc,l,mid),build(rc,mid+1,r);
		s[u]=s[rc]*s[lc];
	}
	void update(int u,int l,int r,int p){
		if(l==r){s[u]=val[idx[l]];return;}
		if(p<=mid)update(lc,l,mid,p);
		else update(rc,mid+1,r,p);
		s[u]=s[rc]*s[lc];
	}
	mat query(int u,int l,int r,int st,int des){
		if(st<=l&&r<=des)return s[u];
		if(des<=mid)return query(lc,l,mid,st,des);
		if(mid<st)return query(rc,mid+1,r,st,des);
		return query(rc,mid+1,r,st,des)*query(lc,l,mid,st,des);
	}
	#undef lc
	#undef rc
	#undef mid
}
inline mat query(int u){
	return Seg::query(1,1,n,in[top[u]],in[but[top[u]]]);
}
inline void pathupdate(int u,int k){
	val[u].a[0][1]+=k-v[u],v[u]=k;
	mat pre,now;
	while(u){
		pre=query(u);
		Seg::update(1,1,n,in[u]);
		now=query(u);
		u=fa[top[u]];
		if(!u)break;
		val[u].a[0][0]+=max(now.a[0][0],now.a[0][1])-max(pre.a[0][0],pre.a[0][1]);
		val[u].a[1][0]=val[u].a[0][0];
		val[u].a[0][1]+=now.a[0][0]-pre.a[0][0];
	}
}
void dfs1(int u){
	siz[u]=1,f[u][1]=v[u];
	for(int &v:e[u]){
		if(v==fa[u])continue;
		dep[v]=dep[u]+1,fa[v]=u;
		dfs1(v),siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}
void dfs2(int u,int tp){
	top[u]=tp,idx[++dfn]=u,in[u]=dfn,but[top[u]]=u;
	if(son[u])dfs2(son[u],tp);
	for(int &v:e[u]){
		if(v==fa[u]||v==son[u])continue;
		dfs2(v,v);
	}
}
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=read(),m=read();
	generate(v+1,v+n+1,read);
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	dfs1(1),dfs2(1,1);
	Seg::build(1,1,n);
	while(m--){
		int u=read(),k=read();
		pathupdate(u,k);
		mat ret=query(1);
		cout<<max(ret.a[0][0],ret.a[0][1])<<'
';
	}
}

树哈希

这玩意从一棵树每个点出发都走一遍
瞎写写就可以了

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define bg begin
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readstring(char *s){
	int top=0;char ch=gc();
	while(isspace(ch))ch=gc();
	while(!isspace(ch))s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int mod=998244353,bas1=31231;
cs int M=1505,N=55;
int vis[M],pr[M],tot;
inline void init(){
	for(int i=2;i<=1500;i++){
		if(!vis[i])pr[++tot]=i;
		for(int j=1;j<=tot&&i*pr[j]<=1500;j++){
			vis[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
}
vector<int> has[N];
vector<int> e[N];
int n,m,rt,fa[N],tt,val[N];
void dfs1(int u,int fa){
	vector<int> son;
	val[u]=1;
	for(int &v:e[u]){
		if(v==fa)continue;
		dfs1(v,u);
		son.pb(val[v]);
	}
	sort(son.bg(),son.end());
	for(int i=0;i<son.size();i++){
		val[u]=(1ll*val[u]*pr[i+1]+1ll*son[i]*bas1)%mod;
	}
}
inline bool check(int a,int b){
	if(has[a].size()!=has[b].size())return false;
	for(int i=0;i<has[a].size();i++)
	if(has[a][i]!=has[b][i])return false;
	return true;
}
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	m=read();init();
	for(int i=1;i<=m;i++){
		n=read();rt=0;tt=i;
		for(int i=1;i<=n;i++){
			fa[i]=read();
			if(!fa[i])rt=i;
			else e[fa[i]].pb(i),e[i].pb(fa[i]);
		}
		for(int j=1;j<=n;j++)dfs1(j,0),has[i].pb(val[j]);
		for(int i=1;i<=n;i++)e[i].clear();
		sort(has[i].bg(),has[i].end());
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=i;j++){
			if(check(i,j)){cout<<j<<'
';break;}
		}
	}
}

后缀数组

注意用字符串 $fread$ 读入如果用 $isspace$ 要特判 $EOF$

记住 $sa2$ 的含义是第二维排名为 $i$ 的开头的位置

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define pb push_back
cs int RLEN=1<<20|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
inline int readstring(char *s){
	char ch=gc();int top=0;
	while(isspace(ch))ch=gc();
	while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();
	return top;
}
template<class tp>inline void chemx(tp &a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp &a,tp b){a>b?a=b:0;}
cs int N=1000005;
namespace Sa{
	int n,m,s[N],rk[N],sa[N],sa2[N],ht[N],buc[N];
	inline void buc_sort(){
		for(int i=1;i<=m;i++)buc[i]=0;
		for(int i=1;i<=n;i++)buc[rk[sa2[i]]]++;
		for(int i=1;i<=m;i++)buc[i]+=buc[i-1];
		for(int i=n;i>=1;i--)sa[buc[rk[sa2[i]]]--]=sa2[i];
	}
	inline void build(char *ss,int _n){
		n=_n,m=128;
		for(int i=1;i<=n;i++)s[i]=(int)ss[i],rk[i]=s[i],sa2[i]=i;
		buc_sort();
		for(int i=1,pos=0;i<=n&&pos<n;i<<=1){
			pos=0;
			for(int j=n-i+1;j<=n;j++)sa2[++pos]=j;
			for(int j=1;j<=n;j++)if(sa[j]>i)sa2[++pos]=sa[j]-i;
			buc_sort();
			swap(sa2,rk);
			rk[sa[1]]=1;pos=1;
			for(int j=2;j<=n;j++)
			rk[sa[j]]=(sa2[sa[j]]==sa2[sa[j-1]]&&sa2[sa[j]+i]==sa2[sa[j-1]+i])?pos:++pos;
			m=pos;
		}
		for(int i=1,j,k=0;i<=n;ht[rk[i++]]=k)
		for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
		for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
	}
}
int n;
char s[N];
int main(){
	#ifdef Stargazer
	freopen("lx.cpp","r",stdin);
	#endif
	n=readstring(s);
	Sa::build(s,n);
}

快速乘

inline ll mul(ll a,ll b,ll mod){
	return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;
}

【CSP-S 2019模板复习2】

可持久化平衡树

SAM

AC自动机

PamPamPam

DDPDDPDDP

树哈希

后缀数组

快速乘

$Pam$

$DDP$