模板

对拍程序

while true; do
	./makedata > test.in
	./A < test.in > A.out
	./B < test.in > B.out
	if diff A.out B.out; then
		printf AC
	else
		echo WA
		exit 0
	fi
done

Vim简要配置

set tabstop=4
set softtabstop=4
set shiftwidth=4
syntax on
set nu
set ruler
set autoindent
set cindent
set smartindent
set scrolloff=5

noremap <F9> :call R()<CR>
noremap <F8> :call G()<CR>

func! R()
	exe "w"
	exe "!g++ % -std=c++14 -g -Wall -o %<"
	exe "!./%<"
endfunc

func! G()
	exe "!g++ % -std=c++14 -g -Wall -o %<"
	exe "!gdb %<"
endfunc

func! s:ADB() abort
	call append(line("'>"),'}')
	call append(line("'<")-1,'{')
endfunc

inoremap {<CR> {<CR>}<ESC>O
vnoremap {  :<C-u>call <sid>ADB()<CR>gvokoj=k$

树链剖分:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL MAX=~0ULL;
const int maxn=1e5+10;

struct HLD // Heavy_Light_Decomposition
{
	struct Segment_Tree
	{
		LL sum[maxn<<2];
		LL tag_inc[maxn<<2];
		LL tag_mul[maxn<<2];
		int n;

		#define ls (o<<1)
		#define rs ((o<<1)|1)
		#define mid ((l+r)>>1)

		void Mark_Inc(int o,int l,int r,LL t_inc)
		{
			sum[o]+=(LL)(r-l+1)*t_inc;
			tag_inc[o]+=t_inc;
		}

		void Mark_Mul(int o,int l,int r,LL t_mul)
		{
			sum[o]*=t_mul;
			tag_mul[o]*=t_mul;
			tag_inc[o]*=t_mul;
		}

		void Push_Down(int o,int l,int r)
		{
			if (tag_mul[o]!=1ULL)
			{
				Mark_Mul(ls,l,mid,tag_mul[o]);
				Mark_Mul(rs,mid+1,r,tag_mul[o]);
				tag_mul[o]=1ULL;
			}
			if (tag_inc[o])
			{
				Mark_Inc(ls,l,mid,tag_inc[o]);
				Mark_Inc(rs,mid+1,r,tag_inc[o]);
				tag_inc[o]=0ULL;
			}
		}

		void Update(int o)
		{
			sum[o]=sum[ls]+sum[rs];
		}

		void Change(int o,int l,int r,int a,int b,LL t_inc,LL t_mul)
		{
			if (a<=l && r<=b)
			{
				Mark_Mul(o,l,r,t_mul);
				Mark_Inc(o,l,r,t_inc);
				return;
			}
			Push_Down(o,l,r);
			if (a<=mid) Change(ls,l,mid,a,b,t_inc,t_mul);
			if (b> mid) Change(rs,mid+1,r,a,b,t_inc,t_mul);
			Update(o);
		}

		LL Query(int o,int l,int r,int a,int b)
		{
			if (a<=l && r<=b)
				return sum[o];
			Push_Down(o,l,r);
			LL res=0ULL;
			if (a<=mid) res+=Query(ls,l,mid,a,b);
			if (b> mid) res+=Query(rs,mid+1,r,a,b);
			Update(o);
			return res;
		}

		void Build_Tree(int o,int l,int r)
		{
			tag_inc[o]=0ULL;
			tag_mul[o]=1ULL;
			sum[o]=0ULL;
			if (l==r) return;
			Build_Tree(ls,l,mid);
			Build_Tree(rs,mid+1,r);
		}

		#undef ls
		#undef rs
		#undef mid

		void Init(int _n) {n=_n;Build_Tree(1,1,n);}
		void Change(int x,int y,LL t_inc,LL t_mul) {Change(1,1,n,x,y,t_inc,t_mul);}
		LL Query(int x,int y) {return Query(1,1,n,x,y);}
	}ST;

	int wson[maxn];
	int sons[maxn];
	int top[maxn];
	int dep[maxn];
	int fa[maxn];
	int dfq[maxn],order[maxn],Index;
	int *head,*nxt,*E;
	int n;

	void DFS(int x,int father,int depth)
	{
		dep[x]=depth;
		fa[x]=father;
		sons[x]=1;
		for (int i=head[x];i;i=nxt[i]) if (E[i]!=father)
		{
			DFS(E[i],x,depth+1),sons[x]+=sons[E[i]];
			if (sons[wson[x]]<sons[E[i]]) wson[x]=E[i];
		}
	}

	void DFS2(int x,int father,int is_wson)
	{
		top[x]=(is_wson)?top[father]:x;
		dfq[++Index]=x;
		order[x]=Index;
		if (wson[x]) DFS2(wson[x],x,1);
		for (int i=head[x];i;i=nxt[i]) if (E[i]!=father && E[i]!=wson[x])
			DFS2(E[i],x,0);
	}

	void Build_HLD(int _n,int *_head,int *_nxt,int *_E)
	{
		n=_n,head=_head,nxt=_nxt,E=_E;
		Index=0;
		memset(wson,0,(n+1)*sizeof(int));
		DFS(1,0,1);
		DFS2(1,0,0);
		ST.Init(n);
	}

	LL Query(int x,int y)
	{
		LL res=0ULL;
		while (top[x]!=top[y])
			(dep[top[x]]>dep[top[y]]) ? (res+=ST.Query(order[top[x]],order[x]),x=fa[top[x]])
									  : (res+=ST.Query(order[top[y]],order[y]),y=fa[top[y]]);
		if (order[x]>order[y]) swap(x,y);
		res+=ST.Query(order[x],order[y]);
		return res;
	}

	void Change(int x,int y,LL t_inc,LL t_mul)
	{
		while (top[x]!=top[y])
			(dep[top[x]]>dep[top[y]]) ? (ST.Change(order[top[x]],order[x],t_inc,t_mul),x=fa[top[x]])
									  : (ST.Change(order[top[y]],order[y],t_inc,t_mul),y=fa[top[y]]);
		if (order[x]>order[y]) swap(x,y);
		ST.Change(order[x],order[y],t_inc,t_mul);
	}

	void Change_Inc(int x,int y,LL t_inc) {Change(x,y,t_inc,1ULL);}
	void Change_Mul(int x,int y,LL t_mul) {Change(x,y,0ULL,t_mul);}
	void Change_Not(int x,int y) {Change(x,y,MAX,MAX);}
}T;

int head[maxn],nxt[maxn],E[maxn],Ecnt;
int n,m;

void Add_Edge(int x,int y) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		memset(head,0,sizeof(head));
		Ecnt=0;
		for(int i=2,x;i<=n;i++)
			scanf("%d",&x),Add_Edge(x,i);
		T.Build_HLD(n,head,nxt,E);
		scanf("%d",&m);
		while(m--)
		{
			int op,u,v;
			LL x;
			scanf("%d",&op);
			if(op==1)
				scanf("%d%d%llu",&u,&v,&x),
				T.Change_Mul(u,v,x);
			if(op==2)
			{
				scanf("%d%d%llu",&u,&v,&x);
				T.Change_Inc(u,v,x);
			}
			if(op==3)
				scanf("%d%d",&u,&v),
				T.Change_Not(u,v);
			if(op==4)
				scanf("%d%d",&u,&v),
				printf("%llu\n",T.Query(u,v));
		}
	}
	return 0;
}

网络流ISAP

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10,inf=~0U>>1;

int head[maxn],nxt[maxm<<1],E[maxm<<1],F[maxm<<1],Ecnt;
int h[maxn],cur[maxn],gap[maxn];
int n,m,S,T;

void Add_Edge(int x,int y,int c)
{
	nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;
	nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=c;
}

int DFS(int v,int flow)
{
	if (v==T) return flow;
	int rest=flow;
	for (int &i=cur[v];i;i=nxt[i]) if (h[v]==h[E[i]]+1 && F[i^1])
	{
		int ret=DFS(E[i],min(rest,F[i^1]));
		F[i]+=ret,F[i^1]-=ret,rest-=ret;
		if (rest==0) return flow;
	}
	if (--gap[h[v]] == 0) h[S]=n;
	gap[++h[v]]++;
	cur[v]=head[v];
	return flow-rest;
}

int ISAP()
{
	int ans=0;
	for (int i=1;i<=n;i++) h[i]=0,gap[i]=0,cur[i]=head[i];
	gap[0]=n;
	while (h[S]<n)
		ans+=DFS(S,inf);
	return ans;
}

int main()
{
	while (scanf("%d%d",&m,&n)!=EOF)
	{
		Ecnt=1;
		for (int i=1;i<=n;i++) head[i]=0;
		for (int i=1,x,y,c;i<=m;i++) scanf("%d%d%d",&x,&y,&c),Add_Edge(x,y,c);
		S=1,T=n;
		printf("%d\n",ISAP());
	}
}

有向图最小生成树

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10,maxm=3e5+10,inf=~0U>>1;

struct Edge
{
	int v,c;
	Edge(int _v=0,int _c=0):v(_v),c(_c){};
	bool operator< (const Edge &b) const {if (c==b.c) return v<b.v;return c<b.c;}
};

set<Edge> ME[maxn],*E[maxn];
stack<int> Q;
int gv[maxn];
int Instack[maxn];
int fa[maxn];
long long ans;
int n,m;

int F(int x) {return (fa[x]==x)?x:fa[x]=F(fa[x]);}
void Union(int x,int y)
{
	x=F(x),y=F(y);
	if (E[x]->size()<E[y]->size()) swap(E[x],E[y]),swap(gv[x],gv[y]);
	for (auto e=E[y]->begin();e!=E[y]->end();++e) if (F(e->v)!=x && F(e->v)!=y)
		E[x]->insert(Edge(F(e->v),e->c-gv[y]+gv[x]));
	E[y]->clear();
	fa[y]=x;
}

int main()
{
	//freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) E[i]=&ME[i];
	for (int i=1,x,y,c;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		ME[y].insert(Edge(x,c));
	}
	for (int i=1;i<=n;i++) fa[i]=i,gv[i]=0;
	for (int i=2;i<=n;i++) if (F(i)!=F(1))
	{
		Q.push(F(i));
		Instack[F(i)]=1;
		while (true)
		{
			int x=F(Q.top());
			while (!E[x]->empty() && F(E[x]->begin()->v)==F(x)) E[x]->erase(E[x]->begin());
			if (E[x]->empty()) {while (!Q.empty()) Instack[Q.top()]=0,Q.pop();break;}
			int mincost=E[x]->begin()->c,nextNode=F(E[x]->begin()->v);
			ans+=mincost-gv[x];
			gv[x]=mincost;
			if (F(nextNode)==F(1))
			{
				while (!Q.empty())
				{
					Instack[F(Q.top())]=0;
					E[F(Q.top())]->clear();
					Union(1,Q.top());
					Q.pop();
				}
				break;
			}
			else if (Instack[F(nextNode)])
			{
				while (F(Q.top())!=F(nextNode))
				{
					Instack[F(Q.top())]=0;
					Union(nextNode,Q.top());
					Q.pop();
				}
			}
			else 
			{
				Q.push(nextNode);
				Instack[nextNode]=1;
			}
		}
	}
	for (int i=1;i<=n;i++) if (F(i)!=F(1))
		return printf("NO\n"),0;
	printf("YES\n%lld\n",ans);
	return 0;
}

FWT(临时)

void FWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)  
        for(int m=d<<1,i=0;i<n;i+=m)  
            for(int j=0;j<d;j++)  
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;  
                //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;  
                //and:a[i+j]=x+y;  
                //or:a[i+j+d]=x+y;  
            }  
}  

void UFWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)  
        for(int m=d<<1,i=0;i<n;i+=m)  
            for(int j=0;j<d;j++)  
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod; 
                //rev表示2在模mod下的逆元 
                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;  
                //and:a[i+j]=x-y;  
                //or:a[i+j+d]=y-x;  
            }  
}  
void solve(int a[],int b[],int n)  
{  
    FWT(a,n);  
    FWT(b,n);  
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;  
    UFWT(a,n);  
}  

FWT(Xor)

void trans(int *a,int n) {
	for (int i = 1; i < n; i << = 1)
	for (int j = 0; j < n; j += (i << 1) )
	for (int k = 0; k < i; ++k)
	{
		long long x = a[j + k], y = a[j + k + i];
		a[j + k] = (x +  y) % P;
		a[j + k + i] = (x - y + P) % P;
	}
}

void trans(int *a,int n) {
	for (int i = 1; i < n; i *= 3)
	for (int j = 0; j < n; j += i * 3)
	for (int k = 0; k < i; ++k)
	{
		long long x = a[j + k], y = a[j + k + i], z = a[j + k + i + i];
		a[j + k] = (x +  y + z) % P;
		a[j + k + i] = (x + W1 * y + W2 * z) % P;
		a[j + k + i + i] = (x + W2 * y + W1 * z) % P;
	}
}
// W1 = g^((P - 1) / 3), W2 = g^((P -1) / 3 * 2)

任意模数FFT

const int maxn = 262144 + 10, M = 32767, mo = 1e9 + 7;
const double pi = acos(-1.0);
typedef long long LL;

struct Complex {
	double r, i;
	Complex (double _r = 0, double _i = 0) : r(_r), i(_i) {}
	Complex operator * (const Complex &a) const {return Complex(r * a.r - i * a.i, r * a.i + i * a.r);}
	Complex operator + (const Complex &a) const {return Complex(r + a.r, i + a.i);}
	Complex operator - (const Complex &a) const {return Complex(r - a.r, i - a.i);}
	void operator += (const Complex &a) {r += a.r; i += a.i;}
	void operator -= (const Complex &a) {r -= a.r; i -= a.i;}
	Complex conj() const {return Complex(r, -i);}
};

void FFT(Complex *arr, int N, int *rev, Complex *w) {
	for (int i = 0; i < N; ++i) if (i < rev[i]) swap(arr[i], arr[rev[i]]);
	for (int i = 1, wn = N >> 1; i < N; i <<= 1, wn >>= 1)
	for (int j = 0; j < N; j += (i<<1))
	for (int k = 0, wp = 0; k < i; ++k, wp += wn)
	{
		Complex tmp = w[wp] * arr[i + j + k];
		arr[i + j + k] = arr[j + k] - tmp; arr[j + k] += tmp;
	}
}

void Mul(int *A, int *B, int *C, int n, int m)
{
	static Complex a[maxn], b[maxn], Da[maxn], Db[maxn], Dc[maxn], Dd[maxn], w[maxn];
	static int N, rev[maxn];
	if (n <= 50 || m <= 50)
	{
		for (int i = 0; i < n + m - 1; ++i) C[i]=0;
		for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			(C[i + j] += (LL)A[i] * B[j] % mo) %= mo;
		return;
	}
	N = 1; while (N <= n + m - 1) N <<= 1;
	for (int i = 0; i < N; ++i) w[i] = Complex(cos(2 * pi / N * i), sin(2 * pi / N * i));
	for (int i = 1; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N >> 1));
	for (int i = 0; i < n; ++i) a[i] = Complex(A[i] & M, A[i] >> 15);
	for (int i = n; i < N; ++i) a[i] = Complex(0, 0);
	for (int i = 0; i < m; ++i) b[i] = Complex(B[i] & M, B[i] >> 15);
	for (int i = m; i < N; ++i) b[i] = Complex(0, 0);
	FFT(a, N, rev, w); FFT(b, N, rev, w);
	for (int i = 0; i < N; ++i)
	{
		int j = (i==0) ? 0 : (N - i);
		Complex da, db, dc, dd;
		da = (a[i] + a[j].conj()) * Complex(0.5, 0);
		db = (a[i] - a[j].conj()) * Complex(0, -0.5);
		dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
		dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
		Da[j] = da * dc; Db[j] = da * dd; Dc[j] = db * dc; Dd[j] = db * dd;
	}
	for (int i = 0; i < N; ++i) a[i] = Da[i] + Db[i] * Complex(0, 1);
	for (int i = 0; i < N; ++i) b[i] = Dc[i] + Dd[i] * Complex(0, 1);
	FFT(a, N, rev, w); FFT(b, N, rev, w);
	for (int i = 0; i < N; ++i) {
		int da = (LL) (a[i].r / N + 0.5) % mo;
		int db = (LL) (a[i].i / N + 0.5) % mo;
		int dc = (LL) (b[i].r / N + 0.5) % mo;
		int dd = (LL) (b[i].i / N + 0.5) % mo;
		C[i] = (da + ((LL)(db + dc) << 15) + ((LL)dd << 30)) % mo; 
	}
}

多项式乘法、除法、取模、多点求值

typedef long long LL;
const int maxn = 262144 + 10, mo = 998244353, g = 3;

long long Pow(long long x,int p)
{
	long long res = 1;
	while (p)
	{
		if (p & 1)  (res *= x) %= mo;
		(x *= x) %= mo;
		p >>= 1;
	}
	return res;
}

long long inv(long long x)
{
	return Pow(x, mo - 2);
}

inline void FFT(int *arr, int N)
{
	static int N0 = 0, rev[maxn];
	if (N != N0)
	{
		for (int i = 1; i < N; ++i)
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N >> 1));
		N0 = N;
	}
	for (int i = 0; i < N; ++i) if (i < rev[i]) swap(arr[i], arr[rev[i]]);
	for (int i = 1; i < N; i <<= 1)
	{
		int wn = Pow(g, ((mo - 1) / i) >> 1);
		for (int j = 0; j < N; j += i << 1)
		{
			int w = 1;
			for (int k = 0; k < i; ++k, w = (long long)w * wn % mo)
			{
				int x = arr[j + k], y = (long long)w * arr[i + j + k] % mo;
				arr[j + k] = (x + y) % mo, arr[j + k + i] = ( x - y + mo) % mo;
			}
		}
	}
}

inline void IDFT(int *arr, int N)
{
	reverse(arr + 1, arr + N);
	FFT(arr, N);
	int invN = inv(N);
	for (int i = 0; i < N; ++i) arr[i] = (long long)arr[i] * invN % mo;
}

inline void Polynomial_Multiply(int *A, int *B, int n, int m, int *C) // n = degree bound of A, m = degree bound of B
{
	static int tempA[maxn],tempB[maxn];
	int N = 1;
	if (n <= 5 || m <= 5)
	{
		N = n + m - 1;
		memset(tempA, 0, sizeof(int) * N);
		for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			(tempA[i + j] += (long long) A[i] * B[j] % mo) %= mo;
		copy(tempA, tempA + N, C);
		return;
	}
	while (N < n + m - 1) N <<= 1;
	memcpy(tempA, A, sizeof(int) * n);
	memcpy(tempB, B, sizeof(int) * m);
	memset(tempA + n, 0, sizeof(int) * (N - n));
	memset(tempB + m, 0, sizeof(int) * (N - m));
	FFT(tempA, N);
	FFT(tempB, N);
	for (int i = 0; i < N; ++i) C[i] = (long long)tempA[i] * tempB[i] % mo;
	IDFT(C, N);
}

void Polynomial_Inverse(int *A, int *invA, int n)  // mod x^n
{
	if (n == 1)
	{
		invA[0] = inv(A[0]);
		return;
	}
	int mid = (n + 1) >> 1, N = 1;
	static int tempA[maxn], tempB[maxn];
	Polynomial_Inverse(A, invA, mid);
	while (N < (n << 1) - 1) N <<= 1;
	copy(A, A + n, tempA);
	memset(tempA + n, 0, sizeof(int) * (N - n));
	copy(invA, invA + mid, tempB);
	memset(tempB + mid, 0, sizeof(int) * (N - mid));
	FFT(tempA, N);
	FFT(tempB, N);
	for (int i = 0; i < N; ++i) invA[i] = (2 - (long long)tempA[i] * tempB[i] % mo + mo) * tempB[i] % mo;
	IDFT(invA, N);
}

void Polynomial_Division(int *A, int *B, int n, int m, int *Q, int *R) // n = degree bound of A, m = degree bound of B, A = B * Q + R
{
	if (n < m)
	{
		memcpy(R, A, sizeof(int) * n);
		return;
	}
	static int tempA[maxn], tempB[maxn];
	int N = 1, M = n - m + 1;
	while (N < (M << 1) - 1) N <<= 1;

	//tempB = B^R^-1
	memset(tempA, 0, sizeof(int) * N);
	reverse_copy(B, B + m, tempA);
	Polynomial_Inverse(tempA, tempB, M);
	reverse_copy(A, A + n, tempA);
	Polynomial_Multiply(tempA, tempB, M, M, Q);
	reverse(Q, Q + M);

	Polynomial_Multiply(Q, B, M, m, R);
	for (int i = 0; i < m - 1; ++i) if ((R[i] = A[i] - R[i]) < 0) R[i] += mo;
}

void Polynomial_Binary_Coefficient(int *X, int *res, int n, int **ptr, int &tot, int id)
{
	if (n == 1)
	{
		if ((res[tot] = -X[0]) < 0) res[tot] += mo;
		res[tot + 1] = 1;
		ptr[id] = res + tot;
		tot += 2;
		return;
	}
	int mid = n >> 1, N = 1;
	Polynomial_Binary_Coefficient(X, res, mid, ptr, tot, id << 1);
	Polynomial_Binary_Coefficient(X + mid, res, n - mid, ptr, tot, id << 1 | 1);
	if (id == 1) return;
	ptr[id] = res + tot;
	Polynomial_Multiply(ptr[id << 1], ptr[id << 1 | 1], mid + 1, n - mid + 1, ptr[id]);
	tot += n + 1;
}

void Polynomial_Calculator(int *A, int n, int *Y, int m, int **BCoef_ptr, int *X, int id)
{
	if (n <= 300 || m <= 300)
	{
		for (int i = 0; i < m; ++i)
		{
			long long p = 1, res = 0;
			for (int j = 0; j < n; ++j)
				res = (res + p * A[j]) % mo,
				p = p * X[i] % mo;
			Y[i] = res;
		}
		return;
	}
	if (n == 1)
	{
		Y[0] = A[0];
		return;
	}
	int mid = m >> 1, Rn = 0;
	static int Q[maxn];
	Polynomial_Division(A, BCoef_ptr[id << 1], n, mid + 1, Q, A + n);                            //R won't be cleared during division
	Rn = mid; while (Rn > 1 && A[n + Rn - 1] == 0) Rn--;
	Polynomial_Calculator(A + n, Rn, Y, mid, BCoef_ptr, X, id << 1);
	Polynomial_Division(A, BCoef_ptr[id << 1 | 1], n, m - mid + 1, Q, A + n);
	Rn = m - mid; while (Rn > 1 && A[n + Rn - 1] == 0) Rn--;
	Polynomial_Calculator(A + n, Rn, Y + mid, m - mid, BCoef_ptr, X + mid, id << 1 | 1);
}

void Polynomial_Calculator(int *Coef, int *X, int *Y, int n, int m)
{
	static int BCoef[maxn * 20], *BCoef_ptr[maxn << 2], temp[maxn << 2];                   //BCoef : Coefficients of \prod(x - xi)
	int tot = 0;
	Polynomial_Binary_Coefficient(X, BCoef, m, BCoef_ptr, tot, 1);
	memcpy(temp, Coef, sizeof(int) * n);
	Polynomial_Calculator(temp, n, Y, m, BCoef_ptr, X, 1);
}

Pollard_Rho

inline LL add(LL x, LL y, LL mod) {
	return (x += y) < mod ? x : x - mod;
}

inline LL mul(LL x, LL y, LL mod) {
	const int BLEN = __builtin_clzll(mod) - 1;
	const LL BMSK = (1LL << BLEN) - 1;
	LL ret = 0;
	if(x < y)
		swap(x, y);
	while(y > 0) {
		ret += x * (y & BMSK);
		ret = ret < mod ? ret : ret % mod;
		y >>= BLEN;
		x <<= BLEN;
		x = x < mod ? x : x % mod;
	}
	return ret;
}

inline LL Pow(LL x, LL k, LL mod) {
	LL ret = mod > 1 ? 1 : 0;
	for( ; k > 0; k >>= 1, x = mul(x, x, mod))
		if(k & 1)
			ret = mul(ret, x, mod);
	return ret;
}

inline bool miller_rabin(LL n) {
	if(n == 2)
		return 1;
	if(n < 2 || !(n & 1))
		return 0;
	LL s, r;
	for(s = 0, r = n - 1; !(r & 1); r >>= 1, ++s);
	static const int ptot = 12, pr[ptot] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
	for(int p : pr) {
		if(p >= n)
			break;
		LL cur = 1, nxt = p;
		for(LL k = r; k > 0; k >>= 1, nxt = mul(nxt, nxt, n))
			if(k & 1)
				cur = mul(cur, nxt, n);
		for(int i = 0; i < s; ++i) {
			nxt = mul(cur, cur, n);
			if(nxt == 1 && cur != 1 && cur != n - 1)
				return 0;
			cur = nxt;
		}
		if(cur != 1)
			return 0;
	}
	return 1;
}

inline LL pollard_rho(LL n) {
	static mt19937_64 rnd(996);
	while(1) {
		LL x = rnd() % (n - 3) + 2, y = x, c = rnd() % n, tim = 0, prd = 1;
		for(LL i = 1, stp = 2; ; ++i) {
			if(i == stp) {
				y = x;
				stp <<= 1;
			}
			if((x = add(mul(x, x, n), c, n)) == y)
				break;
			LL tmp = prd;
			if((prd = mul(prd, abs(y - x), n)) == 0)
				return __gcd(tmp, n);
			static const int maxt = 100;
			if((++tim) < maxt)
				continue;
			if((prd = __gcd(prd, n)) > 1)
				return prd;
			tim = 0;
		}
		if(tim > 0 && (prd = __gcd(prd, n)) > 1)
			return prd;
	}
	assert(0);
}

inline void factorize(LL n, vector<pair<LL, int> > &ret) {
	vector<LL> vec;
	queue<LL> que;
	que.push(n);
	while(!que.empty()) {
		LL x = que.front();
		que.pop();
		for(LL y : vec)
			for( ; x % y == 0; x /= y, vec.push_back(y));
		if(x == 1)
			continue;
		if(miller_rabin(x)) {
			vec.push_back(x);
		} else {
			LL y = pollard_rho(x);
			que.push(y);
			que.push(x / y);
		}
	}
	sort(vec.begin(), vec.end());
	ret.clear();
	for(auto x : vec)
		if(!ret.empty() && ret.back().first == x) {
			++ret.back().second;
		} else {
			ret.push_back(make_pair(x, 1LL));
		}
}

long long get_primitive_root(long long m, long long phim, vector<pair<long long, int> > &fac)
{
	if (m == 2) return 1;
	for (int x = 2;; x++)
	{
		int flg=1;
		if (Pow(x, phim, m) != 1) continue;
		for (auto p : fac)
			if (Pow(x, phim / p.first, m) == 1)
				{flg = 0; break;}
		if (flg) return x;
	}
}

后缀自动机

struct SAM
{
	struct State
	{
		int next[26];
		int link;
		int len;
	}st[maxn<<1];
 
	int last,cnt,n;
	int ccnt[maxn];
	int T[maxn<<1];
	int temp[maxn<<1],minl[maxn<<1];
	 
	SAM() {last=cnt=1;}
 
	void Extend(int c)
	{
		int x=++cnt,p;n++;
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1;
		else {
			int q=st[p].next[c];
			if (st[q].len==st[p].len+1) st[x].link=q;
			else {
				int v=++cnt;
				st[v]=st[q];
				st[v].len=st[p].len+1;
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[x].link=st[q].link=v;
			}
		}
		last=x;
	}
 
	void Topo()
	{
		for (int i=1;i<=cnt;i++) ccnt[st[i].len]++;
		for (int i=1;i<=n;i++) ccnt[i]+=ccnt[i-1];
		for (int i=1;i<=cnt;i++) T[ccnt[st[i].len]--]=i;
		for (int i=1;i<=cnt;i++) minl[i]=st[i].len;
	}
}

后缀数组

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

int sa[maxn],Rank[maxn],h[maxn];
char s[maxn];
int n;

void Radix_Sort(int *x,int *y,int m)
{
	static int c[maxn];
	for (int i=0;i<=m;i++) c[i]=0;
	for (int i=1;i<=n;i++) c[x[y[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];
}

void Build_SA()
{
	static int tmp1[maxn],tmp2[maxn];
	int i,m=128,*x=tmp1,*y=tmp2;
	for (i=1;i<=n;i++) x[i]=s[i],y[i]=i;
	Radix_Sort(x,y,m);
	for (int k=1;k<=n;k<<=1)
	{
		int p=0;
		for (i=n-k+1;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k;
		Radix_Sort(x,y,m);
		swap(x,y);p=1;x[sa[1]]=1;
		for (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;
	}
	for (i=1;i<=n;i++) Rank[sa[i]]=i;
}

void Get_Height()
{
	for (int i=1,hn=0;i<=n;i++)
	{
		if (hn) hn--;
		int j=sa[Rank[i]-1];
		while (i+hn<=n && j+hn<=n && s[i+hn]==s[j+hn]) hn++;
		h[Rank[i]]=hn;
	}
}

LCT维护后缀自动机Link树

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=600010;
 
struct SAM
{
	struct LCT
	{
		struct Node
		{
			Node *c[2],*p,*lcp;
			int v;
			int tag;
			int w() {return p->c[1]==this;}
		}MEM[maxn<<1],*ID[maxn<<1],*Null;
 
		int cnt;
		#define ls (x->c[0])
		#define rs (x->c[1])
 
		Node* NewNode(int _v=0)
		{
			++cnt;
			MEM[cnt].c[0]=MEM[cnt].c[1]=MEM[cnt].p=MEM[cnt].lcp=Null;
			MEM[cnt].v=_v;
			MEM[cnt].tag=0;
			return &MEM[cnt];
		}
 
		LCT()
		{
			Null=&MEM[0];
			Null->c[0]=Null->c[1]=Null->p=Null->lcp=Null;
			Null->v=Null->tag=0;
		}
 
		void Mark_Add(Node *x,int v) {if (x==Null) return;x->v+=v;x->tag+=v;}
 
		void Push_Down(Node *x)
		{
			if (x->tag)
			{
				Mark_Add(ls,x->tag);
				Mark_Add(rs,x->tag);
				x->tag=0;
			}
		}
 
		void Rotate(Node *x)
		{
			Node *p=x->p;
			int w=x->w();
			x->lcp=p->lcp;p->lcp=Null;
			Push_Down(p);Push_Down(x);
			x->p=p->p;p->p->c[p->w()]=x;
			x->c[!w]->p=p;p->c[w]=x->c[!w];
			x->c[!w]=p;p->p=x;
		}
 
		void Splay(Node *x)
		{
			Push_Down(x);
			while (x->p!=Null)
			{
				if (x->p->p==Null) {Rotate(x);break;}
				if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
				else Rotate(x),Rotate(x);
			}
		}
 
		void Access(Node *x)
		{
			Node *v=Null,*pre=x;
			while (x!=Null)
			{
				Splay(x);
				rs->p=v->lcp=Null;
				rs->lcp=v->p=x;
				rs=v;
				v=x;x=x->lcp;
			}
			Splay(pre);
		}
		 
		void Add_Node(int x,int c)
		{
			ID[x]=NewNode(c);
		}
 
		void Link(int x,int y)
		{
			ID[x]->lcp=ID[y];
			Access(ID[y]);
			Mark_Add(ID[y],ID[x]->v);
		}
		 
		void Cut(int x)
		{
			Access(ID[x]);
			ID[x]->c[0]->p=Null;
			Mark_Add(ID[x]->c[0],-ID[x]->v);
			ID[x]->c[0]=Null;
		}
 
		int Query(int x)
		{
			Access(ID[x]);
			return ID[x]->v;
		}
	}T;
 
	struct State
	{
		int next[26];
		int link;
		int len;
	}st[maxn<<1];
 
	int cnt,last;
 
	SAM() {cnt=last=1;T.ID[1]=T.NewNode();}
 
	void Extend(int c)
	{
		int x=++cnt,p;
		T.Add_Node(x,1);
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1,T.Link(x,1);
		else {
			int q=st[p].next[c];
			if (st[p].len+1==st[q].len) st[x].link=q,T.Link(x,q);
			else {
				int v=++cnt;
				T.Add_Node(v,0);
				st[v]=st[q];
				st[v].len=st[p].len+1;
				T.Cut(q);T.Link(v,st[v].link);
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[x].link=st[q].link=v;
				T.Link(x,v);T.Link(q,v);
			}
		}
		last=x;
	}
 
	void Insert(char *ch)
	{
		int n=strlen(ch);
		for (int i=0;i<n;i++) Extend(ch[i]-'A');
	}
 
	int Query(char *ch)
	{
		int n=strlen(ch),x=1;
		for (int i=0;i<n;i++)
		{
			int c=ch[i]-'A';
			if (!st[x].next[c]) return 0;
			x=st[x].next[c];
		}
		return T.Query(x);
	}
}M;
 
void decodeWithMask(char *ch,int mask)
{
	int n=strlen(ch);
	for (int j=0;j<n;j++)
		swap(ch[j],ch[mask=((mask*131)+j)%n]);
}
 
char ch[maxn],type[10];
int q,mask,ans;
 
int main()
{
	scanf("%d",&q);
	scanf("%s",ch);
	M.Insert(ch);
	for (int i=1;i<=q;i++)
	{
		scanf("%s%s",type,ch);
		decodeWithMask(ch,mask);
		if (type[0]=='A') M.Insert(ch);
		else printf("%d\n",ans=M.Query(ch)),mask^=ans;
	}
	return 0;
}

网络流Dinic

int head[maxv],nxt[maxm],E[maxm],F[maxm],Ecnt;
int cur[maxv],h[maxv];
int S,T;

bool BFS()
{
	static int q[maxn];
	int top=1,tail=1;
	for (int i=1;i<=T;i++) cur[i]=head[i],h[i]=inf;
	h[S]=1;
	q[1]=S;
	while (top<=tail)
	{
		int u=q[top++];
		for (int i=head[u];i;i=nxt[i]) if (F[i^1] && h[E[i]]==inf)
		{
			h[E[i]]=h[u]+1;
			q[++tail]=E[i];
		}
	}
	return h[T]!=inf;
}

int DFS(int x,int flow)
{
	if (x==T) return flow;
	int rest=flow;
	for (int &i=cur[x];i;i=nxt[i]) if (F[i^1] && h[E[i]]==h[x]+1)
	{
		int ret=DFS(E[i],min(rest,F[i^1]));
		rest-=ret;
		F[i]+=ret;F[i^1]-=ret;
		if (rest==0) return flow;
	}
	return flow-rest;
}

int Dinic()
{
	int res=0;
	while (BFS()) res+=DFS(S,inf);
	return res;
}

//Init: Ecnt=1;memset(head,0,sizeof(head));

高斯消元

double coef[maxequa][maxn+1];
double ans[maxn];
int freevar[maxn],freevar_num;

int Gauss(int equa_cnt,int num)  //equa_cnt : number of equations; n : number of variables;
{
	int leadvar_num=0;
	for (int i=1,lead_var=1;i<=equa_cnt && lead_var<=num;i++,lead_var++)
	{
		int valid_equa=-1;
		while (valid_equa==-1)
		{
			for (int j=i;j<=equa_cnt;j++) if (coef[j][lead_var]!=0) {valid_equa=j;break;}
			if (valid_equa==-1)
				freevar[++freevar_num]=lead_var++;
			if (lead_var>num) break;
		}
		if (valid_equa==-1) continue;
		leadvar_num++;
		if (valid_equa!=i)
			for (int j=lead_var;j<=num+1;j++) swap(coef[i][j],coef[valid_equa][j]);

		for (int j=lead_var+1;j<=num+1;j++) coef[i][j]=coef[i][j]/coef[i][lead_var];
		coef[i][lead_var]=1;
		for (int j=i+1;j<=equa_cnt;j++) if (coef[j][lead_var]!=0)
		{
			double g=coef[j][lead_var]/coef[i][lead_var];
			for (int k=lead_var;k<=num+1;k++)
				coef[j][k]=coef[j][k]-g*coef[i][k];
		}
	}
	while (lead_var<=num)
		freevar[++freevar_num]=lead_var++;

	for (int i=leadvar_num+1;i<=equa_cnt;i++) if (coef[i][num+1]!=0) return -1;     // no solution

	for (int i=leadvar_num;i>=1;i--)
	{
		int lead_var=-1;
		for (int j=i;j<=num;j++) if (coef[i][j]!=0) {lead_var=j;break;}
		for (int j=1;j<i;j++) if (coef[j][lead_var]!=0)
		{
			double g=coef[j][lead_var]/coef[i][lead_var];
			for (int k=lead_var;k<=num+1;k++)
				coef[j][k]=coef[j][k]-g*coef[i][k];
		}
	}

	return leadvar_num;
}

void MultiSolution(int num)
{
	for (int i=1;i<=freevar_num;i++) ans[freevar[i]]=1;  //free variable
	for (int i=num-freevar_num;i>=1;i--)
	{
		int lead_var=-1;
		for (int j=i;j<=num;j++) if (coef[i][j]!=0) {lead_var=j;break;}
		ans[lead_var]=coef[i][num+1];
		for (int j=lead_var+1;j<=num;j++) if (coef[i][j]!=0)
			ans[lead_var]=ans[lead_var]-coef[i][j]*ans[j];
	}
	for (int i=1;i<=num;i++)
		ans[i].print();
}

前向星存图

struct Edge
{
	int x,y;
};

struct Graph
{
	Edge E[maxm],*begin[maxn],*end[maxn];
	int n,m;

	void init(int _n=0) {n=_n,m=0;}
	void add_edge(int x,int y) {E[m++]={x,y};}

	void resort()
	{
		static Edge tmp[maxm];
		static int cnt[maxn];
		memcpy(tmp,E,sizeof(Edge)*m);
		memset(cnt,0,sizeof(int)*(n+1));
		for (int i=0;i<m;i++) cnt[tmp[i].y]++;
		for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for (int i=0;i<m;i++) E[--cnt[tmp[i].y]]=tmp[i];
		memcpy(tmp,E,sizeof(Edge)*m);
		memset(cnt,0,sizeof(int)*(n+1));
		for (int i=0;i<m;i++) cnt[tmp[i].x]++;
		for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
		for (int i=0;i<m;i++) E[--cnt[tmp[i].x]]=tmp[i];
		int m0=m;m=m0?1:0;
		for (int i=1;i<m0;i++) if (!(E[i].x==E[m-1].x && E[i].y==E[m-1].y)) E[m++]=E[i];
		for (int i=1,j=0;i<=n;i++)
		{
			begin[i]=&E[j];
			while (j<m && E[j].x==i) j++;
			end[i]=&E[j];
		}
	}

	int order[maxn];

	void topo()
	{
		static int deg[maxn];
		memset(deg,0,sizeof(int)*(n+1));
		for (int i=0;i<m;i++) deg[E[i].y]++;
		int tail=0;
		for (int i=1;i<=n;i++) if (deg[i]==0) order[++tail]=i;
		for (int p=1;p<=tail;p++)
		{
			int u=order[p];
			for (auto it=begin[u];it!=end[u];++it)
				if ((--deg[it->y])==0)
					order[++tail]=it->y;
		}
	}
}G;

斜率优化(简易版)

struct Info
{
	long double k,b;
	Info(long double _k=0,long double _b=0):k(_k),b(_b){}
};

struct Deque
{
	Info I[maxn];
	long double k[maxn],b[maxn];
	int top,tail;

	Deque() {top=1;tail=0;}

	void autopop(long double x)
	{
		while (top<tail && I[top].k*x+I[top].b>=k[top+1]*x+b[top+1]) top++;
	}

	void push(long double k0,long double b0)
	{
		while (top<tail && (b0-b[tail-1])/(k0-k[tail-1])>=(b[tail]-b[tail-1])/(k[tail]-k[tail-1])) tail--;
		++tail;
		k[tail]=k0;
		b[tail]=b0;
	}

	Info front() {return Info(k[top],b[top]);}
}Q;

费用流

struct Queue
{
	int q[maxn];
	int Instack[maxn];
	int top,tail;

	bool empty() {return top==(tail+1)%maxn;}
	void Init() {top=1;tail=0;}
	void push(int x)
	{
		tail=(tail+1)%maxn;
		q[tail]=x;
		Instack[x]=1;
	}

	void pop()
	{
		Instack[q[top]]=0;
		top=(top+1)%maxn;
	}

	int front()
	{
		return q[top];
	}
}Q;

int pred[maxn];
int dis[maxn];

bool SPFA()
{
	Q.Init();
	for (int i=1;i<=T;i++) dis[i]=inf;
	dis[S]=0;
	Q.push(S);
	while (!Q.empty())
	{
		int x=Q.front();
		Q.pop();
		if (x==T) continue;
		for (int i=head[x];i;i=nxt[i]) if (F[i^1] && dis[E[i]]>dis[x]+D[i])
		{
			dis[E[i]]=dis[x]+D[i];
			pred[E[i]]=i;
			if (!Q.Instack[E[i]])
				Q.push(E[i]);
		}
	}
	return dis[T]!=inf;
}

int MinCostFlow()
{
	int res=0;
	while (SPFA())
	{
		int flow=inf;
		for (int i=T;i!=S;i=E[pred[i]^1])
			flow=min(flow,F[pred[i]^1]);
		res+=flow;
		for (int i=T;i!=S;i=E[pred[i]^1])
			F[pred[i]]+=flow,
			F[pred[i]^1]-=flow;
	}
	return res;
}

Splay

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int maxn=500010,inf=~0U>>1;
using namespace std;
 
struct Node
{
	Node *c[2],*p;
	int size;
	int v,sum;
	int lmax,rmax,vmax;
	bool tag_same,tag_rev;
	int samev;
 
	bool w() {return p->c[1]==this;}
}*root,*Null;
 
namespace Memory
{
	Node Mem[maxn];
	Node *Stack[maxn];
	int top;
 
	void Memory_Init() {for (int i=0;i<maxn;i++) Stack[i]=&Mem[i];top=maxn-1;}
	void Delete_Node(Node *t) {Stack[++top]=t;}
	Node* New_Node() {return Stack[top--];}
};
 
struct Splay_Tree
{
	#define ls x->c[0]
	#define rs x->c[1]
	void Update(Node *x)
	{
		if (x==Null) return;
		x->sum=ls->sum+rs->sum+x->v;
		x->size=ls->size+rs->size+1;
		int L_rmax=max(ls->rmax,0),R_lmax=max(rs->lmax,0);
		x->lmax=max(ls->lmax,ls->sum+x->v+R_lmax);
		x->rmax=max(rs->rmax,rs->sum+x->v+L_rmax);
		x->vmax=max(ls->vmax,rs->vmax);
		x->vmax=max(x->vmax,L_rmax+x->v+R_lmax);
	}
 
	void Update_Same(Node *x,int samev)
	{
		if (x==Null) return;
		x->v=samev;
		x->sum=x->size*samev;
		x->lmax=x->rmax=x->vmax=max(x->sum,samev);
		x->samev=samev;
		x->tag_same=1;
	}
 
	void Update_Rev(Node *x)
	{
		if (x==Null) return;
		swap(ls,rs);
		swap(x->lmax,x->rmax);
		x->tag_rev^=1;
	}
 
	void Push_Down(Node *x)
	{
		if (x->tag_same)
		{
			Update_Same(ls,x->samev);
			Update_Same(rs,x->samev);
			x->tag_same=0;
			x->samev=0;
		}
		if (x->tag_rev)
		{
			Update_Rev(ls);
			Update_Rev(rs);
			x->tag_rev=0;
		}
	}
 
	void Rotate(Node *x)
	{
		Node *p=x->p;
		Push_Down(p);Push_Down(x);
		bool w=x->w();
		p->p->c[p->w()]=x;
		x->p=p->p;p->c[w]=x->c[!w];
		x->c[!w]->p=p;
		x->c[!w]=p;p->p=x;
		Update(p);
		if (p==root) root=x;
	}
 
	void Splay(Node *x,Node *head) 
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=head)
			if (x->p->p==head) Rotate(x);
		else if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		Update(x);
	}
 
	Node* Select(int kth)
	{
		Node *x=root;
		while (kth)
		{
			Push_Down(x);
			int lsize=ls->size;
			if (lsize+1==kth) return x;
			if (kth>lsize) kth-=lsize+1,x=rs;
			else x=ls;
		}
		return x;
	}
 
	Node* Get_Seq(int l,int r)
	{
		if (l==1 && r==root->size) return root;
		if (l==1 && r< root->size) {Splay(Select(r+1),Null);return root->c[0];}
		if (l> 1 && r==root->size) {Splay(Select(l-1),Null);return root->c[1];}
		Splay(Select(l-1),Null);
		Splay(Select(r+1),root);
		return root->c[1]->c[0];
	}
 
	void Mark_Same(Node *x,int samev)
	{
		Update_Same(x,samev);
		Splay(x,Null);
	}
 
	void Mark_Rev(Node *x)
	{
		Update_Rev(x);
		Splay(x,Null);
	}
 
	Node* New_Node(int v)
	{
		Node *x=Memory::New_Node();
		x->v=v;
		x->samev=x->tag_same=x->tag_rev=0;
		return x;
	}
 
	Node* Make_Tree(int *a,int l,int r)
	{
		if (l>r) return Null;
		int mid=(l+r)>>1;
		Node *x=New_Node(a[mid]);
		ls=Make_Tree(a,l,mid-1);
		rs=Make_Tree(a,mid+1,r);
		if (ls!=Null) ls->p=x;
		if (rs!=Null) rs->p=x;
		Update(x);
		return x;
	}
 
	Splay_Tree()
	{
		Memory::Memory_Init();
		Null=Memory::New_Node();
		Null->v=Null->sum=Null->size=Null->samev=0;
		Null->tag_same=Null->tag_rev=0;
		Null->lmax=Null->rmax=Null->vmax=-inf;
		Null->p=Null->c[0]=Null->c[1]=NULL;
		root=Null;
	}
 
	void Insert(int *a,int posi,int tot)
	{
		Node *x=Make_Tree(a,1,tot);
		if (root==Null) root=x,root->p=Null,Null->c[0]=root;
		else if (posi==root->size) {
			Splay(Select(root->size),Null);
			root->c[1]=x;
			x->p=root;
			Update(root);
		} else if (posi==0) {
			Splay(Select(1),Null);
			root->c[0]=x;
			x->p=root;
			Update(root);
		} else {
			Splay(Select(posi),Null);
			Splay(Select(posi+1),root);
			root->c[1]->c[0]=x;
			x->p=root->c[1];
			Splay(x,Null);
		}
	}
 
	void Delete_DFS(Node *x)
	{
		if (ls!=Null) Delete_DFS(ls);
		if (rs!=Null) Delete_DFS(rs);
		Memory::Delete_Node(x);
	}
 
	void Delete(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		if (x==root) root=Null;
		else x->p->c[x->w()]=Null,Splay(x->p,Null);
		Delete_DFS(x);
	}
 
	void Make_Same(int posi,int tot,int c)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		Mark_Same(x,c);
		Splay(x,Null);
	}
 
	void Make_Rev(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		Mark_Rev(x);
		Splay(x,Null);
	}
 
	void Get_Sum(int posi,int tot)
	{
		Node *x=Get_Seq(posi,posi+tot-1);
		printf("%d\n",x->sum);
		Splay(x,Null);
	}
 
	void Max_Sum()
	{
		printf("%d\n",(root==Null)?0:root->vmax);
	}
	 
	void Print(Node *x)
	{
		if (x==Null) {if (x==root) printf("\n");return;}
		Push_Down(x);
		Print(ls);
		printf("%d ",x->v);
		Print(rs);
		if (x==root) printf("\n");
	}
}T;
 
int a[maxn];
char ctr[20];
int n,m;
 
inline void read(int &x)
{
	char ch;
	int flag=0;
	while (((ch=getchar())<'0' || ch>'9') && ch!='-');
	if (ch=='-') flag=-1,x=0;
	else flag=1,x=ch-'0';
	while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';
	x=x*flag;
}
 
int main()
{
	read(n),read(m);
	for (int i=1;i<=n;i++) read(a[i]);
	T.Insert(a,0,n);
	for (int i=1;i<=m;i++)
	{
		scanf("%s",ctr+1);
		int tot,posi,c;
		if (ctr[1]=='I') {read(posi),read(tot);for (int i=1;i<=tot;i++) read(a[i]);T.Insert(a,posi,tot);}
		else if (ctr[1]=='D') {read(posi),read(tot);T.Delete(posi,tot);}
		else if (ctr[1]=='R') {read(posi),read(tot);T.Make_Rev(posi,tot);}
		else if (ctr[1]=='G') {read(posi),read(tot);T.Get_Sum(posi,tot);}
		else if (ctr[3]=='K') {read(posi),read(tot),read(c);T.Make_Same(posi,tot,c);}
		else T.Max_Sum();
		//T.Print(root);
	}
	return 0;
}

LCT

struct LCT
{
    struct Node
    {
        Node *c[2],*p,*lcp,*maxv;
        int v;
        int tag_rev;
        int w() {return p->c[1]==this;}
    }*Null,*ND[maxn],*ED[maxm];
 
    #define ls x->c[0]
    #define rs x->c[1]
 
    void Update(Node *x)
    {
        if (x==Null) return;
        x->maxv=x;
        if (ls->maxv->v>x->maxv->v) x->maxv=ls->maxv;
        if (rs->maxv->v>x->maxv->v) x->maxv=rs->maxv; 
    }
 
    void Mark_Rev(Node *x)
    {
        swap(ls,rs);
        x->tag_rev^=1;
    }
 
    void Push_Down(Node *x)
    {
        if (!x->tag_rev) return;
        Mark_Rev(ls);
        Mark_Rev(rs);
        x->tag_rev=0;
    }
 
    void Rotate(Node *x)
    {
        Node *p=x->p;
        int w=x->w();
        Push_Down(p);Push_Down(x);
        x->lcp=p->lcp;p->lcp=Null;
        p->p->c[p->w()]=x;x->c[!w]->p=p;
        x->p=p->p;p->c[w]=x->c[!w];
        x->c[!w]=p;p->p=x;
        Update(p);
    }
 
    void Splay(Node *x)
    {
        if (x==Null) return;
        Push_Down(x);
        while (x->p!=Null)
        {
            if (x->p->p==Null) {Rotate(x);break;}
            if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
            else Rotate(x),Rotate(x);
        }
        Update(x);
    }
 
    void Access(Node *x)
    {
        Node *v=Null,*pre=x;
        while (x!=Null)
        {
            Splay(x);
            rs->lcp=x;
            rs->p=Null;
            rs=v;
            v->p=x;
            v->lcp=Null;
            Update(x);
            v=x;x=x->lcp;
        }
        Splay(pre);
    }
 
    Node* Find_Root(Node *x)
    {
        Access(x);
        while (ls!=Null) Push_Down(x),x=ls;
        Splay(x);
        return x;
    }
 
    void Set_Root(Node *x)
    {
        Access(x);
        Mark_Rev(x);
    }
 
    Node* Prev(Node *x)
    {
        Splay(x);
        if (rs==Null) return Null;
        Push_Down(x);x=rs;
        while (ls!=Null) Push_Down(x),x=ls;
        Splay(x);
        return x;
    }
 
    void Link(Node *x,Node *v)
    {
        Set_Root(x);
        x->lcp=v;
        Access(x);
    }
 
    void Cut(Node *x)
    {
        Access(x);
        ls->p=Null;
        ls=Null;
        Update(x);
    }
 
    void Init(int n,int m)
    {
        for (int i=0;i<=n;i++) ND[i]=new Node;
        for (int i=1;i<=m;i++) ED[i]=new Node;
        Null=ND[0];
        for (int i=0;i<=n;i++) ND[i]->c[0]=ND[i]->c[1]=ND[i]->p=ND[i]->lcp=ND[i]->maxv=Null,ND[i]->v=ND[i]->tag_rev=0;
        for (int i=1;i<=m;i++) ED[i]->c[0]=ED[i]->c[1]=ED[i]->p=ED[i]->lcp=Null,ED[i]->maxv=ED[i],ED[i]->v=ED[i]->tag_rev=0;
    }
 
    void Link(int x,int y,int e)
    {
        Link(ND[x],ED[e]);
        Link(ED[e],ND[y]);
    }
     
    bool Connected(int x,int y) {return Find_Root(ND[x])==Find_Root(ND[y]);}
 
    Node* Max_Edge(Node *x,Node *y)
    {
        Set_Root(x);
        Access(y);
        return y->maxv;
    }
 
    void Cut_MaxEdge(int x,int y)
    {
        Node *e=Max_Edge(ND[x],ND[y]);
        Cut(Prev(e)),Cut(e);
    }
     
    int Max_Edge_V(int x,int y) {return Max_Edge(ND[x],ND[y])->v;}
     
    #undef ls
    #undef rs
}T;