题目大意
给你一个序列。定义一个序列的重量=\Sigma子串中相同元素配对的个数。(难以理解的话请参考原题样例)
现在给你一个序列,求它的重量。
解题思路
首先可以抽象此题的解法:
对于任意一对相同元素(i,j)而言,包含这一组元素对的子串有i*(n-j+1)种。(即区间之前和区间之后的乘积)
队友给我讲的时候的举例:
所以我们可以得到一个O(n^2)的做法,枚举两个点i和j即可。
为了优化到题目可以接受的复杂度,我们利用前缀和进行如下操作。
对于每一个点,记录与它的值相同的上一个点的下标。设前缀和数组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 条评论