codeforces#1167F. Scalar Queries(树状数组+求贡献)

时间:2023-03-09 14:56:34
codeforces#1167F. Scalar Queries(树状数组+求贡献)

题目链接:

https://codeforces.com/contest/1167/problem/F

题意:

给出长度为$n$的数组,初始每个元素为$a_i$

定义:$f(l, r)$为,重排$l$到$r$的元素,变成长度为$(r-l+1)$的数组$b_i$,$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)$

数据范围:

$1 \le n \le 5 \cdot 10^5$

$1 \le a_i \le 10^9$

$a_i\neq a_j,for,i\neq j$

分析:

把问题转化为求$a_i$对答案贡献的系数$x_i$

即:$ ans=x[1]\times a[1]+x[2]\times a[2]+x[3]\times a[3]+...$

只有$l\leq i\leq r$的时候,$a_i$才对答案有影响

如果$(l,r)$有$y$个数小于等于$a_i$,那么$x_i = x_i+y$

用树状数组计算$a_i$前面的数和后面的数对$x_i$的影响

ac代码:

#include<bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
using namespace std;
const int maxn=5e5+10;
const ll mod=1e9+7;
int n,t[maxn],num[maxn];
map<int,int>ma;
ll zz[maxn],tree[maxn];
void add(int x,int y)
{
for(int i=x;i<=n;i+=(i&(-i)))tree[i]+=y;
}
ll quer(int x)
{
ll res=0;
for(int i=x;i;i-=(i&(-i)))res+=tree[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
t[i]=num[i];
}
sort(t+1,t+n+1);//离散化处理
for(int i=1;i<=n;i++)
ma[t[i]]=i;
for(int i=1;i<=n;i++)
{
zz[i]=quer(ma[num[i]])*(n-i+1)%mod;//前面的数对zz[i]的贡献
add(ma[num[i]],i);
}
for(int i=1;i<=n;i++)
tree[i]=0;
for(int i=n;i>=1;i--)
{
zz[i]=(zz[i]+quer(ma[num[i]])*i%mod)%mod;//后面的数对zz[i]的贡献
add(ma[num[i]],n-i+1);
zz[i]=(zz[i]+(ll)(n-i+1)*i%mod)%mod;//num[i]对zz[i]的贡献
}
ll ans=0;
for(int i=1;i<=n;i++)
ans=(ans+(ll)num[i]*zz[i]%mod)%mod;
printf("%lld\n",ans);
return 0;
}