注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4127]Abs  

2015-06-20 16:26:28|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4127: Abs

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 121  Solved: 50
[Submit][Status][Discuss]

Description

 给定一棵树,设计数据结构支持以下操作
    1 u v d 表示将路径 (u,v) 加d
    2 u v    表示询问路径 (u,v) 上点权绝对值的和

Input

第一行两个整数n和m,表示结点个数和操作数
接下来一行n个整数a_i,表示点i的权值
接下来n-1行,每行两个整数u,v表示存在一条(u,v)的边
接下来m行,每行一个操作,输入格式见题目描述

Output

对于每个询问输出答案

Sample Input

4 4
-4 1 5 -2
1 2
2 3
3 4
2 1 3
1 1 4 3
2 1 3
2 3 4

Sample Output

10
13
9

HINT

对于100%的数据,n,m <= 10^5 且 0<= d,|a_i|<= 10^8

Solution

树链剖分
维护区间内最大的负数、负数的总数以及答案。每次修改如果不能使一个负数变为非负数,那么打标记,否则递归左右子树。
这样的话,由于每个数只会经过1次从负数变成非负数的过程,因此复杂度是有保证的

Code

/**************************************************************
    Problem: 4127
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:6476 ms
    Memory:18724 kb
****************************************************************/
 
#include<cstdio>
#define rint register int
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa,bb;int F(){
    while(ch=getc(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return bb?aa:-aa;
}
#define N 100010
int n,m,val[N],i,a[N],id[N],top[N],son[N],fa[N],siz[N],dep[N],et,la[N],tim,st,L,R,v;
#define swap(a,b) (st=a,a=b,b=st)
#define abs(x) (x>0?x:-(x))
struct E{int to,nxt;}e[N<<1];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(rint x,rint f){
    dep[x]=dep[fa[x]=f]+1,siz[x]=1;
    for(rint i=la[x];i;i=e[i].nxt)if(e[i].to!=f){
        dfs(e[i].to,x);siz[x]+=siz[e[i].to];
        if(siz[son[x]]<siz[e[i].to])son[x]=e[i].to;
    }
}
void dfs2(rint x,rint tp){
    if(top[x]=tp,a[id[x]=++tim]=x,son[x])dfs2(son[x],tp);
    for(rint i=la[x];i;i=e[i].nxt)
    if(e[i].to!=fa[x]&&e[i].to!=son[x])dfs2(e[i].to,e[i].to);
}
long long ans,sum[1<<18],max[1<<18],add[1<<18],cnt[1<<18];
void mt(rint o){
    sum[o]=sum[o<<1]+sum[o<<1|1],
    cnt[o]=cnt[o<<1]+cnt[o<<1|1],max[o]=max[o<<1];
    if(max[o<<1|1]<0)
    if(max[o]<0)max[o]<max[o<<1|1]?max[o]=max[o<<1|1]:1;else max[o]=max[o<<1|1];
}
void bt(rint o,rint l,rint r){
    if(l==r){
        sum[o]=val[a[l]];
        if(sum[o]<0)max[o]=sum[o],cnt[o]=1,sum[o]=-sum[o];
    }else{
        rint mid=l+r>>1;
        bt(o<<1,l,mid),bt(o<<1|1,mid+1,r);mt(o);
    }
}
void pd(rint o,rint l,rint r){
    if(!add[o])return;
    rint mid=l+r>>1;
    add[o<<1]+=add[o],add[o<<1|1]+=add[o];
    sum[o<<1]+=add[o]*(mid-l+1-2*cnt[o<<1]);
    sum[o<<1|1]+=add[o]*(r-mid-2*cnt[o<<1|1]);
    if(max[o<<1])max[o<<1]+=add[o];
    if(max[o<<1|1])max[o<<1|1]+=add[o];
    add[o]=0;
}
void upd(rint o,rint l,rint r){
    rint mid=l+r>>1;
    if(L<=l&&r<=R){
        if(l==r){
            if(max[o]==0)sum[o]+=v;
            else{
                max[o]+=v;sum[o]=abs(max[o]);
                if(max[o]>=0)max[o]=cnt[o]=0;
            }
        }
        else if(max[o]==0||max[o]+v<0){
            add[o]+=v;sum[o]+=1LL*v*(r-l+1-2*cnt[o]);
            if(max[o])max[o]+=v;
        }
        else{
            pd(o,l,r),upd(o<<1,l,mid),upd(o<<1|1,mid+1,r),mt(o);
        }
        return;
    }
    pd(o,l,r);
    if(L<=mid)upd(o<<1,l,mid);
    if(mid<R)upd(o<<1|1,mid+1,r);
    mt(o);
}
void query(rint o,rint l,rint r){
    if(L<=l&&r<=R){
        ans+=sum[o];return;
    }
    rint mid=l+r>>1;pd(o,l,r);
    if(L<=mid)query(o<<1,l,mid);
    if(mid<R)query(o<<1|1,mid+1,r);
}
int main(){rint x,y,fx,fy;
    for(n=F(),m=F(),i=1;i<=n;i++)val[i]=F();
    for(i=1;i<n;i++)x=F(),y=F(),add(x,y),add(y,x);
    for(dfs(1,0),dfs2(1,1),bt(1,1,n);m--;)
    if(F()==1){
        fx=top[x=F()],fy=top[y=F()],v=F();
        while(fx!=fy){
            if(dep[fx]<dep[fy])swap(x,y),fx=top[x],fy=top[y];
            L=id[fx],R=id[x],upd(1,1,n);x=fa[fx],fx=top[x];
        }
        if(dep[x]>dep[y])swap(x,y);L=id[x],R=id[y],upd(1,1,n);
    }
    else{
        fx=top[x=F()],fy=top[y=F()],ans=0;
        while(fx!=fy){
            if(dep[fx]<dep[fy])swap(x,y),fx=top[x],fy=top[y];
            L=id[fx],R=id[x],query(1,1,n);x=fa[fx],fx=top[x];
        }
        if(dep[x]>dep[y])swap(x,y);L=id[x],R=id[y],query(1,1,n);
        printf("%lld\n",ans);
    }
}
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018