区间统计问题(Subarray Range Count)

题目描述

小 Z 有两个长度为 $n$ 的序列 $A=\{a_1,a_2,\cdots,a_n\},B=\{b_1,b_2,\cdots,b_n\}$。

现在，要求表达式 $\sum_{l=1}^n\sum_{r=l}^n \max(a_l,a_{l+1},\cdots,a_r)\cdot b_r$ 的值。

输入格式

第一行输入一个正整数 $n$ 表示序列长度。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行输入 $n$ 的整数 $b_1,b_2,\cdots,b_n$。

输出格式

输出一行一个整数表示答案。

样例输入 #1

5
1 4 3 5 2
1 2 3 4 5

样例输出 #1

240

数据范围

对于 $50\%$ 的数据，$n\le 5000$

对于 $80\%$ 的数据，$n\le 10^6$

对于 $100\%$ 的数据，$n\le 10^7,-100\le a_i \le 100,-100 \le b_i \le 100$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接