codeforces 1067F (Educational Codeforces Round 65 (Rated for Div. 2) F. Scalar Queries ) 树状数组计算贡献

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;
}