AT_arc158_e.[ARC158E] All Pair Shortest Paths

有一个 $2$ 行 $N$ 列的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。在 $(i,j)$ 这个格子上写有正整数 $x_{i,j}$。

如果两个格子有公共边，则称它们相邻。

从格子 $X$ 到格子 $Y$ 的路径，是指由若干互不相同的格子组成的序列 $(P_1,\ \ldots,\ P_n)$，满足 $P_1 = X$，$P_n = Y$，并且对于任意 $1 \leq i \leq n-1$，$P_i$ 和 $P_{i+1}$ 相邻。该路径的权值定义为 $P_1,\ldots,P_n$ 上所写整数的总和。

对于任意两个格子 $X,\ Y$，记 $f(X,\ Y)$ 为从 $X$ 到 $Y$ 的所有路径中权值的最小值。

请你求出所有格子对 $(X,Y)$ 的 $f(X,\ Y)$ 之和，并对 $998244353$ 取模。

输入以如下格式从标准输入读入：

$N$ $x_{1,1}$ $\ldots$ $x_{1,N}$ $x_{2,1}$ $\ldots$ $x_{2,N}$

输出所有格子对 $(X,Y)$ 的 $f(X,\ Y)$ 之和对 $998244353$ 取模的结果。

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq x_{i,j} \leq 10^9$

样例解释 1

需要计算以下 $4$ 种情况的总和：

• $X = (1,1), Y = (1,1)$ 时：$f(X,Y) = 3$。
• $X = (1,1), Y = (2,1)$ 时：$f(X,Y) = 8$。
• $X = (2,1), Y = (1,1)$ 时：$f(X,Y) = 8$。
• $X = (2,1), Y = (2,1)$ 时：$f(X,Y) = 5$。

由 ChatGPT 4.1 翻译