F. Scalar Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array a1,a2,…,ana1,a2,…,an. All aiai are pairwise distinct.
Let's define function f(l,r)f(l,r) as follows:
- let's define array b1,b2,…,br?l+1b1,b2,…,br?l+1, where bi=al?1+ibi=al?1+i;
- sort array bb in increasing order;
- result of the function f(l,r)f(l,r) is ∑i=1r?l+1bi?i∑i=1r?l+1bi?i.
Calculate (∑1≤l≤r≤nf(l,r))mod(109+7)(∑1≤l≤r≤nf(l,r))mod(109+7), i.e. total sum of ff for all subsegments of aa modulo 109+7109+7.
Input
The first line contains one integer nn (1≤n≤5?1051≤n≤5?105) — the length of array aa.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109, ai≠ajai≠aj for i≠ji≠j) — array aa.
Output
Print one integer — the total sum of ff for all subsegments of aa modulo 109+7109+7
Examples
input
Copy
4
5 2 4 7
output
Copy
167
input
Copy
3
123456789 214365879 987654321
output
Copy
582491518
Note
Description of the first example:
- f(1,1)=5?1=5f(1,1)=5?1=5;
- f(1,2)=2?1+5?2=12f(1,2)=2?1+5?2=12;
- f(1,3)=2?1+4?2+5?3=25f(1,3)=2?1+4?2+5?3=25;
- f(1,4)=2?1+4?2+5?3+7?4=53f(1,4)=2?1+4?2+5?3+7?4=53;
- f(2,2)=2?1=2f(2,2)=2?1=2;
- f(2,3)=2?1+4?2=10f(2,3)=2?1+4?2=10;
- f(2,4)=2?1+4?2+7?3=31f(2,4)=2?1+4?2+7?3=31;
- f(3,3)=4?1=4f(3,3)=4?1=4;
- f(3,4)=4?1+7?2=18f(3,4)=4?1+7?2=18;
- f(4,4)=7?1=7f(4,4)=7?1=7
题意：
定义f(l,r)：从l位置到r位置取出来，然后排序，i*val求和
求所有区间的和（并且ai不相同！！！）
思路：
首先肯定要往计数贡献这方面考虑，先乱想一下，每次对于i位置，那么有贡献的是他这个数当前包括了多少个区间以及前面比它小的数和后面比它小的数，因为这样才会让他的位置往后移动，举个例子，比如
5
1 5 2 4 7
首先我们单看1~i - 1位置给i的贡献，
1是没有的，因为前面没有比它小的
5前面有1，但是1做了几次贡献呢？可以发现其实是从1到5当前位置和后面的位置1都是做了贡献的，所以就是(n - i + 1) * 1
2也是一样，前面只有1对它的贡献就是
1 5 2
1 5 2 4
1 5 2 7
所以一样(n - i + 1) * 1
4,前面有1和2比它小，
1 5 2 4
1 5 2 4 7
5 2 4
5 2 4 7
2 4
2 4 7
4前面有1,5,2，1做了n - i + 1次，我们把5的贡献看成2做的，2做了n - i + 1 * 3
这样就可以得到一个计算贡献的式子
i的贡献 = {1到i - 1,之间所有比它小的数}的下标 * (n - i + 1)
计算i后面比它小的数的贡献也是一样，另外还要把他自己算进去就是i * (n - 1 + 1)，树状数组算贡献就可以了（注意离散化和取模）
代码：
ll n,k;
ll a[maxn];
struct node{ ll c[maxn];void add(int x,int val){ while(x <= n){ c[x] += val;x += lowbit(x); }return ;}ll query(int x){ ll res = 0;while(x){ res += c[x];x -= lowbit(x);} return res;}
}BT1,Bt2;
std::vector<int> v;
int getid(int x){ return lower_bound(all(v),x) - v.begin() + 1;
}
ll b[maxn];
ll num[maxn];
int main()
{ ios; while(cin >> n){ ll ans = 0;for(int i = 1;i <= n;i++) cin >> a[i],v.pb(a[i]),b[i] = a[i]; sort(all(v));for(int i = 1;i <= n;i++) a[i] = getid(a[i]); for(int i = 1;i <= n;i++){ add2(num[i], mul1(BT1.query(a[i]), (n - i + 1)) );BT1.add(a[i],i); wt(num[i]);add2(num[i],(n - i + 1) * i % mod); } for(int i = n;i >= 1;i--){add2(num[i], mul1(Bt2.query(a[i]),i) );Bt2.add(a[i],n - i + 1);add2(ans,num[i] * b[i] % mod); }wt(ans);}return 0;
}