#P18931. [2026多校联测]观测窗口

[2026多校联测]观测窗口

观测窗口

题目描述

气象台把一天的观测结果按记录时间排成了一列。这一天共有 nn 条记录,编号恰好是 11 到 nn,每个编号只出现一次。第 ii 条记录的编号为 pip_i,质量分数为 cic_i。

工作人员准备从中截取一段连续的记录,作为一次观测的回放窗口。一个窗口可以只含一条记录,也可以包含全部记录。如果窗口内出现的编号恰好是一段连续的整数,就称它为完整窗口。编号在窗口内的排列顺序没有要求。

例如,编号依次为 3,1,23,1,2 的三条记录可以组成完整窗口,因为它们包含的编号恰好是 1,2,31,2,3;编号依次为 3,13,1 的两条记录不能组成完整窗口,因为缺少编号 22。

一个窗口的分数是其中所有记录的质量分数之和,窗口的价值是这个分数的平方。请计算所有完整窗口的价值之和,并输出它除以 998244353998244353 的余数。

两个窗口只要选取的起始位置或结束位置不同,就分别计算。

输入格式

第一行一个整数 nn。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示记录的编号。

第三行 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n,其中 cic_i 是第二行第 ii 条记录的质量分数。

输出格式

输出一个整数,表示所有完整窗口的价值之和除以 998244353998244353 的余数。

样例 1 输入

4
2 1 4 3
1 2 3 4

样例 1 输出

188

样例 1 解释

四个只含一条记录的窗口都是完整窗口,价值之和为 12+22+32+42=301^2+2^2+3^2+4^2=30。

另外三个完整窗口分别是位置 [1,2][1,2]、[3,4][3,4] 和 [1,4][1,4],价值分别为 32=93^2=9、72=497^2=49、102=10010^2=100。因此答案为 30+9+49+100=18830+9+49+100=188。

样例 2 输入

3
3 2 1
0 1 0

样例 2 输出

4

样例 2 解释

任意一段连续记录都是完整窗口。含有第二条记录的四个窗口分数均为 11,其余窗口的分数为 00,所以答案为 44。

样例 3

见下发目录中的 chronicle/3.in 和 chronicle/3.ans。

数据范围与子任务

对于所有测试数据,保证 1≤n≤2000001\le n\le200000,p1,p2,…,pnp_1,p_2,\ldots,p_n 是 11 到 nn 的一个排列,0≤ci≤1090\le c_i\le10^9。

各子任务独立整组计分,通过一组中的全部测试点才能获得该组分数,各组之间没有依赖关系。

子任务 分值 额外约束
1 20 n≤200n\le200
2 pi=ip_i=i 对所有 ii 成立,或 pi=n+1−ip_i=n+1-i 对所有 ii 成立
3 n≤5000n\le5000
4 40 无额外约束