BZOJ-4127: Abs

Description
给定一棵树,设计数据结构支持以下操作
1 u v d 表示将路径 (u,v) 加d
2 u v 表示询问路径 (u,v) 上点权绝对值的和
n,m <= 10^5 0<= d,|a_i|<= 10^8

树链剖分+线段树
由于d一直是正的,所以负数只有在开始的一段时间内是负的。
那么可以在区间加d出现负数变成正数情况的时候进行暴力重构,这种操作的次数不超过n次,复杂度nlogn。
需要维护区间内的非负数的个数(用于给区间加d的时候更新绝对值的和),区间内的最大的负数(判断重构),区间的绝对值的和。
然后线段树的部分就结束了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 101000 
using namespace std;
typedef long long ll;
int n,m,w[101000];
inline void read(int &x)
{
    x=0;int f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=f;
}
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int top[N],tid[N],fa[N],son[N],siz[N],tr[N],deep[N],tot;
void dfs1(int x,int pre)
{
    siz[x]=1; fa[x]=pre; deep[x]=deep[pre]+1;
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=pre)
        {
            dfs1(to[i],x);
            siz[x]+=siz[to[i]];
            if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
        }
}
void dfs2(int x,int anc)
{
    tid[x]=++tot; top[x]=anc; tr[tot]=w[x];
    if(son[x]) dfs2(son[x],anc);
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=fa[x]&&to[i]!=son[x])
            dfs2(to[i],to[i]);
}
int si[N<<2],def[N<<2];
ll sum[N<<2],lz[N<<2];
void pushup(int pos)
{
    def[pos]=0;
    if(def[pos<<1]) def[pos]=def[pos<<1];
    if(def[pos<<1|1]) def[pos]=(def[pos])?max(def[pos],def[pos<<1|1]):def[pos<<1|1];
    si[pos]=si[pos<<1]+si[pos<<1|1];
    sum[pos]=sum[pos<<1]+sum[pos<<1|1];
}
void pushdown(int pos,int l,int r,bool fl1,bool fl2)
{
    if(lz[pos])
    {
        int mid=l+r>>1;
        if(fl1)
        {
            if(def[pos<<1]) def[pos<<1]+=lz[pos];
            sum[pos<<1]+=1ll* (si[pos<<1]*2 - (mid-l+1)) *lz[pos];
            lz[pos<<1]+=lz[pos];
        }
        if(fl2)
        {
            if(def[pos<<1|1]) def[pos<<1|1]+=lz[pos];
            sum[pos<<1|1]+=1ll* (si[pos<<1|1]*2 - (r-mid)) *lz[pos];
            lz[pos<<1|1]+=lz[pos];
        }
        lz[pos]=0;
    }
}
void build(int pos,int l,int r)
{
    if(l==r)
    {
        if(tr[l]<0) def[pos]=tr[l],sum[pos]=-tr[l];
        else si[pos]=1,sum[pos]=tr[l];
        return ;
    }
    int mid=l+r>>1;
    build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
    pushup(pos);
}
void rebuild(int pos,int l,int r,ll z)//当前区间应当加上一个z,然而没有加,重构当前区间。
{
    if(l==r) {sum[pos]=def[pos]+z; def[pos]=0; si[pos]=1; return;}
    int mid=l+r>>1; z+=lz[pos]; lz[pos]=z;
    if(def[pos<<1]&&def[pos<<1]+z>=0&&def[pos<<1|1]&&def[pos<<1|1]+z>=0)
    {
        lz[pos]=0;
        rebuild(pos<<1,l,mid,z);
        rebuild(pos<<1|1,mid+1,r,z);
    }
    else if(def[pos<<1]&&def[pos<<1]+z>=0)
    {
        pushdown(pos,l,r,0,1);
        rebuild(pos<<1,l,mid,z);
    }
    else if(def[pos<<1|1]&&def[pos<<1|1]+z>=0)
    {
        pushdown(pos,l,r,1,0);
        rebuild(pos<<1|1,mid+1,r,z);
    }
    pushup(pos);
}
void fix(int pos,int l,int r,int x,int y,int z)
{
    if(x<=l&&y>=r)
    {
        if(def[pos]&&def[pos]+z>=0) rebuild(pos,l,r,z);
        else
        {
            if(def[pos]) def[pos]+=z; lz[pos]+=z;
            sum[pos]+=1ll*(si[pos]*2-(r-l+1))*z;
        }
        return ;
    }
    int mid=l+r>>1;  pushdown(pos,l,r,1,1);
    if(y<=mid) fix(pos<<1,l,mid,x,y,z);
    else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,z);
    else fix(pos<<1,l,mid,x,y,z),fix(pos<<1|1,mid+1,r,x,y,z);
    pushup(pos);
}
ll query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&y>=r) return sum[pos];
    int mid=l+r>>1; pushdown(pos,l,r,1,1);
    if(y<=mid) return query(pos<<1,l,mid,x,y);
    else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
    else return query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y);
}
void Fix()
{
    int x,y,z; scanf("%d%d%d",&x,&y,&z);
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        fix(1,1,n,tid[top[x]],tid[x],z);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    fix(1,1,n,tid[x],tid[y],z);
}
void Query()
{
    int x,y; ll ans=0; scanf("%d%d",&x,&y);
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        ans+=query(1,1,n,tid[top[x]],tid[x]);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    ans+=query(1,1,n,tid[x],tid[y]);
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d%d",&n,&m); int i,x,y;
    for(i=1;i<=n;++i) read(w[i]);
    for(i=1;i!=n;++i)
    {
        read(x); read(y);
        add(x,y); add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--)
    {
        scanf("%d",&x);
        if(x==1) Fix();
        else Query();
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注