gmoj中山纪念中学oj思维好题

· · 个人记录

题目链接

Simple input:

4

1 1 4 5

Simple out:

51

分割线

首先要想消除相同元素带来的影响就要先排序（我这里没排序一直20最后舔着脸问的中山纪念的人要程序...)，我们可

以发现，a[i]给最后答案带来的贡献一定是a[i]\timesi\times(n-i+1),因为从i以后的所有前缀和都需要加上a[i],一轮加(n-i+1)次，

一共 i轮，因为起点从1开始一直到i+1,i才对答案没有影响，剩下注释都在程序里

//Author:ChairmanJ 2022.11.12
#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read()
{
    LL flag=1;
    LL x=0;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        flag=-1;
        ch=getchar();
     } 
     while(isdigit(ch))
     {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
     }
     return x*flag;
}
LL n,s[1000000],ans;
struct node
{
    LL w,z;
}a[1000000];
const LL inf=1e9+7;
bool cmp(node a,node b)
{
    if(a.z!=b.z)
    return a.z<b.z;
    else
    return a.w<b.w;//按照下标排序
}
int main()
{
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].z=read();
        a[i].w=i;//记住第几个元素在第几个位置
        s[i]=(i*(n-i+1))%inf;//统计a[i]在最后答案中要被加几次
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].z==a[i-1].z)
        {
            s[a[i].w]-=a[i-1].w*(n-a[i].w+1)%inf;
/*这里的意思是在a[i-1].w轮里a[i].w的权值往后都不算，因为a[i-1].w已经被算在ans里了，那么因为重复的不算权值，

所以把从a[i-1].w轮以前的都减去影响，因为a[i-1].w往后a[i].w就又恢复了*/
            if(s[a[i].w]<0)
            {
                s[a[i].w]=s[a[i].w]+inf;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=(ans+s[a[i].w]*a[i].z%inf)%inf;
    }
    cout<<ans%inf;
    return 0;
}