[CF 1400D] Zigzags

[CF 1400D] Zigzags - 1900

문제 설명

디스크립션 자체가 요약된 버전이다.
n개의 수 중에서 $i<j<k<l$ 을 만족하도록 숫자 4개를 뽑아서 $a_i == a_k$ && $a_j == a_l$ 을 만족시키는 tuple이 총 몇 쌍인지 구하면 된다.

풀이 방법

변수가 4개이기 때문에 4개를 동시에 생각하는 것은 무리이고, 4개중 2개를 고정시키면 된다. 가운데에 위치한 j와 k를 고정시키고 이를 만족하는 i와 l을 찾으면 된다.

생각할 점

코드

#include <bits/stdc++.h>
using namespace std;
/************************Contest Template**************************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b)
    { a=_a; b=_b; }
    const bool operator<(const S &o) const{
        return a<o.a;}
};
string exm;
inline void exf(void){ cout<<exm<<"\n"; exit(0); }
template <typename T>
inline void showAll(vector<T> &v,string sep=""){
    for(T &here:v) cout<<here<<sep;}
template <typename T>
inline void showAll(T a[],int st,int end,string sep=""){
    for(int i=st ; i<=end ; i++) cout<<a[i]<<sep; }
template <typename T>
inline vector<int> int_seperation(T N,int d=10){
    vector<int> v; while(N){v.push_back(N%d); N/=d;}
    reverse(v.begin(),v.end()); return v; }
/************************Contest Template**************************/
const int SIZE= 3009;
int arr[SIZE];
int cntLeft[SIZE][SIZE],cntRight[SIZE][SIZE];

int main(){
    int t;  scanf("%d",&t);
    while(t--){
        int n;  scanf("%d",&n);
        for(int i=1 ; i<=n ; i++){
            scanf("%d",&arr[i]);
        }

        for(int i=1 ; i<=n ; i++){
            int x = arr[i];
            for(int j=1 ; j<=n ; j++){
                cntLeft[i][j] = cntLeft[i-1][j] + (j==x);
            }
        }

        for(int i=n ; i>=1 ; i--){
            int x = arr[i];
            for(int j=1 ; j<=n ; j++){
                cntRight[i][j] = cntRight[i+1][j] + (j==x);
            }
        }

        ll ans = 0;
        // i < j < k < l
        // i=k, j=l
        for(int j=1 ; j<=n ; j++){
            for(int k=j+1 ; k<=n ; k++){
                ans += cntLeft[j-1][arr[k]] * cntRight[k+1][arr[j]];
                //arr[i]==arr[k] 이면서 j 보다 작은 i의 개수
                //arr[l]==arr[j] 이면서 k 보다 큰 l 의 개수
            }
        }

        printf("%lld\n",ans);
    }
}
/*

*/