模板合集

神奇的模板...总之各种各样的模板整理...已经准备用我现在的码风重新打一遍了...
高精度

已重载运算符.没写FFT什么的...
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int B = 10;
const int W = 1;

struct Big{
	vector s;
	void clear(){ s.clear(); }
	
	Big(LL num=0){ *this=num; }
	Big operator = (LL x){
		clear();
		do{ s.push_back(x%B),x/=B; }while(x);
		return *this;
	}
	Big operator = (const string &str){
		clear();
		int x,len=(str.length()-1)/W+1,l=str.length();
		for(int i=0;i> (istream & in,Big &a){
	string s;
	if(!(in>>s)) return in;
	a=s;return in;
}

ostream& operator << (ostream &out,const Big &a){
	cout<lb) return 0;
	for(int i=la-1;~i;i--){
		if(a.s[i]b.s[i]) return 0;
	}return 0;
}
bool operator <= (const Big &a,const Big &b){ return !(b (const Big &a,const Big &b){ return b= (const Big &a,const Big &b){ return !(ab) && !(ab || a=lim) break;
		x=g;if(i=0) g=0;else g=1,x+=B;
		c.s.push_back(x);
	}i=c.s.size()-1;
	while(c.s[i]==0 && i) c.s.pop_back(),i--;
	return c;
}
Big operator * (const Big &a,const Big &b){
	Big c;
	int i,j,la=a.s.size(),lb=b.s.size(),lc=la+lb;
	c.s.resize(lc,0);
	for(i=0;i>1;
			if(mid*b > f) r=mid-1;
			else l=mid+1;
		}
		f=f-r*b,c.s[i]=r;
//		while(f>=b) f=f-b,c.s[i]++;
	}i=la-1;while(c.s[i]==0 && i) c.s.pop_back(),i--;
	return c;
}
Big operator % (const Big &a,const Big &b){
	Big c=a-(a/b)*b;
	return c;
}
Big operator ^ (Big &a,Big &b){
	Big c=1;
	for(;b!=0;b=b/2,a=a*a){
		if(b.s[0] & 1) c=c*a;
	}return c;
}
Big operator += (Big &a,const Big &b){ return a=a+b; }
Big operator -= (Big &a,const Big &b){ return a=a-b; }
Big operator *= (Big &a,const Big &b){ return a=a*b; }
Big operator /= (Big &a,const Big &b){ return a=a/b; }
Big operator %= (Big &a,const Big &b){ return a=a%b; }
int main(){
	Big A,B;
	cin>>A>>B;
	cout<


FFT \(O(nlogn)\)


#include 
using namespace std;

#define mpr make_pair
#define rr first
#define ii second
const int N = 5e5+50;
const int M = 25;
const double Pi = M_PI;
typedef pair< double,double > Complex;

Complex operator + (const Complex &a,const Complex &b) {
	return mpr(a.rr+b.rr,a.ii+b.ii);
}
Complex operator - (const Complex &a,const Complex &b) {
	return mpr(a.rr-b.rr,a.ii-b.ii);
}
Complex operator * (const Complex &a,const Complex &b) {
	return mpr(a.rr*b.rr-a.ii*b.ii,a.rr*b.ii+a.ii*b.rr);
}

int n,m;
Complex a[N],b[N],c[N];
int ans[N],pow2[M];

void init(int x) {
	pow2[0]=1;
	for(int i=1;ij) swap(a[i],a[j]);
		for(int k=n>>1;(j^=k)>=1);
	}
}
void DFT(Complex y[],int r) {
	Rev(y);
	for(int i=2;i<=n;i<<=1) {
		Complex wi=mpr(cos(2.0*Pi/i),r*sin(2.0*Pi/i));
		for(int k=0;k>s1>>s2;
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	init((int)max(s1.length(),s2.length()));
	for(int i=0;i<(int)s1.length();i++) a[i]=mpr(s1[i]-'0',0);
	for(int i=0;i<(int)s2.length();i++) b[i]=mpr(s2[i]-'0',0);
	FFT(a,b,c);
	for(int i=0;i


FNT \(O(nlogn)\)


#include 
using namespace std;

typedef long long LL;
const int N = 5e5+50;
const int p = (479 << 21) + 1;
const int g = 3;

int n;
LL a[N],b[N],c[N];

LL Pow(LL a,LL b,LL r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
void init(int x) {
	for(n=1;nj) swap(a[i],a[j]);
		for(int k=n>>1;(j^=k)>=1);
	}
}
void FNT(LL y[],int r) {
	Rev(y);
	for(int i=2;i<=n;i<<=1) {
		LL wi=Pow(g,(p-1)/i);
		if(r==-1) wi=Pow(wi,p-2);
		for(int k=0;k>s1>>s2;
	reverse(s1.begin(),s1.end());reverse(s2.begin(),s2.end());
	for(int i=0;i0;p--);
	for(;~p;p--) printf("%d",c[p]);
	return 0;
}




优化

读入优化


char *ps=(char *)malloc(20000000);
inline LL in(LL x=0){ for(;*ps>'9'||*ps<'0';ps++);
    for(;*ps>='0'&&*ps<='9';ps++) x=(x<<3)+(x<<1)+*ps-'0';return x; }

fread(ps,1,20000000,stdin);


输出优化


inline void Out(LL x){
    int l=0;char ch[65];
    if(!x){ putchar('0');return; }
    if(x<0) putchar('-'),x=-x;
    while(x) ch[++l]=x%10+'0',x/=10;
    for(int i=l;i;i--) putchar(ch[i]);
}


计算几何

qwq


#include 
using namespace std;
 
namespace CG {
	typedef long double LD;
	 
	const LD Pi = M_PI;
	const LD PI = 2 * acos(0.0);
	const LD eps = 1e-18;
	const LD oo = 1e15;
	#define sqr(x) ((x)*(x))
	 
	int dcmp(LD x) { return fabs(x)<=eps?0:(x<0?-1:1); }
	 
	struct Point {
		LD x,y;
		Point(LD _x=0,LD _y=0) :x(_x),y(_y) {}
		void out() { cout<<"("<0; }
	};
	int cmpa(const Line &a,const Line &b) { return dcmp(a.ang-b.ang)==-1; }
	Point get_l_l(Line a,Line b) {
		Vector u=a.p-b.p;
		LD t=Cross(b.v,u)/Cross(a.v,b.v);
		return a.get_p(t);
	}
	typedef Line Hp;
	int get_h_h(vector &hs,vector &pt) {
		sort(hs.begin(),hs.end(),cmpa);
		vector p(hs.size());
		vector q(hs.size());
		int h,t;
		q[h=t=0]=hs[0];
		for(int i=1;i<(int)hs.size();i++) {
			while(h &res) {
		LD a=L.v.x,b=L.p.x-C.c.x,c=L.v.y,d=L.p.y-C.c.y;
		LD e=sqr(a)+sqr(c),f=2.0*(a*b+c*d),g=sqr(b)+sqr(d)-sqr(C.r);
		LD dt=f*f-4*e*g;
		if(dcmp(dt)<0) return 0;
		if(dcmp(dt)==0) return res.push_back(L.get_p(-f/(2.0*e))),1;
		LD x1=(-f-sqrt(dt))/(2.0*e),x2=(-f+sqrt(dt))/(2.0*e);
		if(x1>x2) swap(x1,x2);
		res.push_back(L.get_p(x1)),res.push_back(L.get_p(x2));return 2;
	}
	int get_c_c(Circle A,Circle B,vector &res) {
		LD d=get_l(A.c-B.c);
		if(dcmp(d)==0) return dcmp(A.r-B.r)==0?-1:0;
		if(dcmp(A.r+B.r-d)<0) return 0;
		if(dcmp(fabs(A.r-B.r)-d)>0) return 0;
		 
		LD a=get_a(B.c-A.c);
		LD rd=acos((sqr(A.r)+sqr(d)-sqr(B.r))/(2.0*A.r*d));
		 
		Point p1,p2;
		p1=A.get_p(a+rd),p2=A.get_p(a-rd);
		 
		res.push_back(p1);
		if(p1==p2) return 1;
		res.push_back(p2);
		return 2;
	}
	 
	/*---io---*/   
	ostream & operator << (ostream &os,const Point &p) { os<> (istream &is,Point &p) { is>>p.x>>p.y;return is; }
	ostream & operator << (ostream &os,const Circle &C) { os<> (istream &is,Circle &C) { is>>C.c>>C.r;return is; }
};
int main() {
	
}




图论

Tarjan-割点 \(O(m)\)


#include
#include
#include
using namespace std;

const int N = 100005;
#define debug(a) cout<<#a<<"="< g[N];
int b[N],out[N],du[N];
int dfsn[N],low[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void Tarjan(int u,int fa){
	dfsn[u]=low[u]=++cnt;int c=0;
	for(int i=0,v;i0&&dfsn[u]<=low[v]) b[u]=1;
		}else low[u]=min(low[u],dfsn[v]);
	}if(fa==0&&c>1) b[u]=1;
}
int main(){
	n=in(),m=in();
	for(int i=1,u,v;i<=m;i++) u=in(),v=in(),du[u]++,du[v]++,g[u].push_back(v),g[v].push_back(u);
	for(int i=1;i<=n;i++) if(!dfsn[i]) Tarjan(i,0);
	for(int i=1;i<=n;i++) if(b[i]) out[++ans]=i;
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d ",out[i]);putchar('\n');
	return 0;
}


Tarjan-割边(桥) \(O(m)\)


#include
#include
#include
using namespace std;

const int N = 100005;
#define mpr(a,b) make_pair(a,b)

int n,m,cnt,ans;
int iscut[N],e[N];
int dfsn[N],low[N];
struct Edge{ int fr,to,id; }edge[N];
vector g[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
inline void Add_Edge(int u,int v,int id){
	edge[id]=(Edge){ u,v,id };
	g[u].push_back((Edge){ u,v,id });
	g[v].push_back((Edge){ v,u,id });
}
void Tarjan(int u,int fa){
	dfsn[u]=low[u]=++cnt;
	for(int i=0,lim=g[u].size(),v;idfsn[u]) iscut[g[u][i].id]=1;
			low[u]=min(low[u],low[v]);
		}else low[u]=min(low[u],dfsn[v]);
	}
}
int main(){
	n=in(),m=in();
	for(int i=1,u,v;i<=m;i++) u=in(),v=in(),Add_Edge(u,v,i);
	for(int i=1;i<=n;i++) if(!dfsn[i]) Tarjan(i,0);
	for(int i=1;i<=m;i++) if(iscut[i]) e[++ans]=i;
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++) printf("%d\n",e[i]);
	return 0;
}



Tarjan-强连通分量+缩点. \(O(m)\)


#include
#include
#include
#include
using namespace std;
   
const int N = 10005;
#define debug(a) cout<<#a<<"="< g[N];
vector h[N];
stack stk;
struct Edge{ int fr,to; }edge[N*5];
   
inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void Tarjan(int u){
    dfsn[u]=low[u]=++cnt,ins[u]=1,stk.push(u);
    for(int i=0,lim=g[u].size(),v;i


LCA-倍增 \(O(nlogn+mlogn)\)


#include
#include
#include
#include
using namespace std;
 
#define mpr make_pair
#define debug(a) cout<<#a<<"="< pr;
const int N = 50005;
const int M = 31;
 
int n,m,k;
vector h[N];
int pow2[M],d[N];
int f[N][M],g[N][M];
 
inline int in(int x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void DFS(int u,int fa,int dep){
    d[u]=dep;
    for(int i=0,v;i


LCA-ST表 \(O(nlogn+m)\)


#include
#include
#include
#include
#include
#include
using namespace std;
 
#define debug(a) cout<<#a<<"="< pr;
const int N = 200005;
const int M = 25;
 
int n,m,cnt;
vector< pr > g[N];
int pow2[M],dfs[N],d[N],val[N],pos[N],lg2[N];
int f[N][M];
 
 
inline int in(int x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
void DFS(int u,int fa,int dep,int value){
    dfs[++m]=u,d[u]=dep,val[u]=value,pos[u]=m,f[m][0]=u;
    for(int i=0,v;i>1]+1;
    for(int j=1;j


网络流-ISAP  \(O(V^{2}E)\)


#include
#include
#include
#include
#include
using namespace std;

const int INF = 0x7fffffff;
const int N = 505;
const int M = 805;

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
struct NetWork{
	int n,m,s,t;
	struct Edge{ int fr,to,flow; }edge[M<<1];int cnte;
	vector g[N];int flow;
	int num[N],cur[N],d[N],p[N];bool v[N];


	void Add_Edge(int fr,int to,int fl){
		edge[cnte++]=(Edge){ fr,to,fl },edge[cnte++]=(Edge){ to,fr,0 };
		g[fr].push_back(cnte-2),g[to].push_back(cnte-1);
	}
	int Add_Flow(){
		int a=INF;
		for(int x=t;x!=s;x=edge[p[x]].fr) a=min(a,edge[p[x]].flow);
		for(int x=t;x!=s;x=edge[p[x]].fr) edge[p[x]].flow-=a,edge[p[x]^1].flow+=a;
		return a;
	}
	void BFS(){
		for(int i=1;i<=n;i++) d[i]=n;
		memset(v,0,sizeof(v));
		queue q;q.push(t),v[t]=1,d[t]=0;
		for(int x;!q.empty();){
			x=q.front(),q.pop();
			for(int i=0,lim=g[x].size();i


网络流-Dinic  \(O(VE^{2})\)/二分图\(O(\sqrt{V}E)\)


#include
#include
#include
#include
#include
using namespace std;

const int N = 505;
const int INF = 0x7fffffff;

int T,n,m,cnt,ans;
struct NetWork{
	int n,m,s,t,flow;
	struct Edge{ int fr,to,flow; };
	vector edge;vector g[N];
	int cur[N],d[N],p[N];
	
	void Add_Edge(int fr,int to,int flow){
		edge.push_back((Edge){ fr,to,flow });
		edge.push_back((Edge){ to,fr,0 });
		m=edge.size();
		g[fr].push_back(m-2),g[to].push_back(m-1);
	}
	int BFS(){
		memset(d,-1,sizeof(d));
		queue q;q.push(s),d[s]=0;
		for(int x;!q.empty();){
			x=q.front(),q.pop();
			for(int i=0,lim=g[x].size();i0&&d[x]+1==d[e.to]){
						p[k++]=g[x][i],x=e.to,ok=1;break;
					}
				}
				if(!ok){ if(!k) break;d[x]=-1,x=edge[p[--k]].fr; }
			}
		}return flow;
	}
}dinic;
int main(){ return 0; }



最小生成树计数Matrix-Tree定理 \(O(n^3)\)


#include
#include
#include
using namespace std;

const double eps = 1e-8;
const int N = 105;
#define _0(x) ((x>0?x:-x)+eps>0)

int n,m;
int g[N][N],d[N];
double a[N][N];

double det(int n){
	double res=1;int swpt=0;
	for(int i=0,j,k;i=n) return 0;
			for(k=i;k'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
int main(){
	for(int T=in();T--;){
		n=in(),m=in();memset(a,0,sizeof(a)),memset(g,0,sizeof(g)),memset(d,0,sizeof(d));
		for(int i=1,u,v;i<=m;i++) u=in()-1,v=in()-1,g[u][v]=g[v][u]=1,d[u]++,d[v]++;
		for(int i=0;i



曼哈顿最小生成树 \(O(n logn)\)


#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
#define mpr(a,b) make_pair(a,b)
const int N = 50005;
 
int n,ans;
struct seat{ int x,y,id; }a[N],b[N];
bool operator < (const seat &a,const seat &b){ return a.x==b.x?a.y>b.y:a.x>b.x; }
int d[N<<1],id[N<<1],cnt,ys[N];
struct Edge{ int u,v,w; };
bool operator < (const Edge &a,const Edge &b){ return a.w>b.w; }
priority_queue q;
int f[N];
 
inline int in(int x=0,char ch=getchar(),int v=1){
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();if(ch=='-') v=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*v; }
//int cmpx(const seat &a,const seat &b){ return a.x==b.x?a.xv) d[x]=v,id[x]=pos;
}
int Query(int x){
    int minv=0x7f7f7f7f,pos=-1;
    for(;x<=cnt;x+=x&-x) if(d[x]x0&&y1-x1>y0-x0     dis=(x1+y1)-(x0+y0)         */
    memset(d,0x7f,sizeof(d)),memset(id,-1,sizeof(id)),memset(ys,0,sizeof(ys));cnt=0;
    for(int i=1;i<=n;i++) b[i]=a[i];
//  for(int i=1;i<=n;i++) out(a[i]);
    sort(b+1,b+n+1);
//  for(int i=1;i<=n;i++) out(b[i]);
    for(int i=1;i<=n;i++) ys[i]=b[i].y-b[i].x;
    sort(ys+1,ys+n+1);
    cnt=unique(ys+1,ys+n+1)-ys-1;
     
//  cout<"<"<"<"<=n) break;
    }cout<



朱刘算法/最小树形图 \(O(nm)\)


#include 
using namespace std;
  
inline int in(int x=0,char ch=getchar()) { while(ch>'9' || ch<'0') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }
  
const int N = 55;
const int M = N*N+50;
  
struct Edge { int fr,to;double v; };
Edge edge[M];
  
int n,m,rt;
int b[N];
double mic[N];
double miv[N];
int pre[N],vis[N],id[N];
  
void AddEdge(int fr,int to,double v) { edge[++m]=(Edge){ fr,to,v }; }
  
double Solve(int n) {
    double res=0;
    for(int cnt,tmp;;) {
        for(int i=1;i<=n;i++) miv[i]=1e9,pre[i]=0;
        for(int i=1;i<=m;i++) {
            Edge &e=edge[i];
            if(e.v




数学

快速幂 \(O(logn)\) 快速乘 \(O(1)\)


inline LL Mul(LL a,LL b,LL p){
    if(p<=1000000000) return a*b%p;
    return (a*b-(LL)(a/(long double)p*b+1e-3)*p+p)%p;
//  for(;b;b>>=1,a=(a+a)%p) if(b&1) res=(res+a)%p;return res;
}
inline LL Pow(LL a,LL b,LL p,LL res=1){ for(;b;b>>=1,a=Mul(a,a,p)) if(b&1) res=Mul(res,a,p);return res; }




\(\varphi(n)\) \(O(\sqrt{n})\)



inline LL GetPhi(LL p){
    LL res=p,m=sqrt(p)+0.5;
    for(int i=2;i<=m;i++) if(p%i==0){
        res=res/i*(i-1);
        while(p%i==0) p/=i;
    }
    if(p>1) res=res/p*(p-1);return res;
}


线性筛 \(\mu\) \(O(n)\)


#include
#include
#include
using namespace std;

const int N = 1000005;

int mu[N],pr[N],cnt;
bool b[N];
void Pre(){
	mu[1]=1;
	for(int i=2;i<=N;i++){
		if(!b[i]) mu[i]=-1,pr[++cnt]=i;
		for(int j=1;j<=cnt&&pr[j]*i<=N;j++){
			b[i*pr[j]]=1;
			if(i%pr[j]) mu[i*pr[j]]=-mu[i];
			else break;
		}
	}
//	for(int i=1;i<=10;i++) cout<


矩阵乘法和矩阵快速幂 \(O(n^3) O(n^3 logn)\)


#include
#include
#include
using namespace std;

typedef long long LL;
typedef vector Vec;
typedef vector Mat;
const LL p = 10000000007LL;

Mat operator * (const Mat &A,const Mat &B){
    Mat C(A.size(),Vec(B[0].size()));
    for(int i=0;i>=1,A=A*A) if(b&1) res=res*A;
    return res;
}
int main(){ return 0; }



扩展欧几里得 \(O(logn)\)


LL Exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){ x=1,y=0;return a; }
	LL r=Exgcd(b,a%b,x,y);LL t=x;
	x=y,y=t-(a/b)*y;return r;
}



中国剩余定理 \(O(nlogn)\)


#include
#include
using namespace std;

typedef long long LL;
const int N = 1005;

int n;
LL m[N],a[N];

LL Exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){ x=1,y=0;return a; }
	LL r=Exgcd(b,a%b,x,y);LL t=x;
	x=y,y=t-(a/b)*y;return r;
}
LL Solve(){
	LL M=m[1],MM,res=0,x,y;
	for(int i=2;i<=n;i++) M*=m[i];
	for(int i=1;i<=n;i++){
		MM=M/m[i];
		Exgcd(MM,m[i],x,y);
		res=(res+MM*x*a[i])%M;
	}return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>m[i]>>a[i];
	Solve();
	return 0;
}


求解模线性方程组 \(O(nlogn)\)


#include
#include
#include
#include
using namespace std;

typedef long long LL;
#define mpr make_pair
const int N = 1005;

LL n,a1,a2,b1,b2;
pair< LL,LL > m[N];

inline LL in(LL x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
	while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
LL Exgcd(LL a,LL b,LL &x,LL &y){
	if(!b){ x=1,y=0;return a; }
	LL r=Exgcd(b,a%b,x,y);LL t=x;
	x=y,y=t-(a/b)*y;return r;
}
int Solve(){
	LL x,y,d=Exgcd(a1,a2,x,y);
	if((b2-b1)%d) return 0;
	Exgcd(a1/d,a2/d,x,y),x*=(b2-b1)/d,x=(x%(a2/d)+a2/d)%(a2/d);
	b1=a1*x+b1,a1=a1/d*a2,b1=(b1%a1+a1)%a1;
	return 1;
}
int main(){
	n=in();
	for(LL i=1,u,v;i<=n;i++) u=in(),v=in(),m[i]=mpr(u,v);
	a1=m[1].first,b1=m[1].second;
	for(int i=2;i<=n;i++){
		a2=m[i].first,b2=m[i].second;
		if(!Solve()) return puts("-1"),0;
	}return printf("%lld\n",b1),0;
}



字符串

后缀数组 \(O(nlogn)\)


#include 
using namespace std;

const int N = 200050;

int n,m=26;
char s[N];
int a[N];

namespace SuffixArray {
	int s1[N],s2[N],sa[N],rk[N],ht[N],c[N];
	
	void get_sa(int a[],int n=::n,int m=::m) {
		int *x=s1,*y=s2;
		for(int i=1;i<=n;i++) c[x[i]=a[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i;--i) sa[c[a[i]]--]=i;
		for(int k=1,p=0;kk) y[++p]=sa[i]-k;
			for(int i=0;i<=m;i++) c[i]=0;
			for(int i=1;i<=n;i++) c[x[i]]++;
			for(int i=1;i<=m;i++) c[i]+=c[i-1];
			for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i];
			swap(x,y);x[sa[1]]=p=1;
			for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && 
				y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
			if(p>=n) break;
			m=p;
		}
	}
	void get_ht(int a[],int n=::n) {
		for(int i=1;i<=n;i++) rk[sa[i]]=i;
		for(int i=1,k=0,j;i<=n;ht[rk[i++]]=k)
			for(j=sa[rk[i]-1],k=k?k-1:k;a[i+k]==a[j+k];k++);
	}
}

int main() {
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
	using namespace SuffixArray;
	get_sa(a);get_ht(a);
	for(int i=1;i<=n;i++) printf("%d%c",sa[i]," \n"[i==n]);
//	for(int i=1;i<=n;i++) cout<




Manacher \(O(n)\) 寻找最长回文串


#include
#include
#include

using namespace std;

const int N = 1000005;


int p[N];
char s[N];
char ch[N];

int Manacher(char s[]){
	int l=strlen(s+1),mx=0,res=0,id=0;
	
//	cout<i) p[i]=min(p[id*2-i],mx-i);
		else p[i]=1;
		while(s[i+p[i]]==s[i-p[i]]) p[i]++;
		if(mx>(s+1);ch[0]='$';ch[1]='#';
	for(int i=1;i<=strlen(s+1);i++) ch[i*2]=s[i],ch[i*2+1]='#';
//	cout<<(ch+1)<


后缀自动机(SAM) \(O(n)\)


#include
#include
#include
using namespace std;

const int N = 250005;

struct State{
	State *par,*go[26];
	int val;
	State(int _val):par(0),val(_val){ memset(go,0,sizeof(go)); }
}*rt,*lst;
void extend(int w){
	State *p=lst,*np=new State(p->val+1);
	while(p && p->go[w]==0) p->go[w]=np,p=p->par;
	if(!p) np->par=rt;
	else{
		State *q=p->go[w];
		if(q->val == p->val+1) np->par=q;
		else{
			State *nq=new State(p->val+1);
			memcpy(nq->go,q->go,sizeof(q->go));
			nq->par=q->par;
			np->par=q->par=nq;
			while(p && p->go[w]==q) p->go[w]=nq,p=p->par;
		}
	}lst=np;
}

int main(){ rt=new State(0),lst=rt; }



数据结构

Treap \(O(n\log n)\)


#include 
using namespace std;

#define debug(a) cout<<(#a)<<"="<=(int)k;i--)

typedef long long ll;
typedef pair pr;
typedef vector vi;
typedef vector vl;
typedef vector vs;
const int N = 100050;
const int M = 25;
const int oo = 0x3fffffff;
const ll  OO = 1e18;

const ll p = 1000000007;
ll Pow(ll a,ll b,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
ll Pow(ll a,ll b,ll p,ll r=1) { for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r; }
ll inv(ll x) { return Pow(x,p-2); }
void Add(ll &x,ll y) { x=(x+y%p)%p; }
void Sub(ll &x,ll y) { x=(x-y%p+p)%p; }
void Mul(ll &x,ll y) { x=x*(y%p)%p; }
int chkmax(ll &x,ll y) { return xy?x=y,1:0; }

inline ll in(ll x=0,char ch=getchar(),int v=1) {
	while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*v;
}
/*end*/

namespace Treap {
	int cp,rt;
	
	int sz[N],ss[N],ch[N][2],f[N],rv[N];
	int val[N];
	
	int Newnode(int v) {
		++cp,ss[cp]=sz[cp]=1,f[cp]=lc(cp)=rc(cp)=0,val[cp]=v,rv[cp]=rand();
		return cp;
	}
	void init() { rt=0,rv[0]=-oo; }
	void Update(int o) { sz[o]=sz[lc(o)]+sz[rc(o)]+ss[o]; }
	void Rot(int &o,int d) {
		int t=ch[o][d];ch[o][d]=ch[t][d^1],ch[t][d^1]=o,Update(o),Update(t),o=t;
	}
	void insert(int &o,int v) {
		if(!o) { o=Newnode(v);return; }
		if(val[o]==v) { ss[o]++,Update(o);return; }
		int d=v>val[o];
		insert(ch[o][d],v);
		if(rv[ch[o][d]]>rv[o]) Rot(o,d);
		else Update(o);
	}
	void earse(int &o,int v) {
		if(val[o]==v) {
			if(ss[o]>1) { ss[o]--,Update(o);return; }
			int d=rv[lc(o)]val[o]],v);
		Update(o);
	}
	int rk(int o,int v) {
		if(val[o]v) return rk(lc(o),v);
		else return sz[lc(o)];
	}
	int kth(int o,int k) {
		if(sz[lc(o)]>=k) return kth(lc(o),k);
		else if(sz[lc(o)]+ss[o]=v) return pre(lc(o),v);
		else return max(val[o],pre(rc(o),v));
	}
	int nxt(int o,int v) {
		if(!o) return oo;
		if(val[o]<=v) return nxt(rc(o),v);
		else return min(val[o],nxt(lc(o),v));
	}
	void insert(int v) { insert(rt,v); }
	void earse(int v) { earse(rt,v); }
	int rk(int v) { return rk(rt,v); }
	int kth(int k) { return kth(rt,k); }
	int pre(int v) { return pre(rt,v); }
	int nxt(int v) { return nxt(rt,v); }
};

int main() {
	Treap::init();
	for(int T=in();T--;) {
		int opt=in(),x=in();
		switch(opt) {
			case 1:Treap::insert(x);break;
			case 2:Treap::earse(x);break;
			case 3:printf("%d\n",Treap::rk(x)+1);break;
			case 4:printf("%d\n",Treap::kth(x));break;
			case 5:printf("%d\n",Treap::pre(x));break;
			case 6:printf("%d\n",Treap::nxt(x));break;
		}
	}
	return 0;
}




Splay \(O(n\log n)\)


#include 
using namespace std;

typedef long long LL;
const int N = 200050;

inline LL in(LL x=0,char ch=getchar(),int v=1) {
	while(ch>'9' || ch<'0') v=ch=='-'?-1:v,ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*v;
}

int n,q,nw;
LL a[N];

struct SplayTree {
	#define lc(o) ch[o][0]
	#define rc(o) ch[o][1]
	#define mid ((l+r)>>1)
	
	int cp,rt;
	LL sum[N],v[N],d[N],rev[N],sz[N],f[N],ch[N][2];
	
	int NewNode() {
		++cp;
		sum[cp]=v[cp]=d[cp]=rev[cp]=lc(cp)=rc(cp)=0;
		sz[cp]=1;
		return cp;
	}
	void Update(int o) {
		if(!o) return; 
		sz[o]=sz[lc(o)]+sz[rc(o)]+1;
		sum[o]=sum[lc(o)]+sum[rc(o)]+v[o]+d[o]*sz[o];
	}
	void Push(int o) {
		if(!o) return;
		Push(f[o]);
		if(rev[o]) {
			swap(lc(o),rc(o));
			if(lc(o)) rev[lc(o)]^=1;
			if(rc(o)) rev[rc(o)]^=1;
			rev[o]=0;
		}
		if(d[o]) {
			if(lc(o)) d[lc(o)]+=d[o];
			if(rc(o)) d[rc(o)]+=d[o];
			v[o]+=d[o],d[o]=0;
		}Update(lc(o)),Update(rc(o)),Update(o);
	}
	void Pushdown(int o) {
		if(!o) return;
		if(rev[o]) {
			swap(lc(o),rc(o));
			if(lc(o)) rev[lc(o)]^=1;
			if(rc(o)) rev[rc(o)]^=1;
			rev[o]=0;
		}
		if(d[o]) {
			if(lc(o)) d[lc(o)]+=d[o];
			if(rc(o)) d[rc(o)]+=d[o];
			v[o]+=d[o],d[o]=0;
		}Update(lc(o)),Update(rc(o)),Update(o);
	}
	int Build(int l,int r) {
		if(l>r){ return 0; }
		int o=NewNode();
		lc(o)=Build(l,mid-1);
		v[o]=a[nw++];
		rc(o)=Build(mid+1,r);
		if(lc(o)) f[lc(o)]=o;
		if(rc(o)) f[rc(o)]=o;
		Update(o);
		return o;
	}
	void Build(int n) {
		rt=Build(1,n+2);
	}
	void Rot(int o) {
		int p=f[o],k=f[p],r=rc(p)==o;
//		Pushdown(k),Pushdown(p),Pushdown(o);
		if(k) ch[k][rc(k)==p]=o;
		f[p]=o,f[ch[o][r^1]]=p,f[o]=k;
		ch[p][r]=ch[o][r^1],ch[o][r^1]=p;
		Update(p),Update(o),Update(k);
	}
	void Splay(int o,int ff) {
		Push(o);
		for(;f[o]!=ff;) {
			int p=f[o],k=f[p];
			if(k!=ff) Rot((rc(k)==p)==(rc(p)==o)?p:o);
			Rot(o);
		}
		Update(o);
		if(!ff) rt=o;
	}
	int Kth(int o,int k) {
		Pushdown(o);
		if(sz[lc(o)]>=k) return Kth(lc(o),k);
		else if(sz[lc(o)]+1==k) return o;
		else return Kth(rc(o),k-sz[lc(o)]-1); 
	}
	LL Kthw(int o,int k) {
		Pushdown(o);
		if(sz[lc(o)]>=k) return Kthw(lc(o),k)+d[o];
		else if(sz[lc(o)]+1==k) return v[o]+d[o];
		else return Kthw(rc(o),k-sz[lc(o)]-1)+d[o]; 
	}
	LL Kthw(int k) { return Kthw(rt,k+1); }
	void Add(int l,int r,LL w) {
		l++,r++;
		int L=Kth(rt,l-1),R=Kth(rt,r+1);
		Splay(L,0),Splay(R,L);
		d[lc(R)]+=w;
		Update(lc(R)),Update(R),Update(L);
	}
	void Insert(int x,LL w) {
		x++;
		int L=Kth(rt,x),R=Kth(rt,x+1);
		Splay(L,0),Splay(R,L);
		int np=NewNode();lc(R)=np,v[np]=w,f[np]=R;
		Update(np),Update(R),Update(L);
	}
	void Del(int l,int r) {
		l++,r++;
		int L=Kth(rt,l-1),R=Kth(rt,r+1);
		Splay(L,0),Splay(R,L);
		lc(R)=0,Update(R),Update(L);
	}
	LL Qur(int l,int r) {
		l++,r++;
		int L=Kth(rt,l-1),R=Kth(rt,r+1);
		Splay(L,0),Splay(R,L);
		return sum[lc(R)];
	}
	void Rev(int l,int r) {
		l++,r++;
		int L=Kth(rt,l-1),R=Kth(rt,r+1);
		Splay(L,0),Splay(R,L);
		rev[lc(R)]^=1;
	}
}py;

int main() {
	n=in();
	for(int i=1;i<=n;i++) a[i]=in();
	py.Build(n);
	char opt[20];
	int l,r,k,x,v;
	for(q=in();q--;) {
		scanf("%s",opt);
		if(opt[0]=='A') l=in(),r=in(),v=in(),py.Add(l,r,v);
		if(opt[0]=='I') x=in(),v=in(),py.Insert(x,v);
		if(opt[0]=='D')	l=in(),r=in(),py.Del(l,r);
		if(opt[0]=='Q') l=in(),r=in(),printf("%lld\n",py.Qur(l,r));
		if(opt[0]=='K') k=in(),printf("%lld\n",py.Kthw(k));
		if(opt[0]=='R')	l=in(),r=in(),py.Rev(l,r);
	}
	return 0;
}
模板
相关

题解 Count on a tree II/【模板】树分块

二分查找模板（准确找定值）

beautiful 模板

javascript模板字符串（反引号）

并查集模板

一个极短，极好记，常数小的行列式求值模板——qyy 行列式

设计模式之模板方法模式

模板

splay模板指针版&splay被卡祭

考前复习打打模板

Django模板层

excel批量按模板打印 vba经典
标签