Codeforces Round #721 (Div. 2) C. Sequence Pair Weight

Link

很显然,有两种思维模式.
第一种,分别求每个区间的贡献然后加起来.
第二种,分别求每一对的贡献然后加起来.

思考一下,第二种方法是可做的.

假设题目给的串是 1x1xx1 ,第二个1的贡献是1 \(\ast\) 4(因为所有左边界<=第一个1并且有边界>=第二个1的区间都有这一对),
再看第三个1的贡献时即可发现规律,第三个1要考虑前两个1,所以贡献是(1+3) \(\ast\) 1.

所以从头到尾for一遍,每次计算当前位置的数的贡献(sum[a[i]] \(\ast\) (n-i+1)),并更新sum[a[i]]即可 (sum[a[i]]是a[i]这个数出现的位置加起来 )

code

#include <bits/stdc++.h>
using  namespace  std;

int n,t,a[100005];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    map<int,long long> sum;
    long long ans=0;
    for(int i=1;i<=n;i++){
        ans += (n-i+1)*sum[a[i]];
        sum[a[i]] += i;
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);

    cin>>t;
    while(t--)  solve();
}

Codeforces Round #721 (Div. 2) C. Sequence Pair Weight

原文：https://www.cnblogs.com/JOoooo/p/14793632.html