线段树（区间修改，区间和）：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

int c[1000000],n,m;

char s;

void update(int p,int l,int r,int x,int add)

{

    int m=(l+r) / 2;

    if (l==r)

    {

        c[p]+=add;

        return;

    }

    if (x<=m)   update(p*2,l,m,x,add);

    if (x>m)    update(p*2+1,m+1,r,x,add);

    c[p]=c[p<<1]+c[p<<1|1];

}

int find(int p,int l,int r,int a,int b)

{

    if (l==a && r==b)   return c[p];

    else

    {

        int m=(l+r) / 2;

        if (b<=m)   return find(p*2,l,m,a,b);

        else if (a>m)   return find(p*2+1,m+1,r,a,b);

        else return find(p*2,l,m,a,m)+find(p*2+1,m+1,r,m+1,b);

    }

}

int main()

{

    scanf("%d",&n);

    scanf("%d",&m);

    for (int i=1;i<=m;i++)

    {

        cin>>s;

        if (s=='M')

        {

            int x,y;

            scanf("%d%d",&x,&y);

            update(1,1,n,x,y);

        }

        if (s=='C')

        {

            int x,y;

            scanf("%d%d",&x,&y);

            printf("%d\n",find(1,1,n,x,y));

        }

    }

}

线段树（lazy）：

线段树，并且单纯的线段树会超时，因为在将a到b的点全部加上c时，步骤太多，会超时。

需要优化。即lazy算法；

Lazy：

在将a~b点全部加c时，不要加到每个点，在表示区间的root结构体上增加一个inc域，将要加的值赋给这个inc域，然后就不要再往下了。

在求区间和时，将root中的inc值赋给要求的区间，并且将该节点的root置零。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

#define ll long long

using namespace std;

ll a[1000005],t[5000005],n,lazy[5000005],m;

ll read()

{

    ll s=0;

    char ch=getchar();

    while (ch<'0' || ch>'9')    ch=getchar();

    while (ch>='0' && ch<='9')

    {

        s=(s << 1) + (s << 3) +ch-'0';ch=getchar();

    }

    return s;

}

void build(ll p,ll l,ll r)

{

    if (l==r)

    {

        t[p]=a[l];

        return;

    }

    ll m=(l+r)>>1;

    build(p<<1,l,m);

    build(p<<1|1,m+1,r);

    t[p]=t[p<<1]+t[p<<1|1];

}

void pushdown(ll x,ll len)

{

    if (lazy[x]!=0)

    {

        lazy[x<<1]+=lazy[x];

        lazy[x<<1|1]+=lazy[x];

        t[x<<1]+=(len-len/2)*lazy[x];

        t[x<<1|1]+=(len/2)*lazy[x];

        lazy[x]=0;

    }

}

void update(ll a,ll b,ll l,ll r,ll x,ll p)

{

    if (a<=l && b>=r)

    {

        t[p]+=(r-l+1)*x;

        lazy[p]+=x;

        return;

    }

    if (lazy[p]!=0) pushdown(p,r-l+1);

    ll m=(l+r)/2;

    if (b<=m)   update(a,b,l,m,x,p<<1);

    else if (a>m)   update(a,b,m+1,r,x,p<<1|1);

    else update(a,m,l,m,x,p<<1),update(m+1,b,m+1,r,x,p<<1|1);

    t[p]=t[p<<1]+t[p<<1|1];

}

ll find(ll a,ll b,ll l,ll r,ll p)

{

    if (lazy[p]!=0) pushdown(p,r-l+1);

    if (a==l && b==r)   return t[p];

    ll m=(l+r)/2;

    if (b<=m)   return find(a,b,l,m,p<<1);

    else if (a>m)   return find(a,b,m+1,r,p<<1|1);

    else    return find(a,m,l,m,p<<1)+find(m+1,b,m+1,r,p<<1|1);

}

int main()

{

    n=read(); m=read();

    for (int i=1;i<=n;i++)

        a[i]=read();

    build(1,1,n);

    int x,y,z;

    for (int i=1;i<=m;i++)

    {

        x=read();

        if (x==1)

        {

            x=read(),y=read(),z=read();

            update(x,y,1,n,z,1);

        }

        else if (x==2)

        {

            y=read(),z=read();

            printf("%lld\n",find(y,z,1,n,1));

        }

    }

}

二分图匹配：

#include <iostream>

#include <cstring>

#include <cstdio>

#define inf 1000007

using namespace std;

struct arr

{

    int y, n;

}f[1000005];

int ls[1000005], n, m, tot, e, ans, link[1000005];

bool b[1000005];

void add(int x, int y)

{

    f[++tot].y = y;

    f[tot].n = ls[x];

    ls[x] = tot;

}

bool find(int x)

{

    for (int i = ls[x]; i; i = f[i].n)

        if (!b[f[i].y])

        {

            b[f[i].y] = 1;

            if (!link[f[i].y] || find(link[f[i].y]))

            {

                link[f[i].y] = x;

                return true;

            }

        }

    return false;

}

void work()

{

    for (int i = 1; i <= n; i++)

    {

        memset(b, 0, sizeof(b));

        if (find(i))    ans++;

    }

}

int main()

{

    int x, y;

    scanf("%d%d%d", &n, &m, &e);

    for (int i = 1; i <= e; i++)

    {

        scanf("%d%d", &x, &y);

        if (y > m) continue;

        add(x, y);

    }

    work();

    printf("%d", ans);

}

最小生成树：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

struct arr

{

    int x,y,w;

}f[200007];

int g[5007],tot,n,m;

bool b[5007];

int cmp(arr a,arr b)

{

    return a.w<b.w;

}

int find(int x)

{

    if (g[x]==x)    return x;

    g[x]=find(g[x]);

    return g[x];

}

int main()

{

    cin>>n>>m;

    int q,p,o,e=0;

    for (int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&q,&p,&o);

        e++;

        f[e].x=q;

        f[e].y=p;

        f[e].w=o;

    }

    sort(f+1,f+e+1,cmp);

    for (int i=1;i<=n;i++)

        g[i]=i;

    int k=0;

    for (int i=1;i<=e;i++)

    {

        if (k==n-1) break;

        if (find(g[f[i].x])!=find(g[f[i].y]))

        {

            k++;

            tot+=f[i].w;

            g[find(f[i].x)]=find(f[i].y);

        }

    }

    if (k==n-1) printf("%d",tot);

    else printf("orz");

}

最短路（spfa）：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

struct arr

{

    int to,next,w;

}f[5000007];

int n,m,s,d[1000007],ls[1000007],str[1000007];

bool b[1000007];

void spfa()

{

    for (int i=1;i<=n;i++)

        d[i]=2147483647;

    d[s]=0;

    int head=0,tail=1;

    b[s]=1;

    str[1]=s;

    while (head<tail)

    {

        head++;

        int t=ls[str[head]];

        while (t>0)

        {

            if (d[f[t].to]>d[str[head]]+f[t].w)

            {

                d[f[t].to]=d[str[head]]+f[t].w;

                if (!b[f[t].to])

                {

                    b[f[t].to]=1;

                    tail++;

                    str[tail]=f[t].to;

                }

            }

            t=f[t].next;

        }

        b[str[head]]=0;

    }

}

int main()

{

    scanf("%d%d%d",&n,&m,&s);

    int p,q;

    for (int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&q,&p,&f[i].w);

        f[i].to=p;

        f[i].next=ls[q];

        ls[q]=i;

    }

    spfa();

    for (int i=1;i<=n;i++)

        printf("%d ",d[i]);

}

并查集

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int n,m,f[10007];

int find(int x)

{

    if (f[x]==x)    return x;

    f[x]=find(f[x]);

    return f[x];

}

int main()

{

    scanf("%d%d",&n,&m);

    int q,p,z;

    for (int i=1;i<=n;i++)

        f[i]=i;

    for (int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&z,&q,&p);

        if (z==1)

        {

            f[find(q)]=find(p);

        }

        if (z==2)

        {

            if (find(q)==find(p))   cout<<"Y"<<endl;

            else cout<<"N"<<endl;

        }

    }

}

KMP

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

int a[1000005],b[1000005],p[1000005],n,m,next[1000005],ans;

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)

    {

        scanf("%d", &p[i]);

        a[i - 1] = p[i] - p[i - 1];

    }

    for (int i = 1; i <= m; i++)

    {

        scanf("%d", &p[i]);

        b[i - 1] = p[i] - p[i - 1];

    }

    int j = 0;

    for (int i = 2; i < m; i++)

    {

        while (j > 0 && b[j + 1] != b[i])   j = next[j];

        if (b[j + 1] == b[i])   j += 1;

        next[i] = j;

    }

    j = 0;

    for (int i = 1; i < n; i++)

    {

        while (j > 0 && b[j + 1] != a[i])   j = next[j];

        if (b[j + 1] == a[i])   j += 1;

        if (j == m - 1)

        {

            ans++;

            j = next[j];

        }

    }

    printf("%d", ans);

}

快速幂

int pow4(int a,int b)

{

  int r=1,base=a;

  while(b)

  {

    if(b&1) r*=base;

    base*=base;

    b>>=1;

  }

  return r;

}

强连通分量（tarjan）：

#include <cstdio>

#include <iostream>

using namespace std;

struct arr

{

    int x,y,next;

};

arr f[3000];

int ls[40000],stack[40000],belong[40000],low[40000],dfn[40000],cnt,e,n,d,tot,rd[40000],cd[40000],ans,s1,s2;

bool ins[40000];

void add(int x,int y)

{

    e++;

    f[e].x=x;

    f[e].y=y;

    f[e].next=ls[x];

    ls[x]=e;

}

void tarjan(int i)

{

    int t=0;

    int j=0;

    d++;

    dfn[i]=d;

    low[i]=d;

    tot++;

    stack[tot]=i;

    t=ls[i];

    ins[i]=1;

    while (t>0)

    {

        j=f[t].y;

        if (dfn[j]==0)

        {

            tarjan(j);

            if (low[i]>low[j])  low[i]=low[j];

        }

        else if (ins[j]&&dfn[j]<low[i]) low[i]=dfn[j];

        t=f[t].next;

    }

    if (dfn[i]==low[i])

    {

        cnt++;

        do

        {

            j=stack[tot];

            ins[j]=false;

            tot--;

            belong[j]=cnt;

        }

        while (i!=j);

    }

}

int main()

{

    cin>>n;

    int j;

    e=0;

    for (int i=1;i<=n;i++)

    {

        while (scanf("%d",&j)&&j!=0)

            add(i,j);

    }

    for (int i=1;i<=n;i++)

        if (dfn[i]==0)  tarjan(i);

    for (int i=1;i<=e;i++)

        if (belong[f[i].x]!=belong[f[i].y])

        {

            cd[belong[f[i].x]]++;

            rd[belong[f[i].y]]++;

        }

    ans=0;

    s1=0;

    s2=0;

    for (int i=1;i<=cnt;i++)

    {

        if (rd[i]==0)   {ans++; s1++;}

        if (cd[i]==0)   s2++;

    }

    cout<<ans<<endl;

    if (cnt==1) {s1=0; s2=0;}

    if (s1>s2)  cout<<s1<<endl;

    else cout<<s2<<endl;

}

最短路（floyd）：

for (int k = 1; k <= n; k++)

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= n; j++)

                if (i != j && i != k && j != k)

                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

最近公共祖先（lca）：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

struct arr {int  x,y,n;}f[60007];

int ls[30007],n,m,e,deep[30007],fa[30007][30],ans;

void add(int x, int y)

{

    f[++e].x = x;

    f[e].y = y;

    f[e].n = ls[x];

    ls[x] = e;

}

void dfs(int x, int la)

{

    deep[x] = deep[la] + 1;

    fa[x][0] = la;

    for (int i = ls[x]; i ; i = f[i].n)

    {

        if (f[i].y != la)

        {

            dfs(f[i].y, x);

        }

    }

}

int lca(int q, int p)

{

    if (deep[p] < deep[q])  swap(p,q);

    for (int j = 20; j >= 0; j--)

        if (deep[fa[p][j]] >= deep[q])

            p = fa[p][j];

    if (p == q) return p;

    for (int j = 20; j >= 0; j--)

    if (fa[p][j] != fa[q][j])

    {

        p = fa[p][j], q = fa[q][j];

    }

    return fa[p][0];

}

int main()

{

    scanf("%d", &n);

    int x, y;

    for (int i = 1; i <= n - 1; i++)

    {

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

    dfs(1, 0);

    for (int j = 1; j <= 20; j++)

        for (int i = 1; i <= n; i++)

            fa[i][j] = fa[fa[i][j - 1]][j - 1];

    scanf("%d", &m);

    scanf("%d", &x);

    m--;

    while (m--)

    {

        scanf("%d", &y);

        ans += deep[x] + deep[y] - deep[lca(x, y)] * 2;

        x = y;

    }

    printf("%d", ans);

}

巴特西

线段树、最短路径、最小生成树、并查集、二分图匹配、最近公共祖先--C++模板

线段树（区间修改，区间和）：

线段树（lazy）：

二分图匹配：

最小生成树：

最短路（spfa）：

并查集

KMP

快速幂

强连通分量（tarjan）：

最短路（floyd）：

最近公共祖先（lca）：

最新文章

热门文章