U163913 [NOI2021SDPT2Test2]AI高考数学134分

这是一道AI高考数学134分题。 你有 400 台 tesla 显卡，现在你需要做一道题来激活神经元之间的连接，从而通过自动证明和推理得出解题结果： 给出三个长度 $n$ 的正整数序列 $A,B,C$。 定义 $f(X,l,r)$ 为在序列 $X$ 中，区间 $[l,r]$ 的最大值减去区间 $[l,r]$ 的最小值的差。 定义一个区间 $[l,r]$ 的权值为 $f(A,l,r)\times f(B,l,r)\times f(C,l,r)$。 求对于所有 $1\leq l\leq r\leq n$，区间 $[l,r]$ 的权值之和，由于答案可能比较大，所以输出答案对 $2^{32}$ 取模的结果。

第一行一个整数 $n$。 之后三行，每行 $n$ 个正整数，分别表示 $A,B,C$ 三个序列。

一行一个数表示答案。

本题采用子任务评测。 对于 $20\%$ 的数据，满足 $1\leq n\leq 2\times 10^3$。 对于另外 $20\%$ 的数据，满足 $A,B,C$ 序列分别单调不减。 对于另外 $20\%$ 的数据，满足 $A$ 序列均为 $1$。 对于 $100\%$ 的数据，满足 $1\leq n\leq 10^5,1\leq A_i,B_i,C_i \leq 10^9$。 不用注意常数因子带来的影响。