Scalar Queries CodeForces - 1167F (计数,树状数组)

You are given an array $a_1,a_2,…,a_n$. All $a_i$ are pairwise distinct.

Let's define function $f(l,r)$ as follows:

let's define array $b_1,b_2,…,b_{r-l+1}$, where $b_i=a_{l-1+i}$;
sort array $b$ in increasing order;
result of the function $f(l,r)$ is $\sum\limits_{i=1}^{r-l+1}b_i\cdot i$.

Calculate $\Bigg(\sum\limits_{1\le l\le r\le n}f(l,r)\Bigg )mod(10^9+7)$, i.e. total sum of $f$ for all subsegments of $a$ modulo $10^9+7$.

可以得到$a_x$的贡献为

$\sum\limits_{\substack{a_i<a_x\\ i<x}} i\cdot (n-x+1)+\sum\limits_{\substack{a_i<a_x\\ i>x}}x\cdot (n-i+1)+x\cdot (n-x+1)$

#include <iostream>

#include <cstdio>

#include <algorithm>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

using namespace std;

typedef long long ll;

const int N = 1e6+10, P = 1e9+7;

int n, a[N], b[N];

ll c[N], cnt[N];

void add(int x, int v) {

	for (; x<=n; x+=x&-x) c[x]+=v;

}

ll query(int x) {

	ll r = 0;

	for (; x; x^=x&-x) r+=c[x];

	return r%P;

}

int main() {

	scanf("%d", &n);

	REP(i,1,n) scanf("%d",a+i),b[i]=a[i];

	sort(b+1,b+1+n);

	REP(i,1,n) a[i]=lower_bound(b+1,b+1+n,a[i])-b;

	REP(i,1,n) {

		cnt[i] += query(a[i])*(n-i+1)%P;

		add(a[i], i);

	}

	REP(i,1,n) cnt[i] += (ll)i*(n-i+1)%P, c[i] = 0;

	PER(i,1,n) {

		cnt[i] += query(a[i])*i%P;

		add(a[i], (n-i+1));

	}

	ll ans = 0;

	REP(i,1,n) ans+=cnt[i]*b[a[i]]%P;

	printf("%lld\n", ans%P);

}

巴特西

Scalar Queries CodeForces - 1167F (计数,树状数组)

最新文章

热门文章