社区讨论

什么样的码风算好码风?

灌水区参与者 33已保存回复 54

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
54 条
当前快照
1 份
快照标识符
@mi7y2568
此快照首次捕获于
2025/11/21 05:29
4 个月前
此快照最后确认于
2025/11/21 06:57
4 个月前
查看原帖
被老师吐槽不好看懂。。。
CPP
#include <cstdio>
#include <algorithm>
#define N 400010
#define LL long long
using namespace std;
LL n,m;
LL val[N],head[N],next[N],vec[N],edge;//存图相关
LL depth[N],f[N],size[N],mson[N];//dfs1相关
LL new_num[N],new_val[N],top[N],cnt;//dfs2相关
long long w[N],tag[N];//线段树相关
void add(LL x,LL y)
{
    vec[++edge]=y;
    next[edge]=head[x];
    head[x]=edge;
}
LL dfs1(LL u,LL fa,LL dep)
{
    depth[u]=dep;
    f[u]=fa;
    size[u]=1;
    LL mval=-1;
    for(LL i=head[u];i;i=next[i])
    {
        if(vec[i]==fa) continue;
        size[u]+=dfs1(vec[i],u,dep+1);
        if(size[vec[i]]>mval) mval=size[vec[i]],mson[u]=vec[i];
    }
    return size[u];
}
void dfs2(LL u,LL now_top)
{
    new_num[u]=++cnt;//访问顺序作为新编号
    new_val[cnt]=val[u];
    top[u]=now_top;
    if(!mson[u]) return;
    dfs2(mson[u],now_top);
    for(LL i=head[u];i;i=next[i])
     if(!new_num[vec[i]]) dfs2(vec[i],vec[i]);
    return;
}
void build(LL l,LL r,LL p)
{
    if(l==r) {w[p]=new_val[l];return;}
    LL mid=(l+r)>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    w[p]=w[p<<1]+w[p<<1|1];
    return;
}
void down(LL l,LL r,LL p)
{
    if(!tag[p]) return;
    LL mid=(l+r)>>1;
    w[p<<1]+=(mid-l+1)*tag[p];
    w[p<<1|1]+=(r-mid)*tag[p];
    tag[p<<1]+=tag[p];
    tag[p<<1|1]+=tag[p];
    tag[p]=0;
    return;
} 
void p_add(LL l,LL r,LL p,LL x,LL v)
{
    if(l==r) {w[p]+=v;return;}
    down(l,r,p);
    LL mid=(l+r)>>1;
    if(x<=mid) p_add(l,mid,p<<1,x,v);
    else p_add(mid+1,r,p<<1|1,x,v);
    w[p]=w[p<<1|1]+w[p<<1];
    return;
}
void sum_add(LL l,LL r,LL p,LL x,LL y,LL v)
{
    if(x<=l&&y>=r)
    {
        w[p]+=(r-l+1)*v;
        tag[p]+=v;
        return;
    }
    down(l,r,p);
    LL mid=(l+r)>>1;
    if(x<=mid) sum_add(l,mid,p<<1,x,y,v);
    if(y>mid) sum_add(mid+1,r,p<<1|1,x,y,v);
    w[p]=w[p<<1]+w[p<<1|1];
    return;
}
long long query(LL l,LL r,LL p,LL x,LL y)
{
    long long ans=0;
    if(l>=x&&r<=y) return w[p];
    down(l,r,p);
    LL mid=(l+r)>>1;
    if(x<=mid) ans+=query(l,mid,p<<1,x,y);
    if(y>mid) ans+=query(mid+1,r,p<<1|1,x,y);
    return ans;
}
long long t_query(LL x,LL y)
{
    long long ans=0;
    while(top[x]!=top[y])
    {
        if(depth[top[x]]<depth[top[y]]) swap(x,y);
        ans+=query(1,n,1,new_num[top[x]],new_num[x]);
        x=f[top[x]];
    }
    if(depth[x]>depth[y]) swap(x,y);
    ans+=query(1,n,1,new_num[x],new_num[y]);
    return ans;
}
int main()
{
    LL x,y,op;
    scanf("%lld%lld",&n,&m);
    for(LL i=1;i<=n;i++) scanf("%lld",&val[i]);
    for(LL i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,n,1);
    while(m--)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld %lld",&x,&y);
            p_add(1,n,1,new_num[x],y);
        }
        if(op==2)
        {
            scanf("%lld %lld",&x,&y);
            sum_add(1,n,1,new_num[x],new_num[x]+size[x]-1,y);
        }
        if(op==3)
        {
            scanf("%lld",&x);
            printf("%lld\n",t_query(1,x));
        }
    }
    return 0;
}

回复

54 条回复,欢迎继续交流。

正在加载回复...