HDU 5147 Sequence II - 四元組計數優化版

問題描述

同 5436，n≤50000 的排列，求四元組 (i1,i2,i3,i4) 滿足 i1a[i4]。

優化思路：枚舉 i3 位置

固定 i3 = c。條件分解：

• 左側：選 i1
• 右側：選 d>c 且 a[d] < a[b]。但 b 未固定。觀察：對於固定 c，右側合法 d 數取決於 b 的值。若枚舉 b，則右側 d 數 = 在 [c+1, n] 中小於 a[b] 的個數。

結合：總四元組數 = Σ_{c=3}^{n-1} [ Σ_{b=1}^{c-1} leftLess(b, a[c]) * rightLess(b, c) ]？實際上需更巧妙預處理。

標準解法（參考代碼）

#include 
using namespace std;
typedef long long LL;
const int N = 50010;
int n, a[N], c[N];
LL bit1[N], bit2[N], ans;

void add(LL bit[], int x, int v) { for (; x <= n; x += x&-x) bit[x] += v; }
LL sum(LL bit[], int x) { LL r=0; for(;x;x-=x&-x) r+=bit[x]; return r; }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i=1;i<=n;i++) scanf("%d", &a[i]);
        memset(bit1, 0, sizeof(bit1));
        memset(bit2, 0, sizeof(bit2));
        // 正向：bit1 維護值頻率，bit2 維護左側對數
        for (int i=1;i<=n;i++) {
            LL less = sum(bit1, a[i]-1); // 左側小於 a[i] 的個數
            add(bit1, a[i], 1);
            add(bit2, a[i], less); // 以 a[i] 為右端點的合法 (i1,i2) 對數累加到 bit2
        }
        // 逆向：計算右側
        memset(bit1, 0, sizeof(bit1));
        ans = 0;
        for (int i=n;i>=1;i--) {
            LL rightLess = sum(bit1, a[i]-1); // 右側小於 a[i] 的個數
            add(bit1, a[i], 1);
            // 此處需結合 bit2 查詢？原博客邏輯較複雜
        }
        printf("%lld\n", ans);
    }
    return 0;
}

註：完整邏輯涉及兩個樹狀數組協同，一個維護值頻率，一個維護左側有序對計數，逆向掃描時查詢右側小於關係並乘以左側對數。具體推導超過篇幅，核心為 O(n log n) 離線處理。