E. Two Arrays and Sum of Functions

You are given two arrays a and b, both of length n.

Let’s define a function f(l,r)=∑l≤i≤rai⋅bi.

Your task is to reorder the elements (choose an arbitrary order of elements) of the array b to minimize the value of ∑1≤l≤r≤nf(l,r). Since the answer can be very large, you have to print it modulo 998244353. Note that you should minimize the answer but not its remainder.

Input
The first line of the input contains one integer n (1≤n≤2⋅1e5) — the number of elements in a and b.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤1e6), where ai is the i-th element of a.

The third line of the input contains n integers b1,b2,…,bn (1≤bj≤1e6), where bj is the j-th element of b.

Output
Print one integer — the minimum possible value of ∑1≤l≤r≤nf(l,r) after rearranging elements of b, taken modulo 998244353. Note that you should minimize the answer but not its remainder.

input

5
1 8 7 2 4
9 7 2 9 3

output

646

题目大意：
给定两个数列 a , b ，现在要求不能动数列 a ，对数列 b 任意排列，求用上述的 f 方法求得的值的最小值。

这其实是一个贪心加一点技巧

首先，f 方法就是从 l 到 r 求和，但是题目要求的是 ∑1≤l≤r≤nf(l,r) ，即对所有的 f 区间求和。
这个其实有规律可循，

每一项出现的次数满足 count = i*(n-i+1)
由于 a 数列的顺序不能变化，所以我们对 a 数列进行一些操作，因为最后要用 a[i]*b[i]*出现的次数，所以可以先把a[ i ]处理为a[i]*出现的次数，这样的话就完全相当于两个数列不重复的各取一项相乘求和，要求和最小，直接排序利用贪心思想求解即可。乘的时候可能会有乘爆的危险，所以注意取模或者是快速乘优化。

#include <bits/stdc++.h>
using namespace std;

int n;
const int maxn = 2 * 1e5 + 10;
const int mod = 998244353;
typedef long long ll;
ll a[maxn];
ll b[maxn];
ll sum[maxn];

int main()
{
	ios::sync_with_stdio(false);
	while (cin >> n) {
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		for (int i = 1; i <= n; i++) {
			a[i] = a[i] * i*(n + 1 - i);
		}
		sort(a + 1, a + 1 + n);
		sort(b + 1, b + 1 + n, greater<int>());
		ll res = 0;
		for (int i = 1; i <= n; i++) {
			res += ((a[i] % mod) * (b[i] % mod)) % mod;
			res %= mod;
		}
		cout << res;
	}
	return 0;
}