主题

主题

 
   

4127: Abs

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4127

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


个人解法:

开始以为d也是可正可负,想了好久没有想出怎么维护。后来发现d是一个非负数……

那么一下子变得十分好维护了。

先树链剖分,然后变成序列上的询问。

考虑如果一次加法中,没有负数变为非负数。那么我们可以选择维护 “区间负数的个数” 来完成对 “区间绝对值之和” 的更新。

如果有负数变为正数:

  • 如何判断?

维护区间绝对值最小的负数以及其位置即可。

  • 怎样更新?

在线段树底端暴力修改,再合并上来。


细节问题:

  • 如果是一个负数修改之后变为0,也要视为其变为了负数,并且在底端暴力修改,再合并上来。

  • 在底端暴力修改的时候,可能需要底端节点的信息。因此为了保证底端节点信息正确,需要先下传 底端节点 到 根 沿途所有的节点的tag。


代码如下:

https://code.csdn.net/snippets/2158903

 
 
评论