常用板
零. 写在前面
- 请将数组开到合适大小。
- 请考虑是否开
long long。 - 文章内容较多，可使用 Ctrl + F 快速定位。
一. 优化
1. 快读快写
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void write(ll x){
if (x<0){putchar('-'); x = -x;}
if (x>9)write(x / 10);
putchar(x % 10 + '0');
}
2. cin/cout优化
std::ios::sync_with_stdio(false);
cin.tie(NULL);cout.time(NULL);
二. 数论
1. 快速幂取模
int quickpow(int a,int b,int mod){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;b>>=1;
}
return res;
}
2. 龟速乘
ll slowmul(ll a,ll b){
a=a%m;b=b%m; ll res=0;
while(b){
if(b&1) res=(res+a)%mod;
a=(a+a)%mod; b>>=1;
}
return res;
}
3. GCD与LCM
int gcd(int a,int b){
return b==0?a:gcd(b,a/b);
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
4. 扩展欧几里得定理
int exgcd(int a,int b,int&x,int&y){
if(!b){x=1,y=0;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
5. 组合数取模
int fac[N],inv[N];
void init(){
fac[0]=fac[1]=1;
for(int i=2;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=quickpow(fac[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=(1ll*inv[i+1]*(i+1))%mod;
}
int C(int a,int b){
return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
5.1. Lucas 定理
int lucas(int n,int m){
if(m==0) return 1;
else return 1ll*C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
6. 欧拉筛
bool vst[N];
int prime[N],cnt;
void sieve(){
for(int i=2;i<=n;i++){
if(!vst[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&1ll*prime[j]*i<=n;j++){
notprime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
return ;
}
7. 求逆元
7.1. 线性求逆元
void inverse(){
inv[1]=1;
for(int i=1;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
7.2. 求单个逆元
int inverse(int a,int m){
int x,int y; exgcd(a,m,x,y);
return (x%mod+mod)%mod;
}
8. 矩阵快速幂
struct matrix{int num[N][N];};
matrix operator*(const matrix&a,const matrix&b){
matrix c; memset(c.num,0,sizeof(c.num));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j]%mod)%mod;
}
}
}
return c;
}
matrix matrixpow(matrix a,int b){
matrix ans; memset(ans.num,0,sizeof(ans));
for(int i=1;i<=n;i++) ans.num[i][i]=1;
while(b){
if(b&1) ans=ans*a;
a=a*a; b>>=1;
}
return ans;
}
9. 高斯-约当消元
void gauss(){
for(int i=1;i<=n;i++){
int maxn=i;
for(int j=i+1;j<=n;j++){
if(fabs(a[j][i])>fabs(a[maxn][i])) maxn=j;
}
for(int j=1;j<=n+1;j++) swap(a[i][j],a[maxn][j]);
if(fabs(a[i][i])<eps){cout<<"No solution";return ;}
for(int j=n+1;j>=1;j--) a[i][j]=a[i][j]/a[i][i];
for(int j=1;j<=n;j++){
if(j==i) continue;
double t=a[j][i]/a[i][i];
for(int k=1;k<=n+1;k++) a[j][k]-=a[i][k]*t;
}
}
for(int i=1;i<=n;i++) cout<<a[i][n+1]<<endl;
return ;
}
9.1 矩阵求逆
void gauss(){
for(int i=1;i<=n;i++){
int maxn=i;
for(int j=i+1;j<=n;j++){
if(a[j][i]>a[maxn][i]) maxn=j;
}
for(int j=1;j<=n*2;j++) swap(a[i][j],a[maxn][j]);
if(a[i][i]==0){cout<<"No Solution";return ;}
ll inv=inverse(a[i][i],mod);
for(int j=1;j<=n;j++){
if(i==j) continue;
int t=a[j][i]*inv%mod;
for(int k=i;k<=2*n;k++) a[j][k]=((a[j][k]-t*a[i][k])%mod+mod)%mod;
}
for(int j=1;j<=n*2;++j) a[i][j]=(a[i][j]*inv%mod);
}
for(int i=1;i<=n;i++){
for(int j=n+1;j<=n*2;j++) cout<<a[i][j]<<" ";
cout<<endl;
}
return ;
}
10. 求欧拉函数
10.1. 求单个欧拉函数
ll euler(ll x){
ll res=x;
for(ll i=2;i*i<=x;i++){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x!=1) res=res/x*(x-1);
return res;
}
10.2. 线性求欧拉函数
void get_phi(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vst[i]){
vst[i]=1;prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
vst[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
三. 高精度
1. 高精度加法
string add(string a,string b){
ll la=a.size(),lb=b.size(),lc=max(la,lb);
ll na[N]={0},nb[N]={0},nc[N]={0};
string c="";
for(int i=la,j=0;i>=1;i--,j++) na[i]=a[j]-'0';
for(int i=lb,j=0;i>=1;i--,j++) nb[i]=b[j]-'0';
for(int i=1;i<=lc;i++){
nc[i]+=(na[i]+nb[i]);
if(nc[i]>=10) nc[i+1]++,nc[i]-=10;
}
if(nc[lc+1]) lc++;
for(int i=lc;i>=1;i--) c+=(nc[i]+'0');
return c;
}
2. 高精度减法
string minus(string a,string b){
bool flag=0;
if(b.size()>a.size()||a.size()==b.size()&&a<b){
swap(a,b);
flag=1;
}
ll la=a.size(),lb=b.size(),lc=la;
ll na[10009]={0},nb[10009]={0},nc[10009]={0};
string c="";
if(flag) c+='-';
for(int i=0,j=la;i<la;i++,j--) na[j]=a[i]-'0';
for(int i=0,j=lb;i<lb;i++,j--) nb[j]=b[i]-'0';
for(int i=1;i<=la;i++){
nc[i]=na[i]-nb[i];
if(nc[i]<0) nc[i]+=10,na[i+1]--;
}
while(nc[lc]==0&&lc>1) lc--;
for(int i=lc;i>=1;i--) c+=(nc[i]+'0');
return c;
}
3. 高精度乘法
string mul(string a,string b){
ll la=a.size(),lb=b.size(),lc=la+lb;
ll na[N]={0},nb[N]={0},nc[N]={0};
string c="";
for(int i=0,j=la;j>=1;i++,j--) na[j]=a[i]-'0';
for(int i=0,j=lb;j>=1;i++,j--) nb[j]=b[i]-'0';
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++) nc[i+j-1]+=(na[i]*nb[j]);
}
for(int i=1;i<=lc;i++){
if(nc[i]>=10){
nc[i+1]+=nc[i]/10;
nc[i]%=10;
}
}
while(nc[lc]==0&&lc>1) lc--;
for(int i=lc;i>=1;i--) c+=(nc[i]+'0');
return c;
}
4. 高精度除法
string divide(string a,ll b){
ll na[N]={0},nb[N]={0},nc[N]={0};
ll res=0;
string c="";
for(int i=0;i<a.size();i++) na[i]=a[i]-'0';
for(int i=0;i<a.size();i++){
res=res*10+na[i];
nc[i]=res/b;
res%=b;
}
ll i=0;
while(nc[i]==0&&i<a.size()) i++;
if(i==a.size()) return "0";
for(;i<a.size();i++) c+=(nc[i]+'0');
return c;
}
5. 高精度取模
int getmod(string a,int b){
int res=0;
for(int i=0;i<a.size();i++) res=(res*10+(a[i]-'0'))%b;
return res;
}
四. 数据结构
1. 并查集
int id[N];
int root(int x){return id[x]==x?x:id[x]=root(id[x]);}
void unite(int x,int y){
int fx=root(x),fy=root(y);
id[fx]=fy;
return ;
}
2. 树状数组
int bit[N];
int lsb(ll x){return x&(-x);}
void add(int x,int p){
while(x<=n){bit[x]+=p;x+=lsb(x);}
return ;
}
int query(int x){
int ans=0;
while(x){ans+=bit[x];x-=lsb(x);}
return ans;
}
2.1. 区间修改单点查询
void LSB(int x){return x&(-x);}
void add(int x,int d){
while(x<=n){BIT[x]+=d;x+=LSB(x);}
}
void change(int l,int r,int d){add(l,d);add(r+1,-d);}
int query(int x){
int ans=0;
while(x){ans+=BIT[x];x-=LSB(x);}
return ans;
}
2.2. 区间修改区间查询
void add(int x,int d1,int d2){
while(x<=n){
BIT1[x]+=d1; BIT2[x]+=d2;
x+=LSB(x);
}
}
int query1(int x){
int ans=0;
while(x){ans+=BIT1[x];x-=LSB(x);}
return ans;
}
int query2(int x){
int ans=0;
while(x){ans+=BIT2[x];x-=LSB(x);}
return ans;
}
void update(int l,int r,int d){
add(l,d,d*(l-1));
add2(r+1,-d,-d*r);
}
void query(int l,int r){
return r*query1(r)-query2(r)-(l-1)*query(l-1)+query2(l-1);
}
2.3. 二维区间修改区间查询
void add(int x,int y,int d){
for(int i=x;i<=n;i+=LSB(i)){
for(int j=y;j<=m;j+=LSB(j)){
t1[i][j]+=d; t2[i][j]+=x*d;
t3[i][j]+=y*d; t4[i][j]+=x*y*d;
}
}
}
void update(int a,int b,int c,int d,int delta){
add(a,b,delta); add(c+1,d+1,delta);
add(a,d+1,-delta); add(c+1,b,-delta);
}
int sum(int x,int y){
int ans=0;
for(int i=x;i;i-=LSB(i)){
for(int j=y;j;j-=LSB(j)){
ans+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];
}
}
return ans;
}
void query(int a,int b,int c,int d){
return sum(c,d)+sum(a-1,b-1)-sum(c,b-1)-sum(a-1,d);
}
2.4. 康托展开
int cantor(){
fac[0]=1; int res=0;
for(int i=1;i<=n;i++) fac[i]=(fac[i-1]*i)%MOD;
for(int i=n;i>=1;i--){cnt[i]=query(a[i]-1);add(a[i],1);}
for(int i=1;i<=n;i++) res=(res+(cnt[i]*jc[n-i])%MOD)%MOD;
return res;
}
3. ST表
ll LOG2[N],st[N][N];
void init(){
LOG2[1]=0;
for(int i=1;i<=n;i++) LOG2[i]=LOG2[i>>1]+1;
}
void ST(){
for(int i=1;i<=n;i++) st[0][1]=x[i];
ll p=LOG2[n]/LOG2[2];
for(int k=1;k<=p;k++){
for(int i=1;i<=n-(1<<k)+1;i++){
st[k][i]=max(st[k-1][i],st[k-1][i+(1<<(k-1))]);
}
}
}
ll query(ll l,ll r){
ll p=LOG2[r-l+1]/LOG2[2];
return max(st[p][l],st[p][r-(1<<p)+1]);
}
4. 线段树
struct segment_tree{
int l,r,sum,tag;
}tree[N*4];
void pushup(int p){
int ls=p*2,rs=p*2+1;
tree[p].sum=tree[ls].sum+tree[rs].sum;
}
void pushdown(int p){
int ls=p*2,rs=p*2+1;
tree[ls].sum+=(tree[p].tag*(tree[ls].r-tree[ls].l+1));
tree[rs].sum+=(tree[p].tag*(tree[rs].r-tree[rs].l+1));
tree[ls].tag+=tree[p].tag;
tree[rs].tag+=tree[p].tag;
tree[p].tag=0;
}
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r,tree[p].tag=0;
if(l==r){tree[p].sum=a[l];return ;}
int mid=l+(r-l)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void update(int p,int L,int R,int z){
if(tree[p].l>=L&&tree[p].r<=R){
tree[p].sum+=c*(tree[p].r-tree[p].l+1);
tree[p].tag+=c;
return ;
}
pushdown(p);
int mid=tree[p].l+(tree[p].r-tree[p].l)/2;
if(mid>=L) update(p*2,L,R,z);
if(mid+1<=R) update(p*2+1,L,R,z);
}
int query(int p,int L,int R){
if(tree[p].l>=L&&tree[p].r<=R) return tree[p].sum;
pushdown(p);
int res=0,mid=tree[p].l+(tree[p].r-tree[p].l)/2;
if(mid>=L) res+=query(p*2,L,R);
if(mid+1<=R) res+=query(p*2+1,L,R);
}
4.1. 扫描线
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1600009;
ll n,cnt,tag[N],len[N],idx[N],ans,num;
struct scanline{
ll y,lx,rx,io;
}line[N];
bool cmp(const scanline&a,const scanline&b){
return a.y<b.y;
}
void pushup(int p,int l,int r){
int ls=p*2,rs=p*2+1;
if(tag[p]) len[p]=idx[r]-idx[l];
else if(l+1==r) len[p]=0;
else len[p]=len[ls]+len[rs];
}
void update(int p,int l,int r,int L,int R,ll add){
if(L<=l&&R>=r){
tag[p]+=add;
pushup(p,l,r);
return ;
}
if(l+1==r) return ;
int mid=l+(r-l)/2;
if(L<=mid) update(p*2,l,mid,L,R,add);
if(R-1>=mid) update(p*2+1,mid,r,L,R,add);
pushup(p,l,r);
return ;
}
int main(){
cin>>n;
for(ll i=1;i<=n;i++){
ll a,b,c,d; cin>>a>>b>>c>>d;
line[++cnt]=((scanline){b,a,c,1});
idx[cnt]=a;
line[++cnt]=((scanline){d,a,c,-1});
idx[cnt]=c;
}
sort(idx+1,idx+1+cnt);
sort(line+1,line+1+cnt,cmp);
num=unique(idx+1,idx+1+cnt)-(idx+1);
for(int i=1;i<=cnt;i++){
int L,R;
ans+=(len[1]*(line[i].y-line[i-1].y));
L=lower_bound(idx+1,idx+num+1,line[i].lx)-idx;
R=lower_bound(idx+1,idx+num+1,line[i].rx)-idx;
update(1,1,num,L,R,line[i].io);
}
cout<<ans;
return 0;
}
4.2. 逆康托展开
void pushup(int p){
int ls=p*2,rs=p*2+1;
t[p].cnt=t[ls].cnt+t[rs].cnt;
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].cnt=1;return ;}
int mid=l+(r-l)/2;
build(p*2,l,mid);build(p*2+1,mid+1,r);
pushup(p);
}
int modify(int p,int x){
if(t[p].l==t[p].r){t[p].cnt=0; return t[p].l;}
int res=0,ls=p*2,rs=p*2+1;
if(x<=t[ls].cnt) res=modify(ls,x);
else res=modify(rs,x-t[ls].cnt);
pushup(p);
return res;
}
4.3 可持久化线段树
struct t{
int ls,rs,val;
}tree[3500009];
int update(int pre,int l,int r,int x){
int t=++cnt;
tree[t].ls=tree[pre].ls;
tree[t].rs=tree[pre].rs;
tree[t].val=tree[pre].val+1;
int mid=l+(r-l)/2;
if(l==r) return t;
if(x<=mid) tree[t].ls=update(tree[pre].ls,l,mid,x);
else tree[t].rs=update(tree[pre].rs,mid+1,r,x);
return t;
}
int query(int l,int r,int L,int R,int k){
if(l>=r) return l;
int x=tree[tree[R].ls].val-tree[tree[L].ls].val;
int mid=l+(r-l)/2;
if(x>=k) return query(l,mid,tree[L].ls,tree[R].ls,k);
else return query(mid+1,r,tree[L].rs,tree[R].rs,k-x);
}
5. 单调队列
l=1,r=1;
for(int i=1;i<=n;i++){
while(l<r&&i-q[l]>=k) l++;
while(l<r&&x[i]>x[q[r-1]]) r--;
q[r++]=i;
maxn[i]=x[q[l]];
}
//最大值
l=1,r=1;
for(int i=1;i<=n;i++){
while(l<r&&i-q[l]>=k) l++;
while(l<r&&x[i]<x[q[r-1]]) r--;
q[r++]=i;
minn[i]=x[q[l]];
}
//最小值
6. 平衡树
6.1. FHQ Treap
struct node{
int ls,rs,val,pri,sze;
}tree[N];
void newnode(int x){
t[++cnt].sze=1;t[cnt].ls=t[cnt].rs=0;
t[cnt].val=x;t[cnt].pri=rand();
}
void pushup(int x){
tree[x].sze=tree[ls].sze+tree[rs].sze+1;
}
void split(int u,int x,int&L,int&R){
if(u==0){L=R=0;return ;}
if(tree[u].val<=x){L=u;split(tree[u].rs,x,tree[u].rs,R);}
else{R=u;split(tree[u].ls,x,L,tree[u].ls);}
}
int merge(int L,int R){
if(L==0||R==0) return L+R;
if(tree[L].pri>tree[R].pri){tree[L].rs=merge(tree[L].rs,R);return L;}
else{tree[R].ls=merge(L,tree[R].ls);return R;}
}
void insert(int x){
int L,R;split(root,x,L,R);
newnode(x);
int tr=merge(L,cnt);
root=merge(tr,R);
}
void del(int x){
int L,R,p;
split(root,x,L,R);
split(L,x-1,L,p);
int tr=merge(tree[p].ls,tree[p].rs);
root=merge(merge(L,tr),R);
}
int rank(int x){
int L,R;split(root,x-1,L,R);
int ans=tree[L].sze+1;
root=merge(L,R);
return ans;
}
int kth(int u,int k){
if(k==tree[tree[u].ls].sze+1) return u;
if(k<tree[tree[u].ls].sze) return kth(tree[u].ls,k);
else return kth(tree[u].rs,k-tree[tree[u].ls].sze-1);
}
int pre(int x){
int L,R;split(root,x-1,L,R);
int ans=t[kth(L,t[L].sze)].val;
root=merge(L,R);
return ans;
}
int nxt(int x){
int L,R;split(root,x,L,R);
int ans=t[kth(R,1)].val;
root=merge(L,R);
return ans;
}
6.2 文艺平衡树
struct node{
int pri,val,ls,rs,tag,sze;
}t[100009];
void newnode(int x){
t[++cnt].sze=1;
t[cnt].val=x;t[cnt].pri=rand();
t[cnt].ls=t[cnt].rs=t[cnt].tag=0;
}
void pushdown(int p){
if(t[p].tag){
swap(t[p].ls,t[p].rs);
t[t[p].ls].tag^=1;t[t[p].rs].tag^=1;
t[p].tag=0;
}
}
void update(int p){
t[p].sze=t[t[p].ls].sze+t[t[p].rs].sze+1;
}
void split(int u,int x,int&L,int&R){
if(u==0){L=R=0;return ;}
pushdown(u);
if(t[t[u].ls].sze+1<=x){L=u;split(t[u].rs,x-t[t[u].ls].sze-1,t[u].rs,R);}
else{R=u;split(t[u].ls,x,L,t[u].ls);}
update(u);
}
int merge(int L,int R){
if(L==0||R==0) return L+R;
if(t[L].pri>t[R].pri){
pushdown(L);t[L].rs=merge(t[L].rs,R);
update(L); return L;
}
else{
pushdown(R);t[R].ls=merge(L,t[R].ls);
update(R); return R;
}
}
void flip(int x,int y){
int L,R,p;
split(root,y,L,R);split(L,x-1,L,p);
t[p].tag^=1;
root=merge(merge(L,p),R);
}
void inorder(int u){
if(u==0) return ;
pushdown(u);
inorder(t[u].ls); cout<<t[u].val<<" "; inorder(t[u].rs);
}
7. 树链剖分
void dfs_son(int x,int father){
fa[x]=father; sze[x]=1; dep[x]=dep[fa[x]]+1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x]) continue;
dfs_son(y,x);
sze[x]+=sze[y];
if(sze[y]>sze[son[x]]) son[x]=y;
}
return ;
}
void dfs_top(int x,int topx){
id[x]=++total; top[x]=topx; xid[total]=x;
if(!son[x]) return ;
dfs_top(son[x],topx);
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x]||y==son[x]) continue;
dfs_top(y,y);
}
}
void addtag(int p,int len,int d){
tag[p]+=d;
tree[p]=(tree[p]+d*len)%mod;
}
void pushdown(int p,int l,int r){
if(!tag[p]) return ;
int ls=p*2,rs=p*2+1;
int mid=l+(r-l)/2;
addtag(ls,mid-l+1,tag[p]);
addtag(rs,r-mid,tag[p]);
tag[p]=0;
}
void pushup(int p){
int ls=p*2,rs=p*2+1;
tree[p]=(tree[ls]+tree[rs])%mod;
}
void build(int p,int l,int r){
if(l==r){
tree[p]=a[xid[l]]%mod;
return ;
}
int mid=l+(r-l)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
void update(int p,int l,int r,int L,int R,int d){
if(L<=l&&R>=r){
addtag(p,r-l+1,d);
return ;
}
pushdown(p,l,r);
int mid=l+(r-l)/2;
if(mid>=L) update(p*2,l,mid,L,R,d);
if(mid+1<=R) update(p*2+1,mid+1,r,L,R,d);
pushup(p);
}
ll query(int p,int l,int r,int L,int R){
if(L<=l&&R>=r) return tree[p]%mod;
pushdown(p,l,r);
ll res=0; int mid=l+(r-l)/2;
if(mid>=L) res=(res+query(p*2,l,mid,L,R))%mod;
if(mid+1<=R) res=(res+query(p*2+1,mid+1,r,L,R))%mod;
return res;
}
void update_range(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,1,n,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,1,n,id[x],id[y],z);
}
ll query_range(int x,int y){
ll res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=(res+query(1,1,n,id[top[x]],id[x]))%mod;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=(res+query(1,1,n,id[x],id[y]))%mod;
return res;
}
void update_tree(int x,int k){
update(1,1,n,id[x],id[x]+sze[x]-1,k);
}
ll query_tree(int x){
return query(1,1,n,id[x],id[x]+sze[x]-1)%mod;
}
五. 图论
1. 链式前向星
void addedge(int u,int v,int w){
nxt[++tot]=head[u];head[u]=tot;
to[tot]=v;ver[tot]=w;
}
2. Floyd
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
2.1. bitset 优化 Floyd
bitset<N> d;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(d[i][k]) d[i]|=d[k];
}
}
}
3. Dijkstra堆优化
struct node{
int pos,dst;
bool operator<(const node&x)const{
return dst>x.dst;
}
};
int dst[N];
bool vst[N];
void dijkstra(){
priority_queue<node> q;
memset(d,INF,sizeof(d));
dst[s]=0;
q.push((node){s,0});
while(!q.empty()){
int fnt=q.top().pos; q.pop();
if(vst[fnt.pos]) continue;
vst[fnt.pos]=1;
for(int i=head[fnt];i;i=nxt[i]){
int y=to[i];
if(dst[y]>dst[fnt.pos]+ver[i]){
dst[y]=dst[fnt.pos]+ver[i];
q.push((node){y,dst[y]});
}
}
}
return ;
}
4. SPFA
int dst[N];
bool in[N];
void SPFA(){
memset(dis,INF,sizeof(dis));
queue<int> q;
in[s]=1;dst[s]=0;
q.push(s);
while(!q.empty()){
int fnt=q.front();q.pop();
in[fnt]=0;
for(int i=head[fnt];i;i=nxt[i]){
int y=to[i];
if(dst[y]>dst[fnt]+ver[i]){
dst[y]=dst[fnt]+ver[i];
if(!in[y]){in[y]=1;q.push(y);}
}
}
}
return ;
}
4.1. SPFA判负环
int dst[N],cnt[N];
bool in[N];
void SPFA(){
memset(dis,INF,sizeof(dis));
queue<int> q;
in[s]=1;dst[s]=0;cnt[s]=1;
q.push(s);
while(!q.empty()){
int fnt=q.front();q.pop();
in[fnt]=0;
for(int i=head[fnt];i;i=nxt[i]){
int y=to[i];
if(dst[y]>dst[fnt]+ver[i]){
dst[y]=dst[fnt]+ver[i]; cnt[y]++;
if(cnt[y]>=n+1) return 1;
if(!in[y]){in[y]=1;q.push(y);}
}
}
}
return 0;
}
5. Kruskal
struct edge{int x,y,w;}e[N];
bool cmp(const edge&a,const edge&b){return a.w<b.w;}
void Kruskal(){
int ans=0,res=n;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
if(root(e[i].x)==root(e[i].y)) continue;
ans+=e[i].z;
unite(e[i].x,e[i].y);
tot--;
if(tot==1) return ans;
}
return -1;
}
6. 最近公共祖先
ll p[N][21],dep[N];
void dfs(int x,int fa){
p[x][0]=fa; dep[x]=dep[fa]+1;
for(int i=1;i<=20;i++) p[x][i]=p[p[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
dfs(y,x);
}
return ;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--){
if(dep[p[x][i]]>=dep[y]) x=p[x][i];
}
if(x==y) return x;
for(int i=20;i>=0;i--){
if(p[x][i]!=p[y][i]){x=p[x][i];y=p[y][i];}
}
return p[x][0];
}
7. 图的连通性
7.1. 割点
void tarjan(int x,int fa){
dfn[x]=low[x]=++tot;
int cnt=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(x==fa) cnt++;
else if(low[y]>=dfn[x]&&!flag[x]) flag[x]=1;
}
low[x]=min(low[x],low[y]);
}
if(x==fa&&cnt>1) flag[x]=1;
return ;
}
7.2. 割边
void tarjan(int x,int fa){
dfn[x]=low[x]=++tot;
int cnt=0;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(x==fa) cnt++;
else if(low[y]>dfn[x]&&!flag[x]) flag[x]=1;
}
low[x]=min(low[x],low[y]);
}
if(x==fa&&cnt>1) flag[x]=1;
return ;
}
7.3 缩点
void tarjan(int x){
stk[++top]=x;
dfn[x]=low[x]=++total;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
if(id[y]) continue;
if(!dfn[y]) tarjan(y);
low[x]=min(low[x],low[y]);
}
if(low[x]==dfn[x]){
cnt++;
while(stk[top+1]!=x){
num[cnt].push_back(stk[top]);
id[stk[top]]=cnt;
top--;
}
}
}
8. 拓扑排序
void topo(){
queue<int> q;
for(int i=1;i<=n;i++){
if(in[i]==0) q.push(i);
}
int cnt=0;
while(!q.empty()){
int fnt=q.front();q.pop();
tp[++cnt]=fnt;
for(int i=head[fnt];i;i=nxt[i]){
int y=to[i];in[i]--;
if(in[i]==0) q.push(i);
}
}
return ;
}
六. 字符串
1. Hash
ull hash(string s){
ull P=13131;pow[0]=1;
int n=s.size();
for(int i=0;i<n;i++){
H[i]=H[i-1]*P+(s[i]-'a');
pow[i]=pow[i-1]*P;
}
}
ull get_hash(int l,int r){
return H[r]-H[l-1]*pow[r-l+1];
}
2. 字典树
struct node{
int cnt,end,nxt[26];
}tree[N];
int tot=1;
void insert(string s){
int now=1;
for(int i=0;i<s.size();i++){
if(tree[now].nxt[s[i]-'a']==0) tree[now].nxt[s[i]-'a']=++tot;
now=tree[now].nxt[s[i]-'a'];
tree[now].cnt++;
}
tree[now].end++;
}
int query(string s){
int now=1;
for(int i=0;i<s.size();i++){
if(tree[now].nxt[s[i]-'a']==0) return 0;
now=tree[now].nxt[s[i]-'a'];
}
return tree[now].cnt;
}
3. KMP
void kmp(string s1,string s2){
ll len1=s1.size();
ll len2=s2.size();
for(int i=1;i<len2;i++){
while(pos!=0&&s2[i]!=s2[pos]) pos=kmp[pos];
if(s2[pos]==s2[i]) pos++;
kmp[i+1]=pos;
}
ll pos=0;
for(int i=0;i<len1;i++){
while(pos!=0&&s2[pos]!=s1[i]) pos=kmp[pos];
if(s2[pos]==s1[i]) pos++;
if(pos==len2){
cout<<i-len2+2<<endl;
pos=kmp[pos];
}
}
}
4. Manacher
int manacher(){
int k=0,R=0,C=0;
str[k++]='$'; str[k++]='#';
for(int i=0;i<n;i++){
str[k++]=s[i];
str[k++]='#';
}
str[k++]='&';
n=k;
for(int i=1;i<n;i++){
if(i<R) p[i]=min(p[2*C-i],C+p[C]-i);
else p[i]=1;
while(str[i+p[i]]==str[i-p[i]]) p[i]++;
if(p[i]+i>R){R=p[i]+i;C=i;}
ans=max(ans,p[i]);
}
return ans-1;
}
七. 递推/动态规划
1. 01背包
int f[N],w[N],v[N];
void bb01(){
for(int i=1;i<=n;i++){
for(int j=W;j>=w[j];j--) f[j]=max(f[j],f[j-w[j]]+v[j]);
}
}
2. 完全背包
int f[N],w[N],v[N];
void bbINF(){
for(int i=1;i<=n;i++){
for(int j=w[j];j<=W;j++) f[j]=max(f[j],f[j-w[j]]+v[j]);
}
}
八. 前缀和与差分
1. 二维前缀和
int a[N][N],s[N][N];
void sum(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
return ;
}
九. 更新记录
2023/08/14：优化了排版；重写快速幂，扩欧算法，组合数取模，并查集，树状数组，SPFA及SPFA判负环；新增求逆元，高精度取模，龟速乘，矩阵快速幂，高斯消元法，Manacher。
2023/08/15：优化了排版；合并 树论 与 图论；重写 线段树，Kruskal；增加 链式前向星，Floyd，bitset 优化 Floyd，树状数组拓展，割点，拓扑排序，字典树，FHQ Treap，文艺平衡树，Hash。
2023/08/16：使用 链式前向星 重写 图论 板块，重写 最近公共祖先；增加 树链剖分，割边，缩点，求欧拉函数，Lucas 定理，扫描线，（逆）康托展开。
2023/08/17：增加 可持久化线段树。
203/08/19：修正了几处错误；新增 矩阵求逆。