模板 知识点 算法

模板速查

一.线段树(区间求和为例)

#define lson (p<<1)
#define rson (p<<1|1)

1.建树

inline void build(int p,int l,int r){
    t[p].l=l,t[p].r=r; //每一部分的左右端点
    if(l==r){ //叶子节点
        t[p].sum=a[l];
        //创建所要维护的内容
        return ;
    }
    int mid=l+r>>1;
    build(lson,l,mid); //建左子树
    build(rson,mid+1,r); //建右子树
    pushup(p); //得到所维护内容
}

2.区间修改

区间+$k$

inline void change(int p,int l,int r,ll k){
    if(t[p].l>=l&&t[p].r<=r){ //当前区间完全包含于所求区间
        t[p].sum+=k*(t[p].r-t[p].l+1); //直接加上
        t[p].lazy+=k; //更新懒标记
        return ;
    }
    pushdown(p); //标记下传
    int mid=l+r>>1;
    if(t[lson].r>=l) change(lson,l,r,k); //若左子树与所求区间有交集，则递归左子树求值
    if(t[rson].l<=r) change(rson,l,r,k); //右子树同理
    pushup(p) //更新所维护内容
}

3.区间查询

inline int query(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r)return t[p].sum; ///当前区间完全包含于所求区间，直接返回当前区间的值
    pushdown(p); //标记下传
    int res=0;
    if(t[lson].r>=l) res+=query(lson,l,r);
    if(t[rson].l<=r) res+=query(rson,l,r);
    return res;
}

二.树状数组

1.单点修改(+k)

inline void updata(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))
        c[i]+=y;
}

2.区间查询（求和）

inline int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=c[i];
    return res;
}

三.线性基

1.建基

inline void ins(int x){
    for(int i=62;i>=0;i--){
        if(!((x>>i)&1)) continue;
        if(!p[i]){
            p[i]=x;
            break;
        }
        x^=p[i];
    }
}

2.求任意异或的最大值

 int ans=0;
    for(int i=62;i>=0;i--)
        if((ans^p[i])>ans)
            ans^=p[i];

四.强连通分量(缩点)

inline void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    sta[++tp]=u;st[u]=1;
    for(int i=he[u];i;i=ne[i]){
        int v=go[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(st[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;int t;
        do{
            t=sta[tp--];
            id[t]=scc;
            st[t]=0;
            vul[scc]+=val[t];
        }while(t!=u);
    }
}

五.KMP模式匹配法

1.求失配数组

int j=0;
for(int i=2;i<=lt;i++){
    while(j&&t[i]!=t[j+1]) j=ne[j];
    if(t[i]==t[j+1]) j++;
    ne[i]=j;
}

2.匹配

j=0;
for(int i=1;i<=ls;i++){
    while(j&&s[i]!=t[j+1]) j=ne[j];
    if(s[i]==t[j+1]) j++;
    if(j==lt) cout<<i-lt+1<<endl;
}

六.高斯消元法

inline void Gauss(){
    for(int r=1,c=1;c<=n;r++,c++){
        int mai=r;
        for(int i=r+1;i<=n;i++)
            if(fabs(a[i][c])>fabs(a[mai][c]))mai=i;
        for(int i=c;i<=n+1;i++)
            swap(a[mai][i],a[r][i]);
        if(a[r][c]==0){
            puts("No Solution");
            exit(0);
        }//无解或有自由元
        for(int i=n+1;i>=c;i--)
            a[r][i]/=a[r][c];
        for(int i=r+1;i<=n;i++)
            for(int j=n+1;j>=c;j--)
                a[i][j]-=a[r][j]*a[i][c];
    }
    for(int i=n;i>1;i--)
        for(int j=i-1;j>=1;j--){
            a[j][n+1]-=a[i][n+1]*a[j][i];
            a[j][i]=0;
        }
}

七.单调队列

int head=1,tail=1;
for(int i=1;i<=n;i++){
    while(num[head]<i-k+1&&head<=tail) head++;
    while(a[num[tail]]>=a[i]&&head<=tail) tail--;
    num[++tail]=i;
    if(i>=k)printf("%d ",a[num[head]]);
}//求所有长度为k的区间中的最小值

八.