#P16063. [Oni2021国家队选拔赛]Emacs

    ID: 15274 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-贡献法单调栈计算区间贡献枚举较小维度二分查找离散化笛卡尔树

[Oni2021国家队选拔赛]Emacs

题目描述

给定两个长度为 NN 的自然数序列:

V1,V2,…,VNV_1,V_2,\ldots,V_N

和

E1,E2,…,EN.E_1,E_2,\ldots,E_N.

对于每一段连续子序列 [l,r][l,r],若它的两个端点满足:

El=Er,E_l=E_r,

则该子序列会对答案贡献:

max⁡(Vl,Vl+1,…,Vr).\max(V_l,V_{l+1},\ldots,V_r).

请计算所有满足 1≤l≤r≤N1\le l\le r\le N 且 El=ErE_l=E_r 的连续子序列的贡献和,对

1 000 000 0071\,000\,000\,007

取模输出。

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个自然数,表示序列 VV。

第三行包含 NN 个自然数,表示序列 EE。

输出格式

输出一行一个整数,表示所求答案对 1 000 000 0071\,000\,000\,007 取模后的结果。

数据范围与约定

  • 1≤N≤3×1051\le N\le 3\times 10^5;
  • 1≤Vi,Ei≤1091\le V_i,E_i\le 10^9;
  • 连续子序列指下标连续的一段。

子任务

子任务 分值 限制
1 8 N≤2000N\le 2000
2 11 对所有 1≤i≤N1\le i\le N,Ei=1E_i=1
3 12 对所有 1≤i≤N1\le i\le N,Ei≤20E_i\le 20
4 对所有 1≤i≤N1\le i\le N,Vi≤20V_i\le 20
5 19 N≤5×104N\le 5\times 10^4
6 38 无额外限制

样例

5
5 29 3 28 30
9 8 9 9 8
211

样例解释

贡献答案的子序列必须满足两端的 EE 值相等。

本例中,满足条件的区间及其最大值为:

$$(1,1,5),\ (1,3,29),\ (1,4,29),\ (2,2,29),\ (2,5,30),$$(3,3,3), (3,4,28), (4,4,28), (5,5,30).(3,3,3),\ (3,4,28),\ (4,4,28),\ (5,5,30).

这些最大值之和为:

5+29+29+29+30+3+28+28+30=211.5+29+29+29+30+3+28+28+30=211.