4127: Abs
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 381 Solved: 132
[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
-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
13
9
HINT
对于100%的数据，n,m <= 10^5 且 0<= d,|a_i|<= 10^8
Source
Solution
树链剖分显然,把树上路径问题转化为序列问题
然后线段树维护区间权值绝对值和,支持区间加
注意Delta>=0这个条件,即1操作保证加数不为负,即实际值不发生减小
于是线段树维护一些东西:
l,r左右端点;maxf区间最大负数;num区间正数个数-负数个数;tag区间加的标记;sum区间绝对值和
maxf的意义在于,对于区间加Delta,那么如果maxf+Delta<0很显然1操作后会出现变号的情况,对于维护绝对值和必然会做出影响,所以用来进行判断
num的意义在于计算sum的变化,这里同样可以考虑维护正数个数和负数个数,但Code起来比较不方便
tag的意义在于,如果区间+Delta不发生变号情况(即maxf+Delta<0||maxf>=0)的时候,可以直接打上标记,否则则需要把标记下放至叶节点,在向上更新答案
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 110000
int n,m,a[maxn];
struct Edgenode{int to,next;}edge[maxn<<];
int head[maxn],cnt=;
void add(int u,int v){cnt++; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt;}
void insert(int u,int v){add(u,v); add(v,u);}
//----------------------------------------------------------------------------------
int size[maxn],fa[maxn],deep[maxn],son[maxn],pl[maxn],sz,pre[maxn],top[maxn],pr[maxn];
void dfs_1(int now)
{
size[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=fa[now])
{
fa[edge[i].to]=now;
deep[edge[i].to]=deep[now]+;
dfs_1(edge[i].to);
if (size[son[now]]<size[edge[i].to]) son[now]=edge[i].to;
size[now]+=size[edge[i].to];
}
}
void dfs_2(int now,int chain)
{
pl[now]=++sz; pre[sz]=a[now]; top[now]=chain;
if (son[now]) dfs_2(son[now],chain);
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=son[now] && edge[i].to!=fa[now])
dfs_2(edge[i].to,edge[i].to);
pr[now]=sz;
}
//----------------------------------------------------------------------------------
struct TreeNode
{
int l,r;long long maxf,tag,sum,num;
void Add(int k)
{
if (k<) maxf=k,sum=-k,num=-;
else maxf=,sum=k,num=;
tag=;
}
}tree[maxn<<];
long long Maxf(long long x,long long y)
{
if (x>= && y>=) return ;
if (x>= || y>=) return min(x,y);
return max(x,y);
}
void Update(int now)
{
tree[now].maxf=Maxf(tree[now<<].maxf,tree[now<<|].maxf);
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
tree[now].num=tree[now<<].num+tree[now<<|].num;
}
void BuildTree(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r;
if (l==r) {tree[now].Add(pre[l]); return;}
int mid=(l+r)>>;
BuildTree(now<<,l,mid); BuildTree(now<<|,mid+,r);
Update(now);
}
void Pushdown(int now)
{
if (!tree[now].tag || tree[now].l==tree[now].r) return;
int tag=tree[now].tag; tree[now].tag=;
tree[now<<].maxf+=tag; tree[now<<].sum+=tree[now<<].num*tag; tree[now<<].tag+=tag;
tree[now<<|].maxf+=tag; tree[now<<|].sum+=tree[now<<|].num*tag; tree[now<<|].tag+=tag;
}
void Change(int now,int L,int R,int D)
{
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r && (tree[now].maxf>= || tree[now].maxf+D<))
{tree[now].maxf+=D; tree[now].sum+=(long long)tree[now].num*D; tree[now].tag+=D; return;}
if (l==r) {tree[now].Add(tree[now].maxf+D); return;}
Pushdown(now);
int mid=(l+r)>>;
if (L<=mid) Change(now<<,L,R,D);
if (R>mid) Change(now<<|,L,R,D);
Update(now);
}
long long Query(int now,int L,int R)
{
Pushdown(now);
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) return tree[now].sum;
int mid=(l+r)>>; long long re=;
if (L<=mid) re+=Query(now<<,L,R);
if (R>mid) re+=Query(now<<|,L,R);
return re;
}
void DeBug(int now)
{
int l=tree[now].l,r=tree[now].r;
if (l==r) {printf("l==r=%d Val=%d maxf=%lld tag=%lld sum=%lld num=%lld\n",l,a[l],tree[now].maxf,tree[now].tag,tree[now].sum,tree[now].num);return;}
int mid=(l+r)>>;
DeBug(now<<); DeBug(now<<|);
}
//----------------------------------------------------------------------------------
void Solve_1(int x,int y,int D)
{
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
Change(,pl[top[x]],pl[x],D);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
Change(,pl[x],pl[y],D);
}
long long Solve_2(int x,int y)
{
long long re=;
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
re+=Query(,pl[top[x]],pl[x]);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
re+=Query(,pl[x],pl[y]);
return re;
}
//----------------------------------------------------------------------------------
int main()
{
// freopen("4127.in","r",stdin);
// freopen("4127.out","w",stdout);
n=read(),m=read();
for (int i=; i<=n; i++) a[i]=read();
for (int u,v,i=; i<=n-; i++) u=read(),v=read(),insert(u,v);
dfs_1(); dfs_2(,); BuildTree(,,n);
int opt,u,v,w;
while (m--)
{
opt=read();
// DeBug(1);
if (opt==) u=read(),v=read(),w=read(),Solve_1(u,v,w);
else u=read(),v=read(),printf("%lld\n",Solve_2(u,v));
}
return ;
}
友情附送数据生成器:(Designed by YveH)
#include<ctime>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
freopen("4127.in","w",stdout);
srand(time());
int n=,q=;
printf("%d %d\n",n,q);
for (int i=;i<=n;i++)
printf("%d ",rand()%-);
printf("\n");
for (int i=;i<=n;i++)
printf("%d %d\n",i,rand()%(i-)+);
for (int i=;i<=q;i++)
{
int opt=rand()%+;
printf("%d ",opt);
if (opt==)
printf("%d %d %d\n",rand()%n+,rand()%n+,rand()%);
if (opt==)
printf("%d %d\n",rand()%n+,rand()%n+);
}
return ;
}
数据生成器
友情附送对拍:(Designed by YveH)
#include<iostream>
#include<cstdio>
#include<windows.h>
using namespace std;
int main()
{
while ()
{
system("4127data.exe");
system("4127.exe");
system("4127STD.exe");
if (system("fc 4127.out 4127std.out"))
break;
}
return ;
}
对拍
这道破题,两天前YveH和Etienne写了半天多,DCrusher大爷嘲讽他们,我替他们不服,然后自己果断写了1小时,然后调了3小时....发现自信写不错的链剖少打了一句话MDZZ
(加上省队集训,第三题暴力打到70%就去吃饭了,回来懒得打了,体验了连续滚粗的快感)
发现自己的常数已经接近Etienne了...就慢个100ms不到