板子(by Him_shu)

Him_shu · 2025-03-09 14:33:49 · 算法·理论

前言

为Him_shu的板子库

inline int read(){int 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-'0',ch=getchar ();}return x*f;}
void write(int x){if(x<0){putchar ('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return ;}
int qpow(int a,int b){a=(a%mod+mod)%mod;int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

斜率优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5,M=105,inf=1e14,mod=123456789;
int n;
int dp[N],q[N];
int X(int i){return ?;}
int Y(int i){return ?;}
int K(int i){return ?;}
int cmp1(int a,int b,int k){return (Y(b)-Y(a))<=k*(X(b)-X(a));}
int cmp2(int a,int b,int c){return (Y(b)-Y(a))*(X(c)-X(b))>=(Y(c)-Y(b))*(X(b)-X(a));}
void calc(int x,int y){dp[x]=dp[y]+?;}
int work(){
    for(int i=1,ft=1,bk=1;i<=n;i++){
        int l=ft,r=bk,ret;
        while(l<r){
            int mid=(l+r)/2;
            if(cmp1(q[mid],q[mid+1],K(i)))l=mid+1;
            else r=mid-1,ret=mid;
        }
        calc(i,ret);
        while(ft<bk&&cmp2(q[bk-1],q[bk],i))bk--;
        q[++bk]=i;
    }
    return dp[n];
}
signed main(){

    return 0;
}

积性函数线性筛

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) freopen(x".in","r",stdin)
const int N=1e7+5,M=4e3+5,mod=1e9+7;
vector<int>pri;//质数序列
int vis[N],min_p[N],f[N];
//vis表示标记不是质数，min_p表示最小质因子和他的乘方，f是你要筛的东西
void sieve(int m){
    vis[1]=1,min_p[1]=1;
    f[1]=/**/;
    for(int i=2;i<=m;i++){
        if(!vis[i])pri.push_back(i),min_p[i]=i,f[i]=/**/;
        for(auto j:pri){
            if(i*j>m)break;
            vis[i*j]=1;
            if(i%j==0){
                min_p[i*j]=min_p[i]*j;
                if(min_p[i]==i)f[i*j]=/*f(p^(k+1))*/;
                else f[i*j]=f[i/min_p[i]]*f[j*min_p[i]];
                break;
            }
            min_p[i*j]=j,f[i*j]=f[i]*f[j];
        }
    }
}
signed main(){

    return 0;
}

整体二分

void calc(int l,int r,int w){
    if(l<=r) bit.range_add(l,r,w);
    else{
        bit.range_add(l,m,w);
        bit.range_add(1,r,w);
    }
}
//
void solve(int l,int r,vector<pair<int,int>>&qry){
    if(qry.empty())return;
    if(l==r){
        for(auto[,id]:qry)
            ans[id]=l;
        return;
    }
    int mid=(l+r)/2;
    for(int i=l;i<=mid;i++) calc();

    vector<pair<int,int>>qryl,qryr;
    for(auto[w,id]:qry){
    }

    solve(mid+1,r,qryr);
    for(int i=l;i<=mid;i++) calc();
    solve(l,mid,qryl);
}

矩阵乘法

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=101,mod=1e9+7;
inline int read(){int 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-'0',ch=getchar();}return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);} putchar(x%10+'0');return;}
int qpow(int a,int b,int mod){if(b==0){return 1;}int mid=qpow(a,b/2,mod)%mod;if(b&1){return (mid*mid%mod)*a%mod;}return mid*mid%mod;}
struct Max{
    int n,m;
    int a[N][N];
    Max(int n,int m):n(n),m(m){}
    void init(){memset(a,0,sizeof(a));};
    Max operator* (const Max b) const{
        Max c(n,b.m);
        c.init();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=b.m;j++)
                for(int k=1;k<=m;k++)
                    c.a[i][j]+=a[i][k]*b.a[k][j];
        return c;
    }
    Max operator% (int const mod){
        Max b(n,m);
        b.init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                b.a[i][j]=(int)(a[i][j]%mod);
        }
        return b;
    }
    Max operator^ (int cnt){
        Max b(n,m),ans(n,m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                b.a[i][j]=a[i][j];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                ans.a[i][j]=a[i][j];
        }
        int now=1,ctt=cnt-1;
        while(now<=ctt){
            if(ctt&now){
                ans=ans*b%mod;
            }
            now*=2;
            b=b*b%mod;
        }
        return ans;
    }
    int *operator [](const int p)  { return a[p];}
    void print(){
        cout<<"a::\n";
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cout<<a[i][j]<<" ";
            cout<<"\n";
        }
        cout<<"::\n";
    }
    void in(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
    }
};
signed main(){
    Max a(n,n);a_init(a);
    Max b(1,n);
    Max c(1,n);c=b*(a^(k-n+1))%mod;
    return 0;
}

圆方树

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
const int N=4e5+5,M=2e5+5,inf=1e16,mod=1e9+7;
int n,m;
int a,b;
vector<int>g[M];
//圆方树
int dfn[M],low[M],timeid,cnt;
int sk[N],tot;
vector<int>tar[N];
void add_tar(int u,int v){tar[u].push_back(v),tar[v].push_back(u);}
void tarjan(int u,int fa){
    dfn[u]=low[u]=++timeid;
    sk[++tot]=u;
    for(auto v:g[u]){
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                add_tar(u,++cnt);
                do{add_tar(sk[tot],cnt);}while(sk[tot--]!=v);
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
vector<int>node;
int tag=0;
void dfs(int u,int fa){
    if(tag)return;
    if(u==b){
        node.pop_back();
        int ans=inf;
        for(auto i:node)ans=min(ans,i);
        cout<<ans;
        tag=1;
        return;
    }
    for(auto v:g[u]){
        if(v==fa)continue;
        node.push_back(v);
        dfs(v,u);
        node.pop_back();
    }
}
void work(){
    cin>>n;
    while(1){
        int u,v;cin>>u>>v;
        if(u==0&&v==0)break;
        g[u].push_back(v),g[v].push_back(u);
    }
    cin>>a>>b;
    //
    cnt=n;
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i,0);
    //
    dfs(a,0);
    if(!tag)
    cout<<"No solutio";
}
void clear(){}
signed main(){
    int _=1;
    while(_--)work(),clear();
    return 0;
}
/*
2 3 5 6 1 4
*/

RMQ

struct RMQ{
    pair<int,int>dp[N][24],dp2[N][24];
    void RMQ_init(int m,int val[N]){
        for(int i=1;i<=m;i++)
            dp[i][0]=dp2[i][0]={val[i],i};
        for(int j=1;j<24;j++)
            for(int i=1;i+(1<<j)-1<=m;i++)
                dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]),
                dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);                
    }
    int Max_val(int l,int r){
        int lg=__lg(r-l+1);
        return max(dp[l][lg],dp[r-(1<<lg)+1][lg]).first;
    }
    int Max_id(int l,int r){
        int lg=__lg(r-l+1);
        return max(dp[l][lg],dp[r-(1<<lg)+1][lg]).second;
    }
    int Min_val(int l,int r){
        int lg=__lg(r-l+1);
        return min(dp2[l][lg],dp2[r-(1<<lg)+1][lg]).first;
    }
    int Min_id(int l,int r){
        int lg=__lg(r-l+1);
        return min(dp2[l][lg],dp2[r-(1<<lg)+1][lg]).second;
    }
}st_sa,st_h;

K-DTree

https://www.luogu.com.cn/problem/P4148

FFT

https://www.luogu.com.cn/problem/P3803

拉格朗日插值

中心拉格朗日插值:https://www.luogu.com.cn/problem/P4781

连续自然数拉格朗日插：http://ssloj.cn/contest/937/problem/4

SAM(后缀自动机)

https://www.luogu.com.cn/problem/P3804

Treap

#include<bits/stdc++.h>
using namespace std;
#define int long long

mt19937 Rand(time(0));
const int N=1e5+10,inf=1e14;
int n,ans;
int a[N];
struct Treap{
    int tot,rt;
    int val[N];
    int ls[N],rs[N],pri[N],siz[N];
    int l,r,tmp;
    int New(int x){
        tot++,val[tot]=x,pri[tot]=Rand(),siz[tot]=1;
        return tot;
    }
    void up(int x){siz[x]=siz[ls[x]]+siz[rs[x]]+1;}
    void Split(int id,int k,int &x,int &y){
        if(!id){x=y=0;return;}
        if(val[id]<=k)x=id,Split(rs[id],k,rs[id],y);
        else y=id,Split(ls[id],k,x,ls[id]);
        up(id);
    }
    int Merge(int x,int y){
        if(!x||!y)return x+y;
        if(pri[x]<=pri[y])rs[x]=Merge(rs[x],y),up(x);
        else ls[y]=Merge(x,ls[y]),up(y);
        return(pri[x]<=pri[y]?x:y);
    }
    void insert(int x){Split(rt,x-1,l,r),rt=Merge(Merge(l,New(x)),r);}
    void del(int x){
        Split(rt,x-1,l,r);
        Split(r,x,tmp,r);
        tmp=Merge(ls[tmp],rs[tmp]);
        rt=Merge(Merge(l,tmp),r);
    }
    int Rank(int x){
        Split(rt,x-1,l,r);
        int ans=siz[l];
        rt=Merge(l,r);
        return ans;
    }
    int get_val(int x,int k){
        if(k<=siz[ls[x]])
            return get_val(ls[x],k);
        k-=siz[ls[x]]+1;
        return(!k?val[x]:get_val(rs[x], k));
    }
    int get_pre(int x){
        l=r=0;
        Split(rt,x,l,r);
        if(l==0)return inf;
        int ans=get_val(l,siz[l]);
        rt=Merge(l, r);
        return ans;
    }
    int get_suf(int x){
        l=r=0;
        Split(rt,x,l,r);
        if(r==0)return inf;
        int ans=get_val(r,1);
        rt=Merge(l,r);
        return ans;
    }
}t;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i==1)ans+=a[i];
        else ans+=min(llabs(a[i]-t.get_pre(a[i])),llabs(t.get_suf(a[i])-a[i]));
        t.insert(a[i]);
    }
    cout<<ans;
    return 0;
}

同余最短路问题

https://www.luogu.com.cn/problem/T494899

2-SAT

https://www.cnblogs.com/cjjsb/p/9771868.html

点分治

https://www.luogu.com.cn/problem/P4178

树链剖分

https://www.luogu.com.cn/problem/P2590

差分约束/判负环spfa

https://www.luogu.com.cn/problem/P5960

链式前项星

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int head[N];
int n,m,x,y,w,cnt;

struct Edge{
    int to,w,next;
}e[N];

void add(int u,int v,int w){
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}

void print(int u){
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to,w=e[i].w;
        cout<<u<<":"<<v<<":"<<w<<"\n";
    }
}

signed main(){
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    return 0;
}

网络流

最大流_Dinic

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10,M=5e6+10,inf=1e14;
//变量
int n,m,ans;
//Dinic
struct Dinic{
    int s,t;
    int h[N],e[M],ne[M],w[M],idx=1;
    int le[N],it[N];
    Dinic(int s,int t):s(s),t(t){}
    void add(int a,int b,int c){
        e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
        e[++idx]=a,w[idx]=0,ne[idx]=h[b],h[b]=idx;
    }
    int bfs(int s){
        memset(le,0,sizeof(le));
        queue<int>q;
        q.push(s);
        le[s]=1;
        while(q.size()){
            auto u=q.front();
            q.pop();
            for(int i=h[u];i;i=ne[i]){
                int v=e[i];
                if(!le[v]&&w[i]>0){
                    le[v]=le[u]+1;
                    q.push(v);
                }
            }
        }
        return le[t];
    }
    int dfs(int u,int t,int flow){
        if(u==t||!flow) return flow;
        int tot=0;
        for(int &i=it[u];i;i=ne[i]){
            int v=e[i];
            if(w[i]>0&&le[v]==le[u]+1){
                int res=dfs(v,t,min(flow,w[i]));
                if(res>0){
                    w[i]-=res,w[i^1]+=res;
                    tot+=res;
                    flow-=res;
                    if(flow==0) break;
                }
            }
        }
        return tot;
    }
    int flow(){
        int res=0;
        while(bfs(s)){
            for(int i=0;i<=t;i++)it[i]=h[i];
            res+=dfs(s,t,inf);
        }
        return res;
    }
};
signed main(){
    return 0;
}

费用流_Dinic

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e3+10,M=1e5+10,inf=1e14;
//变量
int n,m,ans;
//链式前向星
struct info{int to,cap,pay,next;}e[M];
int head[N],E=1;
void add(int u,int v,int cap,int pay){
    e[++E].to=v,e[E].cap=cap,e[E].pay=pay,e[E].next=head[u];head[u]=E;
    e[++E].to=u,e[E].cap=0,e[E].pay=-pay,e[E].next=head[v];head[v]=E;
}
//fost
int s,t;
int dis[N],f[N],pre[N],vis[N];
int spfa(){
    queue<int>q;
    for(int i=1;i<=n;i++){pre[i]=vis[i]=f[i]=0;dis[i]=inf;}
    dis[s]=0,f[s]=inf,vis[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to,pay=e[i].pay,cap=e[i].cap;
            if(cap&&dis[v]>dis[u]+pay){
                dis[v]=dis[u]+pay;
                f[v]=min(f[u],cap);
                pre[v]=i;
                if(!vis[v])vis[v]=1,q.push(v);
            }
        }
    }
    return f[t];
}
pair<int,int>dinic(){
    int ans=0,answ=0;
    while(spfa()){
        ans+=f[t],answ+=f[t]*dis[t];
        for(int i=t;pre[i];i=e[pre[i]^1].to)
            e[pre[i]].cap-=f[t],e[pre[i]^1].cap+=f[t];
    }
    return {ans,answ};
}
signed main(){
    return 0;
}

分块板子

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=sqrt(N)+1,inf=1e14,mod=1e9+7;
int n,m;
struct Blocking{
    int n,a[N];
    int st[M],ed[M];
    int block,t,pos[N];
    int tag[M],sum[M];
    void init(){
        block=sqrt(n);
        t=(n-1)/block+1;
        for(int i=1;i<=t;i++){
            st[i]=(i-1)*block+1;
            ed[i]=i*block;
            for(int j=st[i];j<=ed[i];j++){
                pos[j]=i;
                sum[i]+=a[j];
            }
            tag[i]=0;
        }
        ed[t]=n;
    }
    void in(int l,int r,int x){
        if(pos[l]==pos[r]){
            for(int i=l;i<=r;i++)a[i]+=x;
            return;
        }
        for(int i=l;i<=ed[pos[l]];i++)a[i]+=x;
        for(int i=st[pos[r]];i<=r;i++)a[i]+=x;
        for(int i=pos[l]+1;i<=pos[r]-1;i++)
            sum[i]+=x;
    }
    int out(int l,int r){
        int ret=0;
        if(pos[l]==pos[r]){
            for(int i=l;i<=r;i++)
                ret+=(a[i]+tag[pos[i]]);
            return ret;
        }
        for(int i=l;i<=ed[pos[l]];i++)
            ret+=(a[i]+tag[pos[i]]);
        for(int i=st[pos[r]];i<=r;i++)
            ret+=(a[i]+tag[pos[i]]);
        for(int  i=pos[l]+1;i<=pos[r]-1;i++)
            ret+=(ed[i]-st[i]+1)*tag[i]+sum[i];
        return ret;
    }
}t;
signed main(){
    ios::sync_with_stdio(0);

    return 0;
}

Trie板子

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,M=2,inf=1e14;
int n,m;
vector<int>v;
struct Trie{
    int next[N][M],num[N],cnt;
    void clear(){
        for(int i=0;i<=cnt;i++){
            num[i]=0;
            for(int j=0;j<M;j++)
                next[i][j]=0;
        }cnt=0;
    }
    void insert(vector<int>s){
        int pos=0;
        for(auto i:s){
            if(!next[pos][i])next[pos][i]=++cnt;
            pos=next[pos][i];
        }
        num[pos]++;

    }
    int find(vector<int>s){
        int pos=0;
        for(auto i:s){
            if(!next[pos][i])return 0;
            pos=next[pos][i];
        }
        return num[pos];
    }
}trie;
signed main(){
    return 0;
}

01Trie

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=2,inf=1e14;
int n,m;
vector<int>v;
struct Trie{
    int next[N][M],num[N],cnt=1;
    void clear(){
        for(int i=0;i<=cnt;i++){
            num[i]=0;
            for(int j=0;j<M;j++)
                next[i][j]=0;
        }cnt=1;
    }
    void insert(int x){
        int pos=1;
        for(int i=60;i>=0;i--){
            int c=(x>>i)&1;
            if(!next[pos][c])next[pos][c]=++cnt;
            pos=next[pos][c];
        }
        num[pos]++;
    }
}trie;
signed main(){
    return 0;
}

矩阵乘法板子

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
struct Max{
    int n,m;
    int a[N][N];
    Max(int n,int m):n(n),m(m){}
    void init(){memset(a,0,sizeof(a));};
    Max operator* (const Max b) const{
        Max c(n,b.m);
        c.init();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=b.m;j++)
                for(int k=1;k<=m;k++)
                    c.a[i][j]+=a[i][k]*b.a[k][j];
        return c;
    }
    Max operator% (int const mod){
        Max b(n,m);
        b.init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                b.a[i][j]=(int)(a[i][j]%mod);
        }
        return b;
    }
    Max operator^ (int cnt){
        Max b(n,m),ans(n,m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                b.a[i][j]=a[i][j];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                ans.a[i][j]=a[i][j];
        }
        int now=1,ctt=cnt-1;
        while(now<=ctt){
            if(ctt&now){
                ans=ans*b%mod;
            }
            now*=2;
            b=b*b%mod;
        }
        return ans;
    }
    int *operator [](const int p)  { return a[p];}
    void print(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                cout<<a[i][j]<<" ";
            cout<<"\n";
        }
    }
    void in(){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
    }
};
signed main(){
    ios::sync_with_stdio(0);
    return 0;
}

字符串

后缀数组

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int 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-'0',ch=getchar();}return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);} putchar(x%10+'0');return;}
int qpow(int a,int b,int mod){if(b==0){return 1;}int mid=qpow(a,b/2,mod)%mod;if(b&1){return (mid*mid%mod)*a%mod;}return mid*mid%mod;}
const int N=1e6+10,M=210,inf=1e14;
int n;
int a[N];
int sa[N],rk[N],h[N];
int r[N];
int ls[M],wa[N],wb[N];
char s[N];
bool cmp(int *r,int a,int b,int l){
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void build_sa(int m){
    memset(ls,0,sizeof(ls));
    int *x=wa,*y=wb,*c=ls;
    for(int i=1;i<=n;i++)c[x[i]=s[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;//先对最开始的x创建SA数组
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k+1;i<=n;i++)y[++p]=i;//空字符占位
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++p]=sa[i]-k;//剩下的字符
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[x[y[i]]]++;//x在y下的映射
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;//求出新的SA
        swap(x,y),p=1,x[sa[1]]=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p:++p;//更新最大排名
        if(p>=n)
            break;
        m=p;
    }
}
void calc_h(){
    memset(h,0,sizeof(h));
    int k=0;
    for(int i=1;i<=n;i++)rk[sa[i]]=i;//根据SA求出rank
    for(int i=1;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&r[i+k]==r[j+k])k++;
        h[rk[i]]=k;
    }
}
signed main(){
    ios::sync_with_stdio(0);

    return 0;
}

manacher

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,mod=1e9+7,lg=60;
char s[N* 2],str[N*2];
int Len[N*2],len;
void getstr(){
    int k=0;
    str[k++]='@';
    for(int i=0;i<len;i++){
        str[k++]='#';
        str[k++]=s[i];
    }
    str[k++]='#';
    len=k;
    str[k]=0;
}
int manacher(){
    int mx=0,id;
    int maxx=0;
    for (int i=1;i<len;i++) {
        if(mx>i)Len[i]=min(mx-i,Len[2*id-i]);
        else Len[i]=1;
        while(str[i+Len[i]]==str[i-Len[i]])Len[i]++;
        if(Len[i]+i>mx){
            mx=Len[i]+i;
            id=i;
            maxx=max(maxx,Len[i]);
        }
    }
    return (maxx-1);
}
signed main(){
    ios::sync_with_stdio(0);
    scanf("%s",s);
    len=strlen(s);
    getstr();
    printf("%d\n",manacher());
    return 0;
}

KMP

void getpi(string s,int *pi) {
    for(int i=1;i<s.size();i++){
        int len=pi[i-1];
        while(len>0&&s[i]!=s[len])len=pi[len-1];
        pi[i]=len+(s[i]==s[len]);
    }
}

最短路

flody板子

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010,inf=1e14,mod=998244354;
int n,m,ans,dp[N][N];
void flody(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                dp[i][j]=inf;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
}
signed main(){
    cin>>n>>m;

    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        dp[u][v]=dp[v][u]=min(w,min(dp[u][v],dp[v][u]));
    }
    return 0;
} 

Dijkstra 板子

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,inf=1e14;
struct info {int v,w;bool operator<(const info&u)const{return w>u.w;}};
int n,m;
int ans,u[N],v[N],w[N];
int vis[N];
int dis[N];
vector<info>g[N];
void Dijkstra(int start,int dis[N],int vis[N]){
    priority_queue<info>sk;
    for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
    dis[start]=0;
    sk.push({start,0});
    while(!sk.empty()){
        int u=sk.top().v;
        sk.pop();
        if(vis[u]) continue;
        else vis[u]=1;
        for(auto [v,w]:g[u])
            if(!vis[v]&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                sk.push({v,dis[v]});
            }
    }
}
signed main(){
    return 0;
}

线段树

[模板]

struct Tree{
    int t[N*4];
    int lson[N*4],rson[N*4],cnt=1;
    int ls(int x){
        if(lson[x])return lson[x];
        else return lson[x]=++cnt;
    }
    int rs(int x){
        if(rson[x])return rson[x];
        else return rson[x]=++cnt;
    }
    void pushup(int x){
        t[x]=t[ls(x)]+t[rs(x)];
    }
    void in(int pos,int val,int x=1,int l=1,int r=n){
        if(l==r){t[x]+=val;return;}
        int mid=(l+r)/2;
        if(pos<=mid)in(pos,val,ls(x),l,mid);
        if(pos>mid)in(pos,val,rs(x),mid+1,r);
        pushup(x);
    }
    int out(int ql,int qr,int x=1,int l=1,int r=n){
        if(ql<=l&&r<=qr)return t[x];
        int mid=(l+r)/2,ret=0;
        if(ql<=mid)ret+=out(ql,qr,ls(x),l,mid);
        if(qr>mid)ret+=out(ql,qr,rs(x),mid+1,r);
        return ret;
    }
}t;

lazy_tag

struct Tree{
    int t[N*4],lazy[N*4];
    int ls(int x){return (x<<1);}
    int rs(int x){return (x<<1|1);}
    void pushup(int x){t[x]=t[ls(x)]+t[rs(x)];}
    void pushdown(int x,int l,int r){
        if(lazy[x]!=0){
            int mid=(l+r)/2;
            lazy[ls(x)]+=lazy[x];
            lazy[rs(x)]+=lazy[x];

            t[ls(x)]+=lazy[x]*(mid-l+1);
            t[rs(x)]+=lazy[x]*(r-mid);
            lazy[x]=0;
        }
    }
    void build(int x=1,int l=1,int r=n){
        lazy[x]=0;
        if(l==r){t[x]=0;return;}
        int mid=(l+r)/2;
        build(ls(x),l,mid);
        build(rs(x),mid+1,r);
        pushup(x);
    }
    void in(int ql,int qr,int val,int x=1,int l=1,int r=n){
        int mid=(l+r)/2;
        if(ql<=l&&r<=qr){t[x]+=(r-l+1)*val,lazy[x]+=val;return;}
        pushdown(x,l,r);
        if(ql<=mid)in(ql,qr,val,ls(x),l,mid);
        if(qr>mid)in(ql,qr,val,rs(x),mid+1,r);
        pushup(x);
    }
    int out(int ql,int qr,int x=1,int l=1,int r=n){
        if(ql<=l&&r<=qr)return t[x];
        int mid=(l+r)/2;
        pushdown(x,l,r);
        int sum=0;
        if(ql<=mid)sum+=out(ql,qr,ls(x),l,mid);
        if(qr>mid)sum+=out(ql,qr,rs(x),mid+1,r);
        return sum;
    }
}t;

扩展

tarjan板子

https://www.luogu.com.cn/training/569532#problems

Kruskal重构树

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,m,ans;
int q;
vector<int>kru_t[N];

//kruskal_tree
int fa[N],val[N];
struct Edge{int u,v,w;}e[N];
int cmp(Edge a,Edge b){return a.w<b.w;}
int find(int x){return (x==fa[x])?x:(fa[x]=find(fa[x]));}
int kruskal_tree(){
    for(int i=1;i<=2*n-1;i++)fa[i]=i;

    sort(e+1,e+m+1,cmp);
    int cnt=n;

    for(int i=1;i<=m&&cnt<2*n-1;i++){
        auto[u,v,w]=e[i];
        if(find(u)!=find(v)){
            int x=find(u),y=find(v);
            fa[x]=fa[y]=++cnt;val[cnt]=w;
            kru_t[cnt].push_back(x),kru_t[cnt].push_back(y);
        }
    }
    return cnt;
}
//lca
int f[N][40],dep[N],vis[N];
void dfs(int u,int fath){
    f[u][0]=fath;
    dep[u]=dep[fath]+1;
    vis[u]=1;
    for(int i=1;i<=30;i++)f[u][i]=f[f[u][i-1]][i-1];

    for(auto v:kru_t[u])
        if(!vis[v])dfs(v,u);
}
int lca(int x,int y){
    if(dep[x]>dep[y])swap(x,y);
    for(int i=30;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])y=f[y][i];

    if(y==x)return x;

    for(int i=30;i>=0;i--)
        if(f[y][i]!=f[x][i])y=f[y][i],x=f[x][i];
    return f[x][0];
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i)
        cin>>e[i].u>>e[i].v>>e[i].w;

    n=kruskal_tree();

    for(int i=1;i<=n;i++)
        if(i==fa[i])dfs(i,0);
    cin>>q;
    while(q--){
        int a,b;cin>>a>>b;
        int id=lca(a,b);
        if(id!=0)cout<<val[id]<<"\n";
        else puts("impossible");
    }
    return 0;
}

LCA板子

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5,inf=1e14,mod=1e9+7;
struct info{
    int v,w;
};
int n,q,s,dep[N],f[N][65],fx[N][65],fi[N][65];
vector<int>a[N]; 
void dfs(int u,int fa)
{
    f[u][0]=fa;
    for(int i=1;i<=30;i++)f[u][i]=f[f[u][i-1]][i-1];
    dep[u]=dep[fa]+1;
    for(auto v:a[u]) 
        if(v!=fa)dfs(v,u);
}
int lca(int x,int y)
{
    int log2n=log(n)/log(2)+0.5;
    if(dep[x]>dep[y])swap(x,y);
    for(int i=log2n;i>=0;i--)
        if(dep[f[y][i]]>=dep[x])y=f[y][i];

    if(y==x)return x;

    for(int i=log2n;i>=0;i--)
        if(f[y][i]!=f[x][i])y=f[y][i],x=f[x][i];
    return f[x][0];
}
signed main(){
    cin>>n>>q>>s;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(s,0);
    while(q--){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<"\n";
    }
    return 0;
}

DSU on Tree

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m;
int a[N];
vector<int>g[N];
int siz[N],son[N],lp[N],rp[N],id[N],dfn;//封装不动
int sum[N],num[N],ans[N];//add/del的操作
vector<pair<int,int>>qry[N];
void add(int x){sum[++num[x]]++;}
void del(int x){sum[num[x]--]--;}
void dfs1(int u,int fa){
    lp[u]=++dfn,id[dfn]=u,siz[u]=1;
    for(auto v:g[u])
        if(v!=fa){
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]])son[u]=v;
        }
    rp[u]=dfn;
}
void dfs2(int u,int fa,bool keep){
    for(auto v:g[u])
        if(v!=son[u]&&v!=fa)dfs2(v,u,0);
    if(son[u])dfs2(son[u],u,1);
    add(a[u]);
    for(auto v:g[u])
        if(v!=son[u]&&v!=fa)
            for(int i=lp[v];i<=rp[v];i++)add(a[id[i]]);
    //ans记录答案
    for(auto[i,k]:qry[u])ans[i]=sum[k];
    if(keep==0)
        for(int i=lp[u];i<=rp[u];i++)del(a[id[i]]);
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1,u,v;i<n;i++)
        cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
    for(int i=1,v,k;i<=m;i++)
        cin>>v>>k,qry[v].push_back({i,k});
    dfs1(1,0);dfs2(1,0,0);
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
    return 0;
}

可持久化

http://ssloj.cn/contest/915

主席树区间：https://www.luogu.com.cn/record/240116224

异或线型基

https://www.luogu.com.cn/article/zo12e4s5

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,inf=1e14,mod=1e9+7;
inline int read(){int 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-'0',ch=getchar ();}return x*f;}
void write(int x){if(x<0){putchar ('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return ;}
int qpow(int a,int b){if(b==0){return 1;}int mid=qpow(a,b/2)%mod;if(b&1){return (mid*mid%mod)*a%mod;}return mid*mid%mod;}
int n,a[N],val[N];
int d[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
struct Basis{
    vector<int>v;
    void init(){v.clear();}
    int add(int w){
        for(auto x:v)w=min(w,x^w);
        for(auto &x:v)x=min(x,x^w);
        if(w){v.push_back(w);return 1;}
        return 0;
    }
    int isok(int x){
        for(auto i:v)x=min(i^x,x);
        return (x==0);
    }
    int num(int len,int x){return (isok(x)?qpow(2,len-v.size()):0);}
}w;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=0;j<19;j++)
            while(a[i]%d[j]==0&&a[i]>0)val[i]^=(1<<j),a[i]/=d[j];
        w.add(val[i]);
    }
    cout<<w.num(n,0)-1;
;
    return 0;
}