M_sea

【合集】M_sea的OI模板
排序快速排序sort多好这么容易被卡的算法写了干嘛qwq不如用下面的归并排序归并排序stable_sort多好in...
扫描右侧二维码阅读全文
06
2018/11

【合集】M_sea的OI模板

排序

快速排序

sort多好

这么容易被卡的算法写了干嘛qwq

不如用下面的归并排序

归并排序

stable_sort多好

inline void Merge_Sort(int l,int r) {
    if (l==r) return;
    int mid=(l+r)>>1;
    Merge_Sort(l,mid); Merge_Sort(mid+1,r);
    int i=l,j=mid+1,k=l-1;
    while (i<=mid&&j<=r) {
        if (a[i]<a[j]) tmp[++k]=a[i++];
        else tmp[++k]=a[j++];
    }
    while (i<=mid) tmp[++k]=a[i++];
    while (j<=r) tmp[++k]=a[j++];
    for (re int q=l;q<=r;++q) a[q]=tmp[q];
}

数论相关

线性筛

int p[1000010],tot=0;
int v[10000010];
inline void getPrime(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) { p[++tot]=i,v[i]=i; }
        for (re int j=1;j<=tot;++j) {
            if (p[j]>v[i]||i*p[j]>n) break;
            v[i*p[j]]=p[j];
        }
    }
}

三分法求函数极值

while (r-l>1e-6) {
    double a=(l+l+r)/3,b=(l+r+r)/3;
    double fa=f(a),fb=f(b);
    if (fa<fb) l=a;
    else r=b;
}

快速幂

inline int FastPow(int a,int b,int p) {
    int ans=1;
    while (b) {
        if (b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

龟速乘

inline int SlowMul(int a,int b,int p){
    int ans=0;
    while (b){
        if (b&1) ans=(ans+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return ans;
}

矩阵快速幂

struct Matrix {
    int r,c;
    int m[110][110];
    Matrix() { this->r=this->c=0; memset(m,0,sizeof(m)); }
    inline void init() { r=c=0; memset(m,0,sizeof(m)); }
    inline void print() {
        for (re int i=1;i<=r;++i)
            for (re int j=1;j<=c;++j)
                printf("%lld%c",m[i][j],j==c?'\n':' ');
    }
};

inline Matrix Mul(Matrix a,Matrix b,int p) {
    Matrix c; c.r=a.r,c.c=b.c;
    for (re int i=1;i<=c.r;++i)
        for (re int j=1;j<=c.c;++j) {
            c.m[i][j]=0;
            for (re int k=1;k<=a.c;++k) (c.m[i][j]+=a.m[i][k]*b.m[k][j])%=p;
        }
    return c;
}

inline Matrix FastPow(Matrix a,int b,int p) {
    Matrix c; c.r=a.r,c.c=a.c;
    for (re int i=1;i<=a.r;++i) c.m[i][i]=1;
    while (b) {
        if (b&1) c=Mul(c,a,p);
        a=Mul(a,a,p);
        b>>=1;
    }
    return c;
}

gcd&exgcd

gcd

inline int gcd(int a,int b) {
    return a%b?gcd(b,a%b):b;
}

exgcd

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y,y=z-y*(a/b);
    return d;
}

卢卡斯定理求模质数意义下组合数

inline int FastPow(int a,int b,int p) { //快速幂求逆元
    int ans=1;
    while (b) {
        if (b&1) ans=ans*a%p;
        a=a*a%p,b>>=1;
    }
    return ans;
}
inline int C(int n,int m,int p) { //组合数
    if (n<m) return 0;
    return fac[n]*FastPow(fac[m],p-2,p)%p*FastPow(fac[n-m],p-2,p)%p;
}
inline int Lucas(int n,int m,int p) {
    if (!m) return 1;
    return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

高斯消元

inline int Gauss() {
    for (re int i=1;i<=n;++i) {
        for (re int j=i;j<=n;++j) {
            if (fabs(a[j][i])>1e-8) {
                for (re int k=1;k<=n;++k) swap(a[i][k],a[j][k]);
                swap(b[i],b[j]);
            }
        }
        if (fabs(a[i][i])<=1e-8) return 0; //无唯一解 
        for (re int j=1;j<=n;++j) {
            if (i==j) continue;
            double rate=a[j][i]/a[i][i];
            for (re int k=1;k<=n;++k) a[j][k]-=rate*a[i][k];
            b[j]-=rate*b[i];
        }
    }
    return 1;
}

数据结构

并查集

struct Union_Find_Set {
    int root[10010];
    inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
    inline int find(int x) { return root[x]==x?x:root[x]=find(root[x]); }
    inline void merge(int a,int b) {
        a=find(a),b=find(b);
        if (a!=b) root[a]=b;
    }
    inline int check(int a,int b) { return find(a)==find(b); }
};

树状数组

单点修改、区间求和

struct Tree_Array {
    int c[MAXN];
    inline int lowbit(int x) { return x&-x; }
    inline void add(int x,int k) {
        while (x<=n) c[x]+=k,x+=lowbit(x);
    }
    inline int sum(int k) {
        int rt=0;
        while (k) rt+=c[k],k-=lowbit(k);
        return rt;
    }
};

区间修改、单点查询

树状数组维护差分数组就好了。

线段树

struct Segment_Tree {
    int sumv[MAXN<<2],addv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) { sumv[o]=sumv[lson]+sumv[rson]; }
    inline void pushdown(int o,int l,int r) {
        if (addv[o]) {
            int mid=(l+r)>>1;
            addv[lson]+=addv[o],addv[rson]+=addv[o];
            sumv[lson]+=addv[o]*(mid-l+1);
            sumv[rson]+=addv[o]*(r-mid);
            addv[o]=0;
        }
    }
    inline void build(int o,int l,int r) {
        if (l==r) { sumv[o]=a[l]; return; }
        int mid=(l+r)>>1;
        build(lson,l,mid); build(rson,mid+1,r);
        pushup(o);
    }
    inline void update(int o,int l,int r,int ql,int qr,int v) {
        if (ql<=l&&r<=qr) { sumv[o]+=(r-l+1)*v,addv[o]+=v; return; }
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (ql<=mid) update(lson,l,mid,ql,qr,v);
        if (qr>mid) update(rson,mid+1,r,ql,qr,v);
        pushup(o);
    }
    inline int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return sumv[o];
        int mid=(l+r)>>1,rt=0;
        pushdown(o,l,r);
        if (ql<=mid) rt+=query(lson,l,mid,ql,qr);
        if (qr>mid) rt+=query(rson,mid+1,r,ql,qr);
        pushup(o);
        return rt;
    }
#undef lson
#undef rson
};

主席树

区间第k大

不会

可持久化数组

不会

可持久化并查集

不会

左偏树(可并堆)

不会

平衡树

fhq treap

struct fhq_treap {
    int sz[MAXN],val[MAXN],rnd[MAXN];
    int ch[MAXN][2];
    int cnt,root;
    
    fhq_treap() { this->cnt=this->root=0; }
    inline void pushup(int o) { sz[o]=sz[ch[o][0]]+sz[ch[o][1]]+1; }
    inline int new_node(int x) { val[++cnt]=x,sz[cnt]=1,rnd[cnt]=rand(); return cnt; }
    
    inline void split(int now,int k,int& x,int& y) {
        if (!now) { x=y=0; return; }
        if (val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y);
        else y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
    inline int merge(int A,int B) {
        if (!A||!B) return A+B;
        if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B); pushup(A); return A; }
        else { ch[B][0]=merge(A,ch[B][0]); pushup(B); return B; }
    }
    inline int kth(int now,int k) { //第k大的节点 
        while (1) {
            if (k<=sz[ch[now][0]]) now=ch[now][0];
            else if (k==sz[ch[now][0]]+1) return now;
            else k-=sz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    
    inline void insert(int k) { //插入 
        int x,y; split(root,k,x,y);
        root=merge(merge(x,new_node(k)),y);
    }
    inline void del(int k) {
        int x,y,z;
        split(root,k,x,z);
        split(x,k-1,x,y);
        y=merge(ch[y][0],ch[y][1]);
        root=merge(merge(x,y),z);
    }
    inline int get_rank_by_val(int k) { //k的排名
        int x,y; split(root,k-1,x,y);
        int ans=sz[x]+1;
        root=merge(x,y);
        return ans;
    } 
    inline int get_val_by_rank(int k) { //排名为k的数的值 
        return val[kth(root,k)];
    }
    inline int getLast(int k) { //严格前驱(不严格只需将k-1改为k) 
        int x,y; split(root,k-1,x,y);
        int ans=val[kth(x,sz[x])];
        root=merge(x,y);
        return ans;
    }
    inline int getNext(int k) { //严格后继(不严格只需将k改为k-1)
        int x,y; split(root,k,x,y);
        int ans=val[kth(y,1)];
        root=merge(x,y);
        return ans;
    }
};

Splay

不会

Link-Cut Tree

不会

字符串算法

KMP

inline void getNext(string s) {
    int l=s.length(); nxt[0]=-1;
    for (re int i=1;i<l;++i) {
        int t=nxt[i-1];
        while (s[t+1]!=s[i]&&t>=0) t=nxt[t];
        if (s[t+1]==s[i]) nxt[i]=t+1;
        else nxt[i]=-1;
    }
}

inline void KMP(string a,string b) {
    getNext(b);
    int la=a.length(),lb=b.length();
    int i=0,j=0;
    while (j<la) {
        if (a[j]==b[i]) {
            ++i,++j;
            if (i==lb) ans[++cnt]=j-lb+1,i=nxt[i-1]+1;
        }
        else {
            if (!i) ++j;
            else i=nxt[i-1]+1;
        }
    }
}

AC自动机

不会

manacher

inline void change() {
    s[0]=s[1]='`';
    for (re int i=0;i<n;++i) s[(i<<1)+2]=a[i],s[(i<<1)+3]='`';
    n=n*2+2,s[n]='\0';
}

inline void Manacher() {
    n=strlen(a); change();
    int MaxRight=0,mid;
    for (re int i=1;i<n;++i) {
        if (i<MaxRight) f[i]=min(f[(mid<<1)-i],f[mid]+mid-i);
        else f[i]=1;
        for (;s[i+f[i]]==s[i-f[i]];++f[i])
            if (f[i]+i>MaxRight) MaxRight=f[i]+i,mid=i;
    }
}

图论

最小生成树

Prim

inline int Prim() {
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0; int ans=0;
    for (re int i=1;i<=n;++i) {
        int u,Min=2147483647;
        for (re int j=1;j<=n;++j)
            if (!vis[j]&&dis[j]<Min) Min=dis[j],u=j;
        if (Min==2147483647) return -1;
        vis[u]=1,ans+=Min;
        for (re int j=head[u];j;j=e[j].nxt) {
            int v=e[j].v,w=e[j].w;
            dis[v]=min(dis[v],w);
        }
    }
    return ans;
}

Kruskal

Union_Find_Set S;

inline int Kruskal() {
    S.init(n); sort(e+1,e+m+1);
    int ans=0,s=0;
    for (re int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (S.find(u)!=S.find(v)) {
            S.merge(u,v);
            ans+=w,++s;
            if (s==n-1) break;
        }
    }
    if (s==n-1) return ans;
    else return -1;
}

最短路算法

Dijkstra

struct node {
    int u,d;
    bool operator <(const node& rhs) const {
        return d>rhs.d;
    }
};

inline void Dijkstra() {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<node> Q;
    Q.push((node){s,0});
    while (!Q.empty()) {
        node fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if (d!=dis[u]) continue;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}

SPFA

inline void SPFA() {
    queue<int> Q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); inq[u]=0; Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                if (!inq[v]) { inq[v]=1; Q.push(v); }
            }
        }
    }
}

Floyd

inline void Floyd() {
    for (re int k=1;k<=n;k++)
        for (re int i=1;i<=n;i++)
            for (re int j=1;j<=n;j++)
                if (dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
}

倍增LCA

int f[500010][25];
int dep[500010];

inline void Dfs(const int u,const int fa) {
    dep[u]=dep[fa]+1; f[u][0]=fa;
    for (re int i=1;(1<<i)<=dep[u];++i)
        f[u][i]=f[f[u][i-1]][i-1];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa) Dfs(v,u);
    }
}

inline int LCA(int a,int b) {
    if (dep[a]<dep[b]) swap(a,b);
    for (re int i=20;~i;i--)
        if (dep[f[a][i]]>dep[b]) a=f[a][i];
    if (dep[a]!=dep[b]) a=f[a][0];
    for (re int i=20;~i;i--)
        if (f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
    if (a!=b) a=f[a][0],b=f[b][0];
    return a;
}

匈牙利算法

int link[2010];
bool vis[2010];

inline bool Hungary(int u) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!vis[v]) {
            vis[v]=1;
            if (!link[v]||Hungary(link[v])) {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

割点

int dfn[100010],low[100010];
bool cut[100010];
int dfs_clock=0;
int root;

inline void Tarjan(int u) {
    dfn[u]=low[u]=++dfs_clock;
    int f=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min_(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                f++;
                if (u!=root||f>1) cut[u]=1;
            }
        }
        else low[u]=min_(low[u],dfn[v]);
    }
}

缩点

int dfn[10010],low[10010];
int sta[10010],top=0;
bool in_stack[10010];
int dfs_clock=0;

int tot=0;
int belong[10010];

inline void Tarjan(int u) {
    low[u]=dfn[u]=++dfs_clock;
    sta[++top]=u; in_stack[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (in_stack[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot; int now;
        while (1) {
            now=sta[top--];
            belong[now]=tot;
            in_stack[now]=0;
            if (now==u) break;
        }
    }
}

负环

inline int SPFA() {
    queue<int> Q;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0,inq[1]=1,cnt[1]=0; Q.push(1);
    while (!Q.empty()) {
        int u=Q.front(); inq[u]=0; Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w<dis[v]) {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if (cnt[v]>=n) return 1; //有负环 
                if (!inq[v]) {
                    inq[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    return 0;
}

树链剖分

int real[MAXN],dep[MAXN],fa[MAXN],sz[MAXN],hson[MAXN],top[MAXN],id[MAXN];
int tot=0;

inline void Dfs1(int u,int f) {
    fa[u]=f,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==f) continue;
        dep[v]=dep[u]+1;
        Dfs1(v,u);
        sz[u]+=sz[v];
        if (!hson[u]||sz[v]>sz[hson[u]]) hson[u]=v;
    }
}

inline void Dfs2(int u,int anc) {
    top[u]=anc,id[u]=++tot,real[tot]=u;
    if (!hson[u]) return;
    Dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v!=fa[u]&&v!=hson[u]) Dfs2(v,v);
    }
}
最后修改:2018 年 11 月 09 日 06 : 10 PM

发表评论

2 条评论

  1. smy

    鸽子博主,举报了

    1. M_sea
      @smy

      这不在补吗qwq