题目描述

难度分:$1600$

输入$n(1 \leq n \leq 2 \times 10^5)$和两个长为$n$的数组$a$，$b$，元素范围在$[1,10^6]$。

定义$c[i]=a[i] \times b[i]$。定义$S$为$c$的所有非空连续子数组的元素和的和。

你可以重排数组$b$。输出$S$的最小值，模$998244353$。

注意，你需要最小化的是$S$，然后再取模，不是最小化取模后的值。

输入样例$1$

5
1 8 7 2 4
9 7 2 9 3

输出样例$1$

646

输入样例$2$

1
1000000
1000000

输出样例$2$

757402647

输入样例$3$

2
1 3
4 2

输出样例$3$

20

算法

排序不等式

这个题一看就是排序不等式，如果忽略对所有子数组求和的这个要求，仅计算整个数组的$f(0,n-1)=\Sigma_{i \in [0,n)}a[i] \times b[i]$，那只要$a$和$b$反序配对就可以了（$a$升序$b$降序，或$a$降序$b$升序）。

但是本题需要对所有子数组的$f$值求和最小，就需要考虑贡献了。对于一个$a[i]$，一个子数组如果要包含它，左边界可以是$[0,i]$，一共$i+1$个数，右边界可以是$[i,n)$，一共$n-i$个数，$a[i]$会对$(i+1) \times (n-i)$个子数组产生贡献。因此我们应该对$a[i] \times (i+1) \times (n-i)$升序排列，对$b$降序排列（或者反过来），再按照排序不等式进行配对组合。

复杂度分析

时间复杂度

排序完成后只需要遍历$i \in [0,n)$就可以求出答案，因此瓶颈就在于排序，时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的两个数组，只使用了有限几个变量，因此额外空间复杂度就是排序的空间复杂度，以快排为基准是$O(log_2n)$，如果是堆排可以控制在$O(1)$。

$python$代码

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
    a[i] *= (i + 1)*(n - i)
a.sort(key=lambda x: -x)
b.sort()
MOD = 998244353
ans = 0
for i in range(n):
    ans += a[i] * b[i] % MOD
    ans %= MOD
print(ans)