其他板子整理

ST表

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)d[i][0]=read();    
    for(int j=1;(1<<j)<=n;j++)
    for(int i=1;i-1+(1<<j)<=n;i++)
    d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
    while(m--)
    {
        l=read();r=read();
        k=log2(r-l+1);
        printf("%d
",max(d[l][k],d[r-(1<<k)+1][k]));
    }
}

LCA

#include<bits/stdc++.h>
using namespace std;
int n,m,ne,head[1000100],x,y,q,t,a,b,dep[1000100],fa[1000100][22];
struct node{int nxt,to;}eg[1000100*2];
void adde(int f,int v){eg[++ne].to=v;eg[ne].nxt=head[f];head[f]=ne;}
void dfs(int u,int father)
{
    for(int i=head[u];i;i=eg[i].nxt)
    if(eg[i].to!=father)
    {int v=eg[i].to;
    dep[v]=dep[u]+1;fa[v][0]=u;dfs(v,u);}  
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
    if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
int main()
{    
    cin>>n>>q>>t;dep[t]=1;
    for(int i=1;i<=n-1;i++)
    {cin>>a>>b;adde(a,b);adde(b,a);}
    dfs(t,t);fa[t][0]=t;
    for(int i=1;i<=20;i++)
    for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
    while(q--)
    {
        scanf("%d%d",&x,&y);
        printf("%d
",lca(x,y));
    }
}

线段树

#include<bits/stdc++.h>
using namespace std;
#define ln now<<1
#define rn (now<<1)+1
int n,m,a,b,c,cnt,d;
long long sum[400040],num[400040],tag[400040];
void pushdown(int now,int l,int r)
{
    if(tag[now])
    {
        int mid=(l+r)>>1;
        sum[ln]+=(tag[now]*(mid-l+1));sum[rn]+=(tag[now]*(r-mid));
        tag[ln]+=tag[now];tag[rn]+=tag[now];
        tag[now]=0;sum[now]=sum[ln]+sum[rn];
    }
}
void build(int now,int l,int r)
{
    if(l==r)sum[now]=num[++cnt];
    else{
    int mid=(l+r)/2;
    build(ln,l,mid);
    build(rn,mid+1,r);
    sum[now]=sum[ln]+sum[rn];    
    }
}
void add(int now,int ll,int rr,int l,int r,int val)
{
    if(l<=ll&&r>=rr)
    {
        sum[now]+=(val*(rr-ll+1));
        tag[now]+=val;
    }
    else{
        pushdown(now,ll,rr);
        int mid=(ll+rr)/2;
        if(l<=mid)add(ln,ll,mid,l,r,val);
        if(r>mid)add(rn,mid+1,rr,l,r,val);
        sum[now]=sum[ln]+sum[rn];
    }
        
}
long long  gsum(int now,int ll,int rr,int l,int r)
{
    long long ans=0;
    if(l<=ll&&r>=rr)ans+=sum[now];
    else{
        pushdown(now,ll,rr);
        int mid=(ll+rr)/2;
        if(l<=mid)ans+=gsum(ln,ll,mid,l,r);
        if(r>mid)ans+=gsum(rn,mid+1,rr,l,r);
        sum[now]=sum[ln]+sum[rn];    
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>num[i];
    build(1,1,n);
    while(m--)
    {
        cin>>a>>b>>c;
        if(a==1)
        {
            cin>>d;
            add(1,1,n,b,c,d);
        }
        else cout<<gsum(1,1,n,b,c)<<endl;
    }
}

其他板子整理

相关推荐