板子复习

说实话，这板子里绝大部分内容都忘了….

常用技巧

快读

inline int read() {
	int w=1,x=0;
	char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return w*x;
}

---

离散化

int raw[N],t;
map<int,int> val;
vector<int> tmp;
void discrete() {
    sort(tmp.begin(),tmp.end());
    t=unique(tmp.begin(),tmp.end())-tmp.begin();
    for(int i=0;i<t;i++) {
        val[tmp[i]]=i+1;
        raw[i+1]=tmp[i];
    }
}

---

快速幂

递归版

int qpow(int x,int y) {
	if(!y) return 1;
	int t=qpow(x,y>>1);
	(t*=t)%=mod;
	if(y&1) return t*x%mod;
	return t;
}

非递归版

int qpow(int x,int y) {
	int ans=1;
	while(y) {
		if(y&1) (ans*=x)%=mod;
		(x*=x)%=mod,y>>=1;
	}
	return ans;
}

---

龟速乘

递归版

int smul(int x,int y) {
	if(!y) return 0;
	int t=smul(x,y>>1);
	(t+=t)%=mod;
	if(y&1) return (t+x)%mod;
	return t;
}

非递归版

int smul(int x,int y) {
	int ans=0;
	while(y) {
		if(y&1) (ans+=x)%=mod
		(a+=a)%=mod,y>>=1;
	}
	return ans;
}

---

邻接表存图

int head[N],tot=0;
struct graph{
    int v,w,next;
}edge[N<<1];
void add_edge(int u,int v,int w) {edge[++tot].v=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v,int w) {add_edge(u,v,w),add_edge(v,u,w);}

---

数学

矩阵

struct Matrix{
	int row,col;
	ll a[N][N];
	Matrix() {row=col=0,memset(a,0,sizeof(a));}
	Matrix(int n):row(n),col(n){memset(a,0,sizeof(a));}
	Matrix(int n,int m):row(n),col(m){memset(a,0,sizeof(a));}
	void readp() {
		for(int i=1;i<=row;i++) {
			for(int j=1;j<=col;j++) a[i][j]=read();
		}
	}
	void printp() {
		for(int i=1;i<=row;i++) {
			for(int j=1;j<=col;j++) printf("%lld ",a[i][j]);
			printf("\n");
		}
	}
	void identity() {for(int i=1;i<=row;i++) a[i][i]=1;}
	Matrix operator * (const Matrix &x)const {
		Matrix y(row,x.col);
		for(int i=1;i<=row;i++) {
			for(int j=1;j<=x.col;j++) {
				for(int k=1;k<=col;k++) (y.a[i][j]+=a[i][k]*x.a[k][j]%mod)%=mod;
				y.a[i][j]=(y.a[i][j]+mod)%mod;
			}
		}
		return y;
	}
	Matrix operator *= (const Matrix &x) {
		return *this=*this*x;
	}
};

---

矩阵快速幂

Matrix qpow(Matrix x,ll y) {
	Matrix a=x,ans(2);
	ans.identity();
	while(y) {
		if(y&1) ans*=a;
		a*=a;
		y>>=1;
	}
	return ans;
}

---

高斯消元法

bool gauss() {
    int i,j,k;
    double t;
    for(i=1;i<=n;i++) {
        for(k=i,j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[k][i])) k=j;
        if(k!=i) for(int j=i;j<=n+1;j++) t=a[i][j],a[i][j]=a[k][j],a[k][j]=t;
        for(int j=i+1;j<=n;j++) for(t=a[j][i]/a[i][i],k=i;k<=n+1;k++) a[j][k]-=a[i][k]*t;
    }
    if(!a[n][n]) return false;
    for(ans[n]=a[n][n+1]/a[n][n],i=n-1;i;i--) {
        for(ans[i]=a[i][n+1],j=n;j>i;j--) ans[i]-=ans[j]*a[i][j];
        if(!a[i][i]) return false;
        ans[i]/=a[i][i];
    }
    return true;
}

---

欧几里得算法（GCD）

int gcd(int x,int y) {
	return !y?x:gcd(y,x%y);
}

---

扩展欧几里得算法（EXGCD）

void Exgcd(int a,int b) {
	if(!b) x=1,y=0;
	else {
		Exgcd(b,a%b);
		int t=x;
		x=y,y=t-a/b*y;
	}
}

---

‘## 中国剩余定理（CRT）

题目：[洛谷P1495] 【模板】中国剩余定理(CRT)/曹冲养猪

学习笔记：中国剩余定理学习笔记

#include<bits/stdc++.h>
#define ll long long 
#define N 15
#define plus(x,y) ((x%m)+(y%m))%m
#define mul(x,y) ((x%m)*(y%m))%m

using namespace std;

inline ll read() {
	ll w=1,x=0;
	char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return w*x;
}

int n;
ll a[N],b[N],x,y,m=1,ans=0;

void Exgcd(ll a,ll b) {
	if(!b) x=1,y=0;
	else {
		Exgcd(b,a%b);
		ll t=x;
		x=y,y=t-a/b*y;
	}
}

int main() {
	n=read();
	for(int i=1;i<=n;i++) {
		a[i]=read(),b[i]=read();
		m*=a[i];
	}
	
	for(int i=1;i<=n;i++) {
		Exgcd(m/a[i],a[i]);
		x=(x%a[i]+a[i])%a[i];
		(ans+=m/a[i]*x*b[i]%m)%=m;
	}
	
	printf("%lld\n",ans);
		
	return 0;
}

---

扩展中国剩余定理(EXCRT)

题目：洛谷[P4777] 【模板】扩展中国剩余定理（EXCRT）

学习笔记：扩展中国剩余定理学习笔记

#include<bits/stdc++.h>
#define N 100010
#define ll long long 

using namespace std;

inline ll read() {
	ll w=1,x=0;
	char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return w*x;
}

int n;
ll a[N],b[N],ans,x,y;

ll gsc(ll a,ll b,ll mod) {
	if(!b) return 0;
	ll t=gsc(a,b/2,mod);
	(t+=t)%=mod;
	if(b&1) return (t+a)%mod;
	return t;
}
ll EXGCD(ll a,ll b) {
	if(!b) {
		x=1,y=0;
		return a;
	}
	else {
		ll gcd=EXGCD(b,a%b),t=x;
		x=y;
		y=t-a/b*y;
		return gcd;
	}
}
void EXCRT(ll a[],ll b[],int n) {
	ans=a[1];
	ll m=b[1];
	for(int i=2;i<=n;i++) {
		ll gcd=EXGCD(m,b[i]),c=((a[i]-ans)%b[i]+b[i])%b[i];
		c/=gcd;
		x=gsc(x,c,b[i]);
		ans+=m*x;
		m*=b[i]/gcd;
		ans=(ans%m+m)%m;
	}
}

int main() {
	n=read();
	for(int i=1;i<=n;i++) b[i]=read(),a[i]=read();
	
	EXCRT(a,b,n);
	
	printf("%lld\n",ans);
		
	return 0;
}

---

BSGS算法

题目：[洛谷P4028] New Product

学习笔记：BSGS算法学习笔记

#include<bits/stdc++.h>
#define ll long long 
#define mul(x,y) ((x%p)*(y%p))%p

using namespace std;

inline int read() {
	int w=1,x=0;
	char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return w*x;
}

int T,p,a,b;
map <ll,int> vh;

int qpow(int x,int y,int p) {
	if(!y) return 1;
	int t=qpow(x,y>>1,p);
	(t*=t)%=p;
	if(y&1) return t*x%p;
	return t;
}
int BSGS(int p,int a,int b) {
	vh.clear();
	if(!(a%p)) return -1;
	if(b==1) return 0;
	b%=p;
	int k=ceil(sqrt(p));
	ll temp=b,t=qpow(a,k,p);
	for(int j=1;j<=k;j++) {
		(temp*=a)%=p;
		vh[temp]=j;
	}
	temp=1;
	for(int i=1;i<=k;i++) {
		(temp*=t)%=p;
		if(vh[temp]) return ((i*k-vh[temp])%p+p)%p;
	}
	return -1;
}

int main() {
	T=read();
		
	while(T--) {
		p=read(),a=read(),b=read();
		int ans=BSGS(p,a,b);
		if(ans!=-1) printf("%d\n",ans);
		else printf("Couldn't Produce!\n");
	}
	
	return 0;
}

---

埃氏筛法

int prime[N],js=0;
bool vh[N];
void primes(int n) {
	vh[1]=true;
	for(int i=2;i<=n;i++) {
		if(!vh[i]) {
			prime[++js]=i;
			for(int j=2;i*j<=n;j++) vh[i*j]=true;
		}
	}
}

---

线性筛法

int prime[N],v[N],js=0;
void primes(int n) {
	for(int i=2;i<=n;i++) {
		if(!v[i]) prime[++js]=i,v[i]=i;
		for(int j=1;j<=js;j++) {
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
		}
	}
}

---

线性筛求欧拉函数

$$x=\prod_{i=1}^m {p_i}^{c_i}\\\varphi(x)=x\prod_{i=1}^m(1-\frac{1}{p_i})$$

int prime[N],v[N],phi[N],js=0;
void primes(int n) {
	phi[1]=1;
	for(int i=2;i<=n;i++) {
		if(!v[i]) prime[++js]=i,v[i]=i,phi[i]=i-1;
		for(int j=1;j<=js;j++) {
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]) phi[i*prime[j]]=phi[i]*phi[prime[j]];
			else phi[i*prime[j]]=phi[i]*prime[j];
		}
	}
}

---

线性筛求因数个数

$$x=\prod_{i=1}^m {p_i}^{c_i}\\ d(x)=\prod_{i=1}^m (c_i+1)$$

int prime[N],v[N],d[N],num[N],js=0;
void primes(int n) {
	d[1]=1;
	for(int i=2;i<=n;i++) {
		if(!v[i]) prime[++js]=i,v[i]=i,num[i]=1,d[i]=2;
		for(int j=1;j<=js;j++) {
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]) num[i*prime[j]]=1,d[i*prime[j]]=d[i]*(num[i*prime[j]]+1);
			else num[i*prime[j]]=num[i]+1,d[i*prime[j]]=d[i]/(num[i]+1)*(num[i*prime[j]]+1);
		}
	}
}

---

线性筛求因数和

$$x=\prod_{i=1}^m {p_i}^{c_i}\\ \sigma(x)=\prod_{i=1}^m\Bigg(\sum_{j=0}^{c_i}p_i^{j}\Bigg)$$

int prime[N],v[N],sigma[N],sum[N],js=0;
void primes(int n) {
	sigma[1]=1;
	for(int i=2;i<=n;i++) {
		if(!v[i]) prime[++js]=i,v[i]=i,sum[i]=i+1,sigma[i]=i+1;
		for(int j=1;j<=js;j++) {
			if(prime[j]>v[i]||i*prime[j]>n) break;
			v[i*prime[j]]=prime[j];
			if(i%prime[j]) sum[i*prime[j]]=prime[j]+1,sigma[i*prime[j]]=sigma[i]*sum[prime[j]];
			else sum[i*prime[j]]=sum[i]*prime[j]+1,sigma[i*prime[j]]=sigma[i]/sum[i]*sum[i*prime[j]];
		}
	}
}

---

乘法逆元（EXGCD）

void Exgcd(int a,int b) {
	if(!b) x=1,y=0;
	else {
		Exgcd(b,a%b);
		int t=x;
		x=y,y=t-a/b*y;
	}
}
int inv(int a) {
	Exgcd(a,mod);
	return (x%mod+mod)%mod;
}

---

乘法逆元（费马小定理）

ll qpow(ll x,ll y) {
	if(!y) return 1;
	ll t=qpow(x,y>>1);
	(t*=t)%=mod;
	if(y&1) return t*x%mod;
	return t;
}
ll inv(ll a) {
	return qpow(a,mod-2);
}

---

乘法逆元（线性递推）

$$\text{inv}(i)=-\Big\lfloor\dfrac{p}{i}\Big\rfloor\times(p\bmod i)\pmod {p}$$

ll n,p;
ll inv[N];
void init() {
    inv[1]=1;
    for(int i=2;i<=n;i++) {
        inv[i]=-(p/i)*inv[p%i];
        if(inv[i]<0) inv[i]=inv[i]%p+p;
    }
}

---

组合数（递推）

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$$

void init(){ 
	c[0][0]=1; 
	for(int i=1;i<=n;i++) { 
		for(int j=0;j<=i;j++) {
			if(j==0||i==j)c[i][j]=1; 
			else c[i][j]=c[i-1][j-1]+c[i-1][j];
		}
	}
}

---

组合数取模（卢卡斯定理）

ll qpow(ll x,ll y) {
	if(!y) return 1;
	ll t=qpow(x,y>>1);
	(t*=t)%=p;
	if(y&1) return t*x%p;
	return t;
}
ll inv(ll a) {
	return qpow(a,p-2);
}
ll C(ll n,ll m) {
	if(n<m) return 0;
	if(m>n-m) m=n-m;
	ll a=1,b=1;
	for(int i=0;i<m;i++) {
		a=(a*(n-i))%p;
		b=(b*(i+1))%p;
	}
	return (a*inv(b))%p;
}
ll Laucs(ll n,ll m) {
	if(!m) return 1;
	return (Laucs(n/p,m/p)*C(n%p,m%p))%p;
}

---

数据结构

树状数组

题目：[洛谷P3374] 【模板】树状数组 1

int n,m;  
class Binary_Indexed_Tree{  
  private:  
    int sum[N];  
    #define lowbit(x) (x&(-x))  
  public:  
    void change(int x,int y) {for(;x<=n;x+=lowbit(x)) sum[x]+=y;}  
    int ask(int x) {int ans=0;for(;x;x-=lowbit(x)) ans+=sum[x];return ans;}
}BIT;

---

树状数组求RMQ

题目：[HDU1754] I Hate It

class Binary_Indexed_Tree{  
  private:  
      int d[N];  
      #define lowbit(x) (x&(-x)) 
  public:  
    void change(int x,int y) {  
        a[x]=y;  
        while(x<=n) {  
            d[x]=y;  
            for(int j=1;j<lowbit(x);j<<=1) d[x]=max(d[x],d[x-j]);  
            x+=lowbit(x);  
        }  
    }  
    int ask(int L,int R) {  
        int ans=0;  
        while(L<=R) {  
            if(R-lowbit(R)+1>=L) ans=max(ans,d[R]),R-=lowbit(R);  
            else ans=max(ans,a[R]),R--;  
        }  
        return ans;  
    }  
}BIT;

---

线段树

题目：[洛谷P3373] 【模板】线段树 2

class SegmentTree{
  private:
  	ll sum[N<<2],lazymul[N<<2],lazyplus[N<<2];
  	#define s(x) sum[x]
  	#define lm(x) lazymul[x]
  	#define lp(x) lazyplus[x]
  	#define ls (p<<1)
  	#define rs (ls|1)
  	#define mid (l+r>>1)
	inline void update(int p) {
		s(p)=s(ls)+s(rs);
		Mod(s(p));
	}
	inline void spread(int p,int l,int r) {
		if(!lp(p)&&lm(p)==1) return ;
		s(ls)*=lm(p);Mod(s(ls));s(ls)+=lp(p)*(mid-l+1);Mod(s(ls));
		s(rs)*=lm(p);Mod(s(rs));s(rs)+=lp(p)*(r-mid);Mod(s(rs));
		lm(ls)*=lm(p);Mod(lm(ls));
		lm(rs)*=lm(p);Mod(lm(rs));
		lp(ls)*=lm(p);Mod(lp(ls));lp(ls)+=lp(p);Mod(lp(ls));
		lp(rs)*=lm(p);Mod(lp(rs));lp(rs)+=lp(p);Mod(lp(rs));
		lp(p)=0;
		lm(p)=1;
	}
  public:
  	void build(int p,int l,int r) {
  		lm(p)=1,lp(p)=0;
  		if(l==r) {
  			s(p)=read();
  			Mod(s(p));
  			return ;
  		}
  		build(ls,l,mid);
  		build(rs,mid+1,r);
  		update(p);
  	}
  	void changeplus(int p,int l,int r,int L,int R,ll x) {
  		if(l>R||r<L) return ;
  		if(l>=L&&r<=R) {
  			s(p)+=x*(r-l+1);Mod(s(p));
  			lp(p)+=x;Mod(lp(p));
  			return ;
  		}
  		spread(p,l,r);
  		changeplus(ls,l,mid,L,R,x);
  		changeplus(rs,mid+1,r,L,R,x);
  		update(p);
  	}
  	void changemul(int p,int l,int r,int L,int R,ll x) {
  		if(l>R||r<L) return ;
  		if(l>=L&&r<=R) {
  			s(p)*=x;Mod(s(p));
  			lp(p)*=x;Mod(lp(p));
  			lm(p)*=x;Mod(lm(p));
  			return ;
  		}
  		spread(p,l,r);
  		changemul(ls,l,mid,L,R,x);
  		changemul(rs,mid+1,r,L,R,x);
  		update(p);
  	}
  	ll ask(int p,int l,int r,int L,int R) {
  		if(l>R||r<L) return 0;
  		if(l>=L&&r<=R) return s(p);
  		spread(p,l,r);
  		ll ans=ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);Mod(ans);
  		return ans;
  	}
}SMT;

---

可持久化线段树

题目：[洛谷P3834] 【模板】可持久化线段树 2（主席树）

学习笔记：主席树学习笔记

class Persistent_SegmentTree{  
  private:  
    struct node{  
        int cnt,lson,rson;  
    }nod[N*Log];  
    #define ls(x) nod[x].lson  
    #define rs(x) nod[x].rson  
    #define c(x) nod[x].cnt  
    #define mid (l+r>>1)  
    void update(int p) {  
        c(p)=c(ls(p))+c(rs(p));  
    }  
  public:  
    void change(int &p,int pre,int l,int r,int x) {
        if(l>x||r<x) return ;  
        p=++tot;  
        nod[p]=nod[pre];  
        if(l==r) {  
            c(p)++;  
            return ;  
        }  
        change(ls(p),ls(pre),l,mid,x);  
        change(rs(p),rs(pre),mid+1,r,x);  
        update(p);  
    }  
    int ask(int p,int q,int l,int r,int k) { 
        if(l==r) return l;  
        int lcnt=c(ls(p))-c(ls(q));  
        if(lcnt>=k) return ask(ls(p),ls(q),l,mid,k);  
        return ask(rs(p),rs(q),mid+1,r,k-lcnt);  
    }  
}PSMT;  

---

Treap

题目：[洛谷P3369] 【模板】普通平衡树

学习笔记：Treap学习笔记

int n,root,tot=0;
class Treap{
  private:
  	struct node{
  		int lson,rson,value,data,size,cnt;
  		#define ls(x) nod[x].lson
  		#define rs(x) nod[x].rson
  		#define v(x) nod[x].value
  		#define d(x) nod[x].data
  		#define s(x) nod[x].size
  		#define c(x) nod[x].cnt
  	}nod[N];
  	inline int New(int val) {
		v(++tot)=val;
		d(tot)=rand();
		c(tot)=s(tot)=1;
		return tot;
	}
	inline void update(int p) {
		s(p)=s(ls(p))+s(rs(p))+c(p);
	}
	inline void lturn(int &p) {
		int q=rs(p);
		rs(p)=ls(q),ls(q)=p,p=q;
		update(ls(p));
		update(p);
	}
	inline void rturn(int &p) {
		int q=ls(p);
		ls(p)=rs(q),rs(q)=p,p=q;
		update(rs(p));
		update(p);
	}
  public:
  	void build() {
  		New(-INF),New(INF);
  		root=1,rs(1)=2;
  		update(root);
  	}
  	void insert(int &p,int val) {
  		if(!p) {
  			p=New(val);
  			return ;
  		}
  		if(val==v(p)) {
  			c(p)++;
  			update(p);
  			return ;
  		}
  		if(val<v(p)) {
  			insert(ls(p),val);
  			if(d(p)<d(ls(p))) rturn(p);
  		}
  		else {
  			insert(rs(p),val);
  			if(d(p)<d(rs(p))) lturn(p);
  		}
  		update(p);
  	}
  	void remove(int &p,int val) {
  		if(!p) return ;
  		if(val==v(p)) {
  			if(c(p)>1) {
  				c(p)--;
  				update(p);
  				return ;
  			}
  			if(ls(p)||rs(p)) {
  				if(!rs(p)||d(ls(p))>d(rs(p))) rturn(p),remove(rs(p),val);
  				else lturn(p),remove(ls(p),val);
  				update(p);
  			}
  			else p=0;
  			return ;
  		}
  		if(val<v(p)) remove(ls(p),val);
  		else remove(rs(p),val);
  		update(p);
  	}
  	int getrank(int p,int val) {
  		if(!p) return 0;
  		if(val==v(p)) return s(ls(p))+1;
  		if(val<v(p)) return getrank(ls(p),val);
  		return s(ls(p))+c(p)+getrank(rs(p),val);
  	}
  	int getval(int p,int rank) {
  		if(s(ls(p))>=rank) return getval(ls(p),rank);
  		if(s(ls(p))+c(p)>=rank) return v(p);
  		return getval(rs(p),rank-s(ls(p))-c(p));
  	}
  	int getpre(int p,int val) {
  		if(!p) return -INF;
  		if(val<=v(p)) return getpre(ls(p),val);
  		return max(v(p),getpre(rs(p),val));
  	}
  	int getnext(int p,int val) {
  		if(!p) return INF;
  		if(val>=v(p)) return getnext(rs(p),val);
  		return min(v(p),getnext(ls(p),val));
  	}
}TP;

---

无旋Treap（Fhq Treap）

题目：[洛谷P3369] 【模板】普通平衡树

学习笔记：Fhq Treap学习笔记

class Fhq_treap{
  private:
    struct node{
        int lson,rson,size,value,data;
        #define ls(x) nod[x].lson
        #define rs(x) nod[x].rson
        #define s(x) nod[x].size
        #define v(x) nod[x].value
        #define d(x) nod[x].data
    }nod[N];
    inline int New(int val) { 
        v(++tot)=val;
        s(tot)=1;
        d(tot)=rand();
        return tot;
    }
    inline void update(int p) {
        s(p)=s(ls(p))+s(rs(p))+1;
    }
    void split(int p,int k,int &x,int &y) {
        if(!p) {
            x=y=0;
            return ;
        }
        if(v(p)<=k) x=p,split(rs(p),k,rs(p),y);
        else y=p,split(ls(p),k,x,ls(p));
        update(p);
    }
    int merge(int x,int y) {
        if(!x||!y) return x+y;
        if(d(x)>d(y)) {
            rs(x)=merge(rs(x),y);
            update(x);
            return x;
        } 
        else {
            ls(y)=merge(x,ls(y));
            update(y);
            return y;
        }
    }
  public:
    void insert(int val) {
        split(root,val,x,y);
        root=merge(merge(x,New(val)),y);
    }
    void remove(int val) {
        split(root,val,x,z);
        split(x,val-1,x,y);
        y=merge(ls(y),rs(y));
        root=merge(merge(x,y),z);
    }
    int getrank(int val) {
        split(root,val-1,x,y);
        int ans=s(x)+1;
        root=merge(x,y);
        return ans;
    }
    int getval(int p,int rank) {
        if(rank<=s(ls(p))) return getval(ls(p),rank);
        else if(rank==s(ls(p))+1) return v(p);
        else return getval(rs(p),rank-s(ls(p))-1);
    }
    int getpre(int val) {
        split(root,val-1,x,y);
        int ans=getval(x,s(x));
        root=merge(x,y);
        return ans;
    }
    int getnext(int val) {
        split(root,val,x,y);
        int ans=getval(y,1);
        root=merge(x,y);
        return ans;
    }
}FTP;

---

分块

题目：[LOJ#6283] 数列分块入门 7 区间加，区间乘。

学习笔记：分块学习笔记

#include<bits/stdc++.h>
#define mod 10007
#define N 100010
#define ll long long 

using namespace std;

int n,L[N],R[N],pos[N],t;
ll add[N],a[N],mul[N];

void init() {
	t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	R[t]=n;
	for(int i=1;i<=t;i++) {
		mul[i]=1;
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
	}
}

void reset(int x) {
	for(int i=L[x];i<=R[x];i++) a[i]=(a[i]*mul[x]+add[x])%mod;
	mul[x]=1,add[x]=0;
}

void change_mul(int l,int r,ll c) {
	int p=pos[l],q=pos[r];
	if(p==q) {
		reset(p);
		for(int i=l;i<=r;i++) a[i]=(a[i]*c)%mod;
	}
	else {
		reset(p);
		for(int i=l;i<=R[p];i++) a[i]=(a[i]*c)%mod;
		for(int i=p+1;i<q;i++) mul[i]=(mul[i]*c)%mod,add[i]=(add[i]*c)%mod;
		reset(q);
		for(int i=L[q];i<=r;i++) a[i]=(a[i]*c)%mod;
	}
}

void change_add(int l,int r,ll c) {
	int p=pos[l],q=pos[r];
	if(p==q) {
		reset(p);
		for(int i=l;i<=r;i++) a[i]=(a[i]+c)%mod;
	}
	else {
		reset(p);
		for(int i=l;i<=R[p];i++) a[i]=(a[i]+c)%mod;
		for(int i=p+1;i<q;i++) add[i]=(add[i]+c)%mod;
		reset(q);
		for(int i=L[q];i<=r;i++) a[i]=(a[i]+c)%mod;
	}
}

ll ask(int x) {
	return (a[x]*mul[pos[x]]+add[pos[x]])%mod;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]%=mod;
	
	init();
	for(int i=1;i<=n;i++) {
		int opt,l,r;
		ll c;
		scanf("%d%d%d%lld",&opt,&l,&r,&c);
		if(!opt) change_add(l,r,c);
		else if(opt&1) change_mul(l,r,c);
		else printf("%lld\n",ask(r));
	}
	
	return 0;
}

题目：[LOJ#6278] 数列分块入门 2 区间加，区间查询小于 $x$ 个数。

#include<bits/stdc++.h>
#define N 50010
#define ll long long 

using namespace std;

int n,L[N],R[N],pos[N],add[N],a[N],b[N];

void init() {
	int t=sqrt(n);
	for(int i=1;i<=t;i++) L[i]=(i-1)*t+1,R[i]=i*t;
	R[t]=n;
	for(int i=1;i<=t;i++) {
		sort(b+L[i],b+R[i]+1);
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
	}
}

void reset(int x) {
	for(int i=L[x];i<=R[x];i++) b[i]=a[i];
	sort(b+L[x],b+R[x]+1);
}

void change(int l,int r,int c) {
	if(pos[l]==pos[r]) {
		for(int i=l;i<=r;i++) a[i]+=c;
		reset(pos[l]);
	}
	else {
		for(int i=l;i<=R[pos[l]];i++) a[i]+=c;
		reset(pos[l]);
		for(int i=pos[l]+1;i<pos[r];i++) add[i]+=c;
		for(int i=L[pos[r]];i<=r;i++) a[i]+=c;
		reset(pos[r]);
	}
}

int ask(int l,int r,int c) {
	int ans=0;
	if(pos[l]==pos[r]) {
		for(int i=l;i<=r;i++) if(a[i]<c-add[pos[l]]) ans++;
	}
	else {
		for(int i=l;i<=R[pos[l]];i++) if(a[i]<c-add[pos[l]]) ans++;
		for(int i=pos[l]+1;i<pos[r];i++) ans+=lower_bound(b+L[i],b+R[i]+1,c-add[i])-(b+L[i]);
		for(int i=L[pos[r]];i<=r;i++) if(a[i]<c-add[pos[r]]) ans++;
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
	
	init();
	for(int i=1;i<=n;i++) {
		int opt,l,r,c;
		scanf("%d%d%d%d",&opt,&l,&r,&c);
		if(opt) printf("%d\n",ask(l,r,c*c));
		else change(l,r,c);
	}
	
	return 0;
}

---

莫队

学习笔记：莫队学习笔记

struct query{		//离线询问
	int l,r,id,pos;
	bool operator < (const query &x)const{
		return (pos^x.pos)?l<x.l:((pos&1)?r<x.r:r>x.r);				//奇偶优化
	}
/*    bool operator < (const query &x)const{			//非奇偶优化
		if(pos==x.pos) return r<x.r;
		return pos<x.pos;
	}*/
}q[N];

void init() {
	blo=sqrt(n);			//块的大小根据题意
	for(int i=1;i<=m;i++) {
		q[i].l=read(),q[i].r=read();
		q[i].id=i,q[i].pos=(q[i].l-1)/blo+1;
	}
}

inline void add(int x) {
    //do sth
}

inline void del(int x) {
	//do sth
}

int main() {
    ...........
    for(int i=1;i<=m;i++) {
		while(l>q[i].l) l--,add(l);
		while(r<q[i].r) r++,add(r);
		while(l<q[i].l) del(l),l++;
		while(r>q[i].r) del(r),r--;
		Ans[q[i].id]=ans;
	}
}

---

图论

SPFA

ll dis[N];
bool vh[N];
void SPFA(int s) {
    memset(vh,false,sizeof(vh));
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    dis[s]=0;
    q.push(s);
    vh[s]=true;
    while(!q.empty()) {
        int u=q.front();q.pop();
        vh[u]=false;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v;
            ll w=edge[i].w;
            if(dis[u]<dis[v]-w) {
                dis[v]=dis[u]+w;
                if(!vh[v]) {
                    vh[v]=true;
                    q.push(v);
                }
            }
        }
    }
}

---

堆优化Dijkstra

struct node{
    int id;
    ll d;
    bool operator < (const node &x)const {
        return d>x.d;
    }
};
ll dis[N];
bool vh[N];
void Dijkstra(int s) {
    memset(vh,false,sizeof(vh));
    memset(dis,0x3f,sizeof(dis));
    priority_queue<node> q;
    dis[s]=0;
    q.push(node{s,0});
    while(!q.empty()) {
        int u=q.top().id;q.pop();
        if(vh[u]) continue;
        vh[u]=true;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v;
            ll w=edge[i].w;
            if(!vh[v]&&dis[u]<dis[v]-w) {
                dis[v]=dis[u]+w;
                q.push(node{v,dis[v]});
            }
        }
    }
}

---

堆优化Prim

struct node{
	int id,d;
	bool operator < (const node &x)const {
		return d>x.d;
	}
};
int d[N],ans=0;
bool vh[N];
void prim() {
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	priority_queue<node> q;
	q.push(node{1,0});
	while(!q.empty()) {
		int u=q.top().id;
		q.pop();
		if(vh[u]) continue;
		vh[u]=true;
		ans+=d[u];
		for(int i=head[u];i;i=edge[i].next) {
			int v=edge[i].v,w=edge[i].w;
			if(!vh[v]&&d[v]>w) {
				d[v]=w;
				q.push(node{v,d[v]});
			}
		}
	}
}

---

Kruskal

int n,m,ans=0;
int head[N],tot=0;
struct graph{
	int u,v,w;
	bool operator < (const graph &x)const {
		return w<x.w;
	}
}edge[MAXN];
int vset[N];
int find(int x) {
	if(x==vset[x]) return x;
	return vset[x]=find(vset[x]);
}
void kruskal() {
	int js=0;
	for(int i=1;i<=n;i++) vset[i]=i;
	for(int i=1;i<=m;i++) {
		int fu=find(edge[i].u),fv=find(edge[i].v),w=edge[i].w;
		if(fu==fv) continue;
		js++;
		vset[fv]=fu;
		ans+=w;
		if(js==n-1) break;
	}
}

---

强连通分量（Tarjan）

int n,m,tot=0,head[N],dfn[N],low[N],sccid[N],stk[N],top=0,cnt=0,num=0,out[N],ans=0;
struct graph{
	int v,next;
}edge[MAXN];
vector<int> scc[N];
bool vh[N];
//scc储存强连通分量内的点。
void add(int u,int v) {edge[++tot].v=v;edge[tot].next=head[u];head[u]=tot;}
void Tarjan(int u) {
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	vh[u]=true;
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v;
		if(!dfn[v]) {
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vh[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		num++;
		while(vh[u]) {
			int v=stk[top--];
			vh[v]=false;
			scc[num].push_back(v);
			sccid[v]=num;
		}
	}
}

---

割点和桥（Tarjan）

int n,m,head[N],tot=1,dfn[N],low[N],cnt=0,ans=0,root;
struct graph{
	int v,next;
}edge[N<<1];
bool bridge[N<<1],cut[N];
// bridge标记边是否为桥，cut标记点是否为割点。
void add(int u,int v) {edge[++tot].v=v;edge[tot].next=head[u];head[u]=tot;}
void Tarjan(int u,int id) {
	dfn[u]=low[u]=++cnt;
	int js=0;
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v;
		if(!dfn[v]) {
			Tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=true;
			if(low[v]>=dfn[u]) {
				js++;
				if((u!=root||js>1)&&!cut[u]) cut[u]=true,ans++;
			}
		}
		else if(i!=(id^1)) low[u]=min(low[u],dfn[v]);
	}
}

---

树论

LCA（倍增）

int depth[N],fa[N][Log],lg[N];
void dfs(int u) {
    for(int i=1;i<=lg[depth[u]];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa[u][0]) continue;
        fa[v][0]=u,depth[v]=depth[u]+1;
        dfs(v);
    }
}
int LCA(int x,int y) {
    if(depth[x]<depth[y]) swap(x,y);
    while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]];
    if(x==y) return x;
    for(int i=lg[depth[x]];~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void init() {
    lg[0]=-1;
    for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
    dfs(s);
}

---

树链剖分

题目： [洛谷P4114] Qtree1

学习笔记：树剖学习笔记

int n,tot=0,cnt=0;
int head[N],val[N],fa[N],son[N],size[N],depth[N],id[N],rk[N],top[N],ep[N];
struct graph{  
    int u,v,next,w;  
}edge[N<<1];
void add(int u,int v,int w) {  
    edge[++tot].u=u;  
    edge[tot].v=v;  
    edge[tot].w=w;  
    edge[tot].next=head[u];  
    head[u]=tot;  
}
class SegmentTree{  
  private:  
    int maxn[N<<2];  
    #define m(x) maxn[x]  
    #define ls (p<<1)  
    #define rs (ls|1)  
    #define mid (l+r>>1)  
    inline void update(int p) {  
        m(p)=max(m(ls),m(rs));  
    }  
  public:  
    void build(int p,int l,int r) {  
        if(l==r) {  
            m(p)=val[rk[l]];  
            return ;  
        }  
        build(ls,l,mid);  
        build(rs,mid+1,r);  
        update(p);  
    }  
    void change(int p,int l,int r,int x,int y) {  
        if(l==r) {  
            m(p)=y;  
            return ;  
        }  
        if(x<=mid) change(ls,l,mid,x,y);  
        else change(rs,mid+1,r,x,y);  
        update(p);  
    }  
    int ask(int p,int l,int r,int L,int R) {  
        if(l>R||r<L) return 0;  
        if(l>=L&&r<=R) return m(p);  
        return max(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R));  
    }  
}T;  

void dfs_first(int u) {  
    depth[u]=depth[fa[u]]+1;  
    size[u]=1;  
    for(int i=head[u];i;i=edge[i].next) {  
        int v=edge[i].v;  
        if(v==fa[u]) continue;  
        fa[v]=u;  
        dfs_first(v);  
        size[u]+=size[v];  
        if(size[v]>size[son[u]]) son[u]=v;  
    }  
}  
  
void dfs_second(int u,int t) {  
    if(!u) return ;  
    top[u]=t;  
    id[u]=++cnt;  
    rk[cnt]=u;  
    dfs_second(son[u],t);  
    for(int i=head[u];i;i=edge[i].next) {  
        int v=edge[i].v;  
        if(v!=fa[u]&&v!=son[u]) dfs_second(v,v);  
    }  
}  
  
void init() {  
    dfs_first(1);  
    dfs_second(1,1);  
    for(int i=1;i<=tot;i+=2) {  
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;  
        fa[v]==u?(val[v]=w,ep[(i>>1)+1]=v):(val[u]=w,ep[(i>>1)+1]=u);  
    }  
    T.build(1,1,n);  
} 

---

点分治

题目：[洛谷P3806]【模板】点分治1

学习笔记：点分治学习笔记

int n,m,k[N];
bool vh[N],flag[N];
int size[N],maxn[N],root=0,a[N],b[N],d[N],cnt;
bool cmp(int x,int y) {
	return d[x]<d[y];
}
void get_root(int u,int fa,int S) {
	size[u]=1,maxn[u]=0;
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v;
		if(v==fa||vh[v]) continue;
		get_root(v,u,S);
		size[u]+=size[v];
		maxn[u]=max(maxn[u],size[v]);
	}
	maxn[u]=max(maxn[u],S-size[u]);
	if(!root||maxn[u]<maxn[root]) root=u;
}
void get_db(int u,int fa) {
	a[++cnt]=u;
	b[u]=b[fa];
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v,w=edge[i].w;
		if(v==fa||vh[v]) continue;
		d[v]=d[u]+w;
		get_db(v,u);
	}
}
void calc(int u) {
	cnt=0;
	a[++cnt]=u;
	d[u]=0;
	b[u]=u;
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v,w=edge[i].w;
		if(vh[v]) continue;
		b[v]=v,d[v]=w;
		get_db(v,v);
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=1;i<=m;i++) {
		if(flag[i]) continue;
		int l=1,r=cnt;
		while(l<r) {
			if(d[a[l]]+d[a[r]]>k[i]) r--;
			else if(d[a[l]]+d[a[r]]<k[i]) l++;
			else if(b[a[l]]==b[a[r]]) {
				if(d[a[r]]==d[a[r-1]]) r--;
				else l++;
			}
			else {
				flag[i]=true;
				break;
			}
		}
	}
}
void solve(int u) {
	vh[u]=true;
	calc(u);
	for(int i=head[u];i;i=edge[i].next) {
		int v=edge[i].v,w=edge[i].w;
		if(vh[v]) continue;
		root=0;
		get_root(v,v,size[v]);
		solve(root);
	}
}

---

字符串

Hash

const ull PP=131;
int n,m,l;
char s[N];
ull H[N],P[N];
ull BKDRHash(char *s) {					//计算一个字符串的哈希值
    ull P=131,H=0;
    while(*s) H=H*P+(*s++);
    return H;
}
ull get_hash(int l,int r) {					//求某个子区间的哈希值
    return H[r]-H[l-1]*P[r-l+1];
}
void init() {							//预处理
    n=strlen(s+1);
    P[0]=1;
    for(int i=1;i<=n;i++) P[i]=P[i-1]*PP;
    for(int i=1;i<=n;i++) H[i]=H[i-1]*PP+s[i];
}

---

Manacher

char a[N],s[N<<1];
int n,P[N<<1],ans=0;

void init() {
    n=strlen(a);
    int m=0;
    s[m++]='$',s[m++]='#';
    for(int i=0;i<n;i++) s[m++]=a[i],s[m++]='#';
    s[m++]='&';
    n=m;
}

void Manacher() {
    int R=0,C;
    for(int i=1;i<n;i++) {
        if(i<R) P[i]=min(P[(C<<1)-i],R-i);
        else P[i]=1;
        while(s[i+P[i]]==s[i-P[i]]) P[i]++;
        if(P[i]+i>R) {
            R=P[i]+i;
            C=i;
        }
        ans=max(ans,P[i]-1);
    }
}

字典树

#include<bits/stdc++.h>
#define N 55
#define M 500010

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;
char s[N];

int tot=0;
struct Trie{
    bool rpt,v;
    int son[26],num;
}t[M];
void Insert(char *s) {
    int now=0;
    for(int i=0;s[i];i++) {
        int ch=s[i]-'a';
        if(!t[now].son[ch]) t[now].son[ch]=++tot;
        now=t[now].son[ch];
        t[now].num++;
    }
    t[now].v=true;
}
int Find(char *s) {
    int now=0;
    for(int i=0;s[i];i++) {
        int ch=s[i]-'a';
        if(!t[now].son[ch]) return 3;
        now=t[now].son[ch];
    }
    if(t[now].num==0||!t[now].v) return 3;
    if(!t[now].rpt) {
        t[now].rpt=true;
        return 1;
    }
    return 2;
}

void solve() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%s",&s);
        Insert(s);
    }
    scanf("%d",&m);
    while(m--) {
        scanf("%s",&s);
        int res=Find(s);
        if(res==1) printf("OK\n");
        else if(res==2) printf("REPEAT\n");
        else printf("WRONG\n");
    }
}

int main() {
    solve();    
    return 0;
}