题目链接

题目大意

给你一个序列。定义一个序列的重量=\Sigma子串中相同元素配对的个数。(难以理解的话请参考原题样例)
现在给你一个序列,求它的重量。

解题思路

首先可以抽象此题的解法:

对于任意一对相同元素(i,j)而言,包含这一组元素对的子串有i*(n-j+1)种。(即区间之前和区间之后的乘积)

队友给我讲的时候的举例:
图片.png

所以我们可以得到一个O(n^2)的做法,枚举两个点ij即可。

为了优化到题目可以接受的复杂度,我们利用前缀和进行如下操作。

对于每一个点,记录与它的值相同的上一个点的下标。设前缀和数组s[i],每一步的s[i]=s[a[i]相同值的上一个点]+i

这样我们只需要遍历j,每一个j和此前所有的i的配对,只需要(n-j+1)*s[a[j]的相同值的上一个点]时间复杂度降至O(n)

代码实现

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

const int N = 2e6+7;
int T;
int n,k;
struct node{
    int last,next;//前驱后继
    int val;//该点的值
    int id;//该点的下标
}a[N];
int last[N];
int s[N];
map<int,int> m;//储存每一个数值的上一个点的下标

signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        m.clear();
        for(int i=1;i<=n;i++){
            cin>>a[i].val;
            a[i].id=i;
            a[i].last=m[a[i].val]; //i点的前驱=a[i]相同值的上一个的下标
            a[a[i].last].next=i;//a[i]相同值的上一个的后继=i点下标
            m[a[i].val]=i;//更新“上一个的下标”
            s[i]=a[i].id+s[a[i].last];//做前缀和
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(a[i].last!=0){
                ans+=s[a[i].last]*(n-i+1);//计算答案
                //cout<<i<<" "<<s[i]<<" "<<n-i+1<<endl;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
分类: 补题

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注