AT_arc169_f [ARC169F] Large DP Table

给定长度为 $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$。 - 当 $(i,j)\neq (1,1)$ 且 $A_i < B_j$ 时：$d_{i,j}=d_{i,j-1}+X_i$。 - 当 $(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$ 取模的结果。

输入通过标准输入给出，格式如下： > $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$

输出答案。

## 限制条件 - $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$。 - 输入的所有值均为整数。 ## 样例解释 1 $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$。 由 ChatGPT 4.1 翻译