D. Zigzags

D. Zigzags

题意：

给一个数组a1,a2,…an,

统计数组中有多少个四元组（i,j,k,l）满足

1 <= i < j < k < l <= n

并且ai=ak，aj=al

思路：

统计每一位数在每一位的前缀pre以及后缀suf

代码：

#include<bits/stdc++.h>
#define ll long long
#define maxn (ll)1e3+5
using namespace std;
map<int,int>mp;
ll a[3005],pre[3005][3005],suf[3005][3005];
int main(){
    int t;
    cin>>t;
    while(t--){
        mp.clear();
        memset(suf,0,sizeof(suf));
        memset(pre,0,sizeof(pre));
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(int j=1;j<=n;j++){
                pre[j][i]=mp[j];
            }
            mp[a[i]]++;
        }
        mp.clear();
        for(int i=n;i>0;i--){
            for(int j=1;j<=n;j++){
                suf[j][i]=mp[j];
            }
            mp[a[i]]++;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                ans+=suf[a[i]][j]*pre[a[j]][i];
            }
        }
        cout<<ans<<endl;
    }
}