Abs bzoj-4127
题目大意：给定一棵数，支持链加和链上权值的绝对值的和。
注释：$1le n,m le 10^5$，$delta ge 0$，$|a_i|le 10^8$。
想法：看完题，以为又是什么数据结构裸题。然后发现绝对值... ...卧槽？啥jb玩意儿？绝对值？这怎么加？开始的想法是维护一个do标记，表示这个区间有没有负值，如果没有直接懒标记，如果有，往下走的时候负数取出来，然后二分治... ...不想写，上网查的题解。我们先树链剖分之后建线段树。紧接着我们对于一段区间维护一个小信息：maxdown。表示这个点所代表的区间中的所有负值中的最大值的绝对值。我们发现所有的增量都是正的，所以每一个数的正负号只能变动一次并且只能从负号变成正号。所以在区间修改的时候如果这个区间有负值我们就暴力修改即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define lson l,mid,x<<1
#define rson mid+1,r,x<<1|1
using namespace std;
typedef long long ll;
const int inf=1<<30;
int a[N],head[N],to[N<<1],next[N<<1],cnt,fa[N],deep[N],sv[N],bl[N],pos[N],tot,v[N];
int n,val[N<<2],si[N<<2],add[N<<2];
ll sum[N<<2];
void addedge(int x,int y)
{
to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x)
{
sv[x]=1;
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x])
fa[to[i]]=x,deep[to[i]]=deep[x]+1,dfs1(to[i]),sv[x]+=sv[to[i]];
}
void dfs2(int x,int c)
{
int k=0;
bl[x]=c,pos[x]=++tot,v[tot]=a[x];
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x]&&sv[to[i]]>sv[k])
k=to[i];
if(k)
{
dfs2(k,c);
for(int i=head[x];i;i=next[i])
if(to[i]!=fa[x]&&to[i]!=k)
dfs2(to[i],to[i]);
}
}
void pushup(int x)
{
int l=x<<1,r=x<<1|1;
sum[x]=sum[l]+sum[r];
if(val[l]>0&&val[r]>0)val[x]=min(val[l],val[r]);
else if(val[l]>0)val[x]=val[l];
else if(val[r]>0)val[x]=val[r];
else val[x]=0;
si[x]=si[l]+si[r];
}
void pushdown(int x)
{
if(add[x])
{
int l=x<<1,r=x<<1|1;
sum[l]+=(ll)si[l]*add[x],val[l]-=add[x],add[l]+=add[x];
sum[r]+=(ll)si[r]*add[x],val[r]-=add[x],add[r]+=add[x];
add[x]=0;
}
}
void build(int l,int r,int x)
{
if(l==r)
{
if(v[l]<0) sum[x]=val[x]=-v[l],si[x]=-1;
else sum[x]=v[l],val[x]=0,si[x]=1;
return;
}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(x);
}
void update(int b,int e,int a,int l,int r,int x)
{
if(b<=l&&r<=e&&(val[x]<=0||val[x]>a)) sum[x]+=(ll)si[x]*a,val[x]-=a,add[x]+=a;
else if(l==r) sum[x]=a-sum[x],val[x]=0,si[x]=1;
else
{
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) update(b,e,a,lson);
if(e>mid) update(b,e,a,rson);
pushup(x);
}
}
ll query(int b,int e,int l,int r,int x)
{
if(b<=l&&r<=e)return sum[x];
pushdown(x);
int mid=(l+r)>>1;
ll ans=0;
if(b<=mid)ans+=query(b,e,lson);
if(e>mid)ans+=query(b,e,rson);
return ans;
}
void modify(int x,int y,int z)
{
while(bl[x]!=bl[y])
{
if(deep[bl[x]]<deep[bl[y]])swap(x,y);
update(pos[bl[x]],pos[x],z,1,n,1),x=fa[bl[x]];
}
if(deep[x]>deep[y])swap(x,y);
update(pos[x],pos[y],z,1,n,1);
}
ll solve(int x,int y)
{
ll ans=0;
while(bl[x]!=bl[y])
{
if(deep[bl[x]]<deep[bl[y]])swap(x,y);
ans+=query(pos[bl[x]],pos[x],1,n,1),x=fa[bl[x]];
}
if(deep[x]>deep[y])swap(x,y);
ans+=query(pos[x],pos[y],1,n,1);
return ans;
}
int main()
{
int m,opt,x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++)scanf("%d%d",&x,&y),addedge(x,y),addedge(y,x);
dfs1(1),dfs2(1,1),build(1,n,1);
while(m--)
{
scanf("%d%d%d",&opt,&x,&y);
if(opt==1)scanf("%d",&z),modify(x,y,z);
else printf("%lld
",solve(x,y));
}
return 0;
}
小结：注意题目中的数据范围，对于一些比较特殊的性质要发掘并利用。