题解：AT_abc276_f [ABC276F] Double Chance
__Creeper__
·
·
题解
思路
根据题意，对于第 K 次询问，答案为：
\dfrac{\sum\limits_{i=1}^K\sum\limits_{j=1}^K \max(A_i, A_j)}{K^2}
当我们从 $K-1$ 个元素扩展到 $K$ 个元素，加入新元素 $A_i$ 时，新增的 $\max$ 和由三部分组成：
- 前面小于等于 $A_i$ 的数 $y$，取 $\max$ 显然为 $A_i$。
- 前面大于 $A_i$ 的数 $y$，取 $\max$ 显然为 $y$。
- 当前两次都取 $A_i$，取 $\max$ 为 $A_i$。
所有小于 $A_i$ 的数的总贡献为小于 $A_i$ 的个数乘 $A_i$ 再乘 $2$（$A_i$ 可以和小于 $A_i$ 的数顺序调换，所以乘 $2$）。
所有大于 $A_i$ 的数的总贡献为大于 $A_i$ 的数的总和乘 $2$（同理）。
最后再加上 $A_i$，这是两次都取到 $A_i$ 的贡献。
注意到 $1 \le A_i \le 2 \times 10^5$，值域区间求个数和区间和，可以用两个权值树状数组分别维护。
## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace Creeper{
const int N = 2e5 + 5, mod = 998244353;
int n, a[N], ans;
struct Tree{
int t[N];
int lowbit(int x) {return x & (-x);}
void modify(int x, int y) {while (x < N) {t[x] += y; x += lowbit(x);}}
int qry(int x) {int res = 0; while (x) {res += t[x]; x -= lowbit(x);} return res;}
}A, B;
int qp(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res *= a; res %= p;
a *= a; a %= p;
b >>= 1;
}
return res;
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ans += (2 * A.qry(a[i]) % mod + 1) * a[i] % mod + ((B.qry(200000) % mod - B.qry(a[i]) % mod) % mod + mod) % mod * 2 % mod;
ans %= mod;
cout << ans * qp(i * i % mod, mod - 2, mod) % mod << '\n';
A.modify(a[i], 1);
B.modify(a[i], a[i]);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--) Creeper::solve();
}
```