Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意

给一个数列\(a\),定义\(f(l,r)\)为\(b_1, b_2, \dots, b_{r - l + 1}\),\(b_i = a_{l - 1 + i}\),将\(b\)排序,\(f(l,r)\)=\(\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}\)

计算\(\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)\)

分析

考虑每个数字对答案的贡献，首先每个\(a_i\)的区间贡献为\((n-i+1)\times i\times a_i\)

在\(a_i\)左边的比它小的数\(a_j\)的贡献为\((n-i+1)\times j\times a_i\)

在\(a_i\)右边的比它小的数\(a_j\)的贡献为\(i\times (n-j+1)\times a_i\)

将所有贡献加起来即为答案

按排序后的下标建树状数组，维护原下标前缀和,边更新边加答案

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define bug cout<<"--------------"<<endl

using namespace std;

typedef long long ll;

const double PI=acos(-1.0);

const double eps=1e-6;

const int inf=1e9;

const ll llf=1e18;

const int mod=1e9+7;

const int maxn=5e5+10;

int n;

ll a[maxn],c[maxn],tr[maxn];

void add(int x,ll k){

	while(x<=n){

		tr[x]=(tr[x]+k)%mod;

		x+=x&-x;

	}

}

ll dor(int x){

	ll ret=0;

	while(x){

		ret=(ret+tr[x])%mod;

		x-=x&-x;

	}

	return ret;

}

ll ans=0;

void solve(){

	memset(tr,0,sizeof(tr));

	for(int i=1;i<=n;i++){

		ll t=dor(a[i])*(n-i+1)%mod;

		ans+=c[a[i]]*t%mod;

		ans%=mod;

		add(a[i],i);

	}

}

int main(){

	ios::sync_with_stdio(false);

	//freopen("in","r",stdin);

	cin>>n;

	for(int i=1;i<=n;i++){

		cin>>a[i];

		ans+=a[i]*(n-i+1)%mod*i%mod;

		ans%=mod;

		c[i]=a[i];

	}

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

	for(int i=1;i<=n;i++){

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

	}

	solve();

	reverse(a+1,a+n+1);

	solve();

	cout<<ans<<endl;

	return 0;

}

巴特西

Codeforces 1167 F Scalar Queries 计算贡献+树状数组

题意

分析

Code

最新文章

热门文章