题目描述

一个长度为$n$的序列a，有$m$次操作:

1.将第$x$个数加上$k$;

2.求出区间 $[l,r]$ 中所有数的两两乘积的和;

3.求出区间 $[l,r]$ 中所有相邻两数的乘积和;

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示序列 $a$。

后面 $m$ 行：

• 1 x k: 将第$x$个数加上$k$;

• 2 l r: 求出区间 $[l,r]$ 中所有数的两两乘积的和;

• 3 l r: 求出区间 $[l,r]$ 中所有相邻两数的乘积和;

输出格式

对于每个询问，输出一个数表示答案并换行。

输出的答案都需要对$998244353$取模。

数据范围$1\le n,m\le 2*10^5,0\le k\le 10^5,1\le a_i\le 10^9,1\le x,l,r \le n$

---

显然可以用线段树维护：2操作的结果，3操作的结果和区间和。

但是在2操作小段合成大段时我写成了这样：

return (sum_2(o*2,l,mid,x,y)+sum_2(o*2+1,mid+1,r,x,y)+sum(o*2,l,mid,x,y)*sum(o*2+1,mid+1,r,x,y))%Mod;

即每次合并都需要再求一次sum操作，这样时间复杂度显然是不对的。所以请问各位dalao有什么方法能让时间复杂度从$O(nlog^2n)$（我不确定，也不会求）左右降低一些吗？

---