P6477

标签：const int res 1000005 long c2 P6477

#include <bits/stdc++.h>
using namespace std;
typedef long long long long;
const int INF=0x3f3f3f3f;
const long long mod=1e9+7;
long long c1[1000005],c2[1000005];
long long sum(int x) {
    long long res=0;
    for (int i=x;i > 0;i -= i & -i) {
        res+=c1[i]*(x+1)-c2[i];
    }
    return res;
}
void add(int x,int d,int n) {
    for (int i=x;i<=n;i+=i & -i) {
        c1[i]+=d;
        c2[i]+=(long long)d*x;
    }
}
int a[1000005],b[1000005],d[1000005],last[1000005];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        b[i-1]=a[i];
    }
    sort(b,b+n);
    int m=unique(b,b+n)-b;
    for (int i=1;i<=n;i++) {
        a[i]=lower_bound(b,b+m,a[i])-b;
        last[i]=d[a[i]];
        d[a[i]]=i;
    }
    long long ans=0,now=0;
    for (int i=1;i<=n;i++) {
        now+=i-last[i]+2*(sum(i)-sum(last[i]));
        now%=mod;
        ans+=now;
        add(last[i]+1,1,n);
        add(i+1,-1,n);
    }
    printf("%lld\n",ans % mod);
    return 0;
}

标签：const,int,res,1000005,long,c2,P6477
From： https://www.cnblogs.com/zan-mei-tai-yang/p/18493520