首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

在賽中只想出大概方向，真正實作卡了好久，最後還是沒解出來。後來覺得我的想法完善後應該是正解，一直繞迴圈、陣列這些很基本的東西才成功AC。
我的解法需要有不弱的實作能力，不然要在比賽時限內寫出來難度不小。

解題想法

接下來使用的pa、pb、pc、pd是題目內的敘述。
以下3個陣列為解題核心：
1.dp[i]，把i點設為pb然後遍歷至n-1，期間遍歷的元素ax只要小於a[i]，dp[i]就++，此時dp[i]代表遍歷到索引x時有多少元素符合pb>pd。(原先使用二維陣列dp[i][x]然後MLE，所以做了一次壓縮)
2.prefix[i][j]，i固定，遍歷j從0到i-2，prefix[i][j]代表的是，以a[j]為pb，pd從j+1遍歷到a[i]的dp[j]，並加上前綴和(prefix[y][x]=prefix[y][x-1]+dp[x])，我們可以用這個前綴和去做技巧性地省略大量遍歷。
3.prefix_dp[i]，是dp[]的前綴和，以i為例子dp[i]最後就是i+1到n-1中所有小於a[i]的a[]數量。
前置作業中，我們遍歷計算dp[]時，同時把prefix、prefix_dp陣列賦予數值，這部分需要很細節的規劃。
只要把前置作業做的足夠，我們只需要一個二層迴圈就能解出答案，而答案會需要用到prefix、prefix_dp兩個陣列。
假設有一個長度為6的陣列，把索引0做為pa、索引3做為pc。那麼我們會需要x從1到2的a[x]做為pb，pc之後的a[]將做為pd，所以我們可以把index從1到2為pb的prefix_dp算出來後去減掉已經覆蓋卻不該計算的總和(所有以1(pa+1)到1(pc-2)為pb且以pc為pd的prefix[i][j])
請先完全讀懂dp、prefix、prefix_dp這三個陣列的意思，前置作業的理解很重要，否則你會看不懂最後的二層迴圈在幹嘛。
有些數字的關係(加一、減二…)要自己細心理解一下，最主要就是pa、pb、pc、pd之間的關係。

AC code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,n;
int a[5005];
ll int dp[5005];
ll int prefix[5005][5005];
ll int prefix_dp[5005];
ll int sum=0;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n;
        sum=0;
        for(int x=0;x<n;x++)cin >> a[x];
        for(int x=0;x<n-1;x++){
            dp[x]=0;
            for(int y=x+2;y<n;y++){
                if(a[x]>a[y])dp[x]++;
                if(x==0)prefix[y][x]=dp[x];
                else prefix[y][x]=(prefix[y][x-1]+dp[x]);
            }
            if(x==0)prefix_dp[x]=dp[x];
            else prefix_dp[x]=(prefix_dp[x-1]+dp[x]);
        }
        for(int x=0;x<n-3;x++){
            for(int y=x+2;y<n-1;y++){
                if(a[x]<a[y]){
                    sum+=(prefix_dp[y-1]-prefix_dp[x]-(prefix[y][y-2]-prefix[y][x]));
                }
            }
        }
        cout << sum << endl;
    }


    return 0;
}

題目連結 : Codeforces Round 789 - C. Tokitsukaze and Strange Inequality