← 返回题目列表

AtCoder · arc169_f

F. 大型 DP 工作台

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给定长度的整数序列 N: A=(A_1,A_2,\cdots,A_N), B=(B_1,B_2,\cdots,B_N), X=(X_1,X_2,\cdots,X_N),和 Y=(Y_1,Y_2,\cdots,Y_N)。在这里, A 和 B 满足以下属性:

  • A_1=1.
  • B_1=2.
  • (A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N) 是一个排列 (1,2,\cdots,2N).

定义整数 d_{i,j} (1 \leq i,j \leq N)如下:

  • d_{1,1}=0.
  • If (i,j) \neq (1,1) 和 A_i<B_j,那么 d_{i,j}=d_{i,j-1}+X_i.
  • If (i,j) \neq (1,1) 和 A_i>B_j,那么 d_{i,j}=d_{i-1,j}+Y_j.

查找 \sum_{1 \leq i \leq N}\sum_{1 \leq j \leq N}d_{i,j},模数 998244353.

约束

  • 2 \leq N \leq 250000
  • A_1=1
  • B_1=2
  • (A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N) 是一个排列 (1,2,\cdots,2N).
  • 1 \leq X_i \leq 10^9
  • 1 \leq Y_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
X_1 X_2 \cdots X_N
Y_1 Y_2 \cdots Y_N

输出

打印答案。


示例输入 1

2
1 4
2 3
2 2
1 3

示例输出 1

8

的值 d_{i,j} 如下:

  • d_{1,1}=0
  • d_{1,2}=d_{1,1}+X_1=0+2=2
  • d_{2,1}=d_{1,1}+Y_1=0+1=1
  • d_{2,2}=d_{1,2}+Y_2=2+3=5

因此,答案是 0+2+1+5=8.


示例输入 2

3
1 3 5
2 6 4
1 10 100
1000 10000 100000

示例输出 2

108153

示例输入 3

3
1 6 5
2 4 3
1 10 100
1000 10000 100000

示例输出 3

333009

示例输入 4

10
1 17 4 7 16 18 9 3 12 6
2 19 20 14 5 11 13 8 15 10
744280520 249168130 239276621 320064892 910500852 164832983 245532751 198319687 715892722 967824729
769431650 80707350 459924868 257261830 777045524 583882654 950300099 438099970 322288793 532405020

示例输出 4

746075419