部分問題
\(a\) を size \(N\) の vector, \(i \in N\) とする. \(a_{[0,i)}\) において, \(a_{i}\) 未満の個数と \(a_{i}\) 以上の和が分かれば十分.
これらは segtree で実装可能.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll op(ll a, ll b) {return a+b; }
ll e() {return 0LL;}
int main() {
ll n,m;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
cout << (s/mint(i+1).pow(2)).val() << endl;
t.set(a[i], t.get(a[i])+1);
u.set(a[i], u.get(a[i])+a[i]);
}
return 0;
}
*1:ll)2e5+5),u((ll)2e5+5);
mint s;
rep(i,n){
s += a[i];
s += mint(2)*(a[i]*t.prod(0,a[i]) + u.prod(a[i],(ll)2e5+5