1. 题目

2. 题解

可以说这题令我非常angry。。。

其实不难,就一个splay区间加&区间乘,结果写我这么久!

我屮艸芔茻,因为在学校写的时候思路被中断了,所以代码就写得非常Silly B且不可debug。。。

浪费我好多时间哟QvQ

最后回家以后一下子就写出来惹QvQ

其实我们只要灵活地运用splay的提取区间操作就行了。

对于区间加和区间乘应该没啥好说的。

唯一要注意的地方是要先下放乘法标记,再下放加法标记!

下放标记(push_down)的代码:

然后区间次数加一的话,就等于将区间右端点的值加到区间右端点的右边的点上,再把区间右端点的值归零,最后区间顺时针旋转1个位置即可。

对此,我们可以先提取出只有右端点一个元素的区间(即区间[r,r]),然后切断它与整个序列的联系,接着提取出只有左端点一个元素的区间(即区间[l,l]),并push_down左儿子!并push_down左儿子!并push_down左儿子!(重要的事情说三遍!一定要记得push_down!我™前面就忘了!)。这时候左端点对应的节点没有左儿子,直接把已经与序列切断联系的右端点接到左端点的左儿子上,就相当于把区间旋转了1个位置。然后再提取出只有原来区间右端点右边的那个节点的区间(即区间[r+1,r+1]),并把这个节点的值加上刚刚的右端点的值,并把刚刚的右端点的值设为0。

于是我们就很愉悦♂地实现了这个mulx操作啦!

这个操作的代码:

这个故事告诉我们要灵活运用splay的获取区间操作QvQ

查询操作就递归就行了,中序遍历。查询操作代码如下:

还有一点小细节:

  • 一开始建树应该建大小为$10^5+n+2$的大小的树,那个2是两个哨兵节点,初始节点值为0(节点值保存系数),多了节点没关系的QvQ,不影响答案
  • 记得开long long QvQ坑死惹!

整道题の代码: