题目描述:
$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$;
最后查询求一遍前缀和,完了!!!