极差

[编程题]极差

热度指数：1 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出三个长度为n的正整数序列，一个区间[L,R]的价值定义为：三个序列中，这个区间的极差（最大值与最小值之差）的乘积。
求所有区间的价值之和。答案对2³²取模。

输入描述:

第一行一个整数n
接下来三行，每行n个正整数，分别表示三个序列

输出描述:

一行，一个整数，表示答案

示例1

输入

输出

备注:

1≤ n ≤ 10⁵
序列中的值为不超过10⁹的正整数

算法知识视频讲解

苟且的狮子

发表于 2021-03-13 13:45:21

线段树线段树是我的弱项我们来看这一题：要维护值得乘积对 abc如果a发生变化，那么我们要是知道b*c则只要加上a得增量就好了基于着中国想法，我们使用了线段树。我们一共开了7棵线段树！先开三棵a,b,c在我们的线段树所开的数组中记录的点seg[x]是，从点x到目前边界的极差线段树维护这个极差的展开全文