题目描述:

$N$ 个柱子排成一排,一开始每个柱子损伤度为0。

接下来勇仪会进行$M$ 次攻击,每次攻击可以用4个参数$l$ ,$r$ ,$s$ ,$e$ 来描述:

表示这次攻击作用范围为第$l$ 个到第$r$ 个之间所有的柱子(包含$l$ ,$r$ ),对第一个柱子的伤害为$s$ ,对最后一个柱子的伤害为$e$ 。

攻击产生的伤害值是一个等差数列。若$l=1$ ,$r=5 $, $s=2$ ,$e=10$ ,则对第1~5个柱子分别产生2,4,6,8,10的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

输入输出格式

输入格式:

第一行2个整数 $N$ , $M$ ,用空格隔开,下同。

接下来 $M$ 行,每行4个整数 $l$ , $r$ , $s$ ,$e$ ,含义见题目描述。

数据保证对每个柱子产生的每次伤害值都是整数。

输出格式:

由于输出数据可能过大无法全部输出,为了确保你真的能维护所有柱子的损伤度,只要输出它们的异或和与最大值即可。

(异或和就是所有数字按位异或起来的值)

(异或运算符在c++里为^)

数据范围:

本题满分为100分,下面是4个子任务。(x/y)表示(得分/测试点数量)

妖精级(18/3): $1⩽n ,m⩽1000$ 。这种工作即使像妖精一样玩玩闹闹也能完成吧?

河童级(10/1): $s=e$ ,这可以代替我工作吗?

天狗级(20/4): $1⩽n⩽1e5$ , $1⩽m⩽1e5$ 。小打小闹不再可行了呢。

鬼神级(52/2):没有特殊限制。要真正开始思考了。

以上四部分数据不相交。

对于全部的数据: $1⩽n⩽1e7$ , $1⩽m⩽3×1e5$ ,$1⩽l<r⩽n$ .

所有输入输出数据以及柱子受损伤程度始终在$[0,9×1e18]$ 范围内。

这题n<=1e7,看上去有点吓人?同时也是很大的提示:使用O(N)甚至更低的数据结构

我们来看一下这题的需求,区间加一个等差数列,一开始就可以想到N log n的 差分+线段树 经典做法。

a[l]~a[r]加上一个首项为x,公比为y的等差数列的做法

设b数组为a数组的差分数列

则:$b[l]+=x$,$b[l]~b[r]+=y$.$b[r+1]-=(r-l)*y$ (末项)

我们发现如果用线段树去维护它的话,只是一个区间加,查询操作只有最后一次。

考虑到不用查询,我们就可以放弃线段树,维护a数列的差分数列b的差分数列c

似乎有点绕口?没关系可以自己模拟一下

反正就是这样,然后把所有操作都变成区间加。

差分数列区间加的方法区间$(l,r)$加x,$c[l]+=x$,$c[r+1]-=x$;

最后查询求一遍前缀和,完了!!!

05-27 13:06