翻译
给定一个长度为 (n) 的序列 (a) (( nle 3000,a_i le n )) ，求有多少个四元组 ((i,j,k,l)) 满足：
- (1 le i < j < k < l le n)
- (a_i=a_k) 且 (a_j=a_l)
思路
看到 (n le 3000) ，所以可以确定复杂度最高是 ( ext{O}(n^2)) 的，故枚举时至多只能枚举两个变量。
那么枚举 (i,j,k,l) 中的哪两个量能得到的信息最多呢？
-
当枚举 (i,j) 时：
能够得到满足条件时 (a_k) 和 (a_l) 的值，即 (a_k=a_i)，(a_l=a_j) 。
但是这样枚举无法得到 (k,l) 的相对位置，不好满足条件 (k<l)，故不可行。
枚举 (k,l) 也是同理。
-
当枚举 (i,k) 时：
能够得到 (j,l) 的相对位置，即 (j) 在 (isim k) 之间， (l) 在 (k sim n) 之间。
但是这样无法得到 (a_j) 和 (a_l) 的值，不好满足条件 (a_j=a_l) ，故也不可行。
枚举 (j,l) 也是同理。
-
当枚举 (j,k) 时：
能够得到满足条件时 (a_i) 和 (a_l) 的值，即 (a_i=a_k)，(a_l=a_j) 。
同时也能够得到 (i,l) 的相对位置，即 (i) 在 (1sim j) 之间， (l) 在 (k sim n) 之间。
这显然是可行的。
那么我们可以枚举 (j,k)，这样只要统计一个前缀和，维护每个数在某个区间出现的个数，再根据乘法原理，就能 ( ext{O}(1)) 计算出当 (j,k) 确定时的方案数。
由于 (a_i le n) ，故预处理前缀和的复杂度也是 ( ext{O}(n^2)) 的。
总时间复杂度 ( ext{O}(n^2)) 。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
int ans=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
const int N=3005;
int t,n,sum[N][N],a[N],ans;
signed main()
{
t=read();
while(t--)
{
n=read();
for(int i=1;i<=n;++i)
{
a[i]=read();
for(int j=1;j<=n;++j)
sum[i][j]=sum[i-1][j];
sum[i][a[i]]++;
//统计每个数出现次数的前缀和
}
ans=0;
//枚举 j,k O(1) 计算答案
for(int j=2;j<=n;++j)
for(int k=j+1;k<=n-1;++k)
ans+=(sum[j-1][a[k]])*(sum[n][a[j]]-sum[k][a[j]]);
printf("%lld
",ans);
}
return 0;
}