codeforces-Ed94-D

codeforces-Ed94-D

八月 28, 2020

D. Zigzags

题意

给出一个数组a ,长度为n <3000

求出有多少对四元组$(i,j,k,l)$

使得$a_i=a_k$ 且$a_j=a_l$

题解

最暴力的方法分别枚举i,j,k,l 时间复杂度$On^4$

由于题目条件约束我们想到 将ai和ak作为一对，将aj和al作为一对

处理前缀以num作为ak有多少个位置i<k满足ai=num

处理后缀以num作为aj有多少个位置l>j满足al=num

然后再枚举数对$(j,k)$ 统计四元组 复杂度为$On^2$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3000+5;
const double Pi=acos(-1);
const ll Mod=1e9+7;
/*
*/
int data[Max];
int K[Max][Max],J[Max][Max],dp[Max];
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
 
        for(int i=1;i<=n;i++)cin>>data[i];
        for(int i=1;i<=n;i++){
            for(int num=1;num<=n;num++){
                K[num][i]=K[num][i-1]+(data[i]==num);
            }
        }
        for(int num=1;num<=n;num++)J[num][n+1]=0;
        for(int i=n;i>=1;i--){
            for(int num=1;num<=n;num++){
                J[num][i]=J[num][i+1]+(data[i]==num);
            }
        }
        ll cnt=0;
        for(int k=2;k<n;k++){
            for(int j=1;j<k;j++){
                ll L=K[data[k]][j-1];
                ll R=J[data[j]][k+1];
                cnt+=L*R;
            }
        }
        cout<<cnt<<endl;
    }
}