今天給分享的是一道算法決賽的題目，這道題目的綜合要求比較高，希望大家可以好好理解，同時這道題用到的是樹狀樹形結構的有關知識。可以用這幾天學的相關內容結合起來。

問題描述

給定兩個長度為?N的排列?A?和?B。若一對二元組下標?(i,j)?滿足以下關系則被稱之為壓制二元組：

• 1≤i<j≤N。
• pAi??<pAj??，其中?px??表示值?x在數組?B?中的下標。

一對壓制二元組的價值被定義為?j?ij?i，請你計算出所有壓制二元組的價值之和。

排列的定義：長度為?N?的排列表示一個長度為?NN?的數組，其中?[1,N][1,N]?每個數都恰好出現一次。

輸入格式

第一行輸入一個整數?N(1≤N≤2×105)N(1≤N≤2×105)?表示排列的長度。

第二行輸入?N?個整數A1?,A2?,A3?,?,AN??表示排列?A。

第三行輸入?N?個整數B1?,B2?,B3?,?,BN??表示排列?B。

保證?A,B?是一個排列。

輸出格式

輸出一個整數表示答案。

輸入案例：

4
2 4 1 3
4 1 2 3

輸出案例：

7

說明

樣例中有效的壓制二元組有 1,4),(2,3),(2,4),(3,4)，總價值為?4?1+3?2+4?2+4?3=7。

注意：二元組指的是下標對。

代碼答案：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
int a[N],h[N]; // h[]存儲每個數在B數組中的下標位置
LL b[N],c[N]; // b[]數組存儲數量，c[]數組存儲下標之和int lowbit(int x)
{return x & -x;
}void update(int pos,int x,LL d[])
{for(int i = pos;i <= n;i+=lowbit(i))d[i] += x;
}LL query(int pos,LL d[])
{LL res = 0;for(int i = pos;i;i-=lowbit(i)) res += d[i];return res;
}int main()
{scanf("%d", &n);for(int i = 1;i<=n;i++) scanf("%d",&a[i]);for(int i = 1;i<=n;i++){int x;scanf("%d",&x);h[x] = i;}LL ans = 0;for(int i = 1;i<=n;i++){update(h[a[i]],1,b);update(h[a[i]],i,c);ans += i * query(h[a[i]] - 1,b) - query(h[a[i]] - 1,c);}printf("%lld\n",ans);return 0;
}

1.首先需要理解題目中所求的價值對應的是a中的坐標，即

對于當前元素i，所有符合條件的j（j<i且p[A[j]]<p[A[i]]）的總價值是：
sum(i-j) = i * 符合條件的j的數量 - sum(符合條件的j的具體值)

2.兩個樹狀數組b和c的作用：

1. b數組：記錄「在某個位置上有多少個歷史元素」。

   • 當我們處理元素j時，會在b數組中h[A[j]]的位置加 1（表示該位置新增了一個元素）。
   • query(pos-1, b)的結果是：所有「位置小于當前pos」的歷史元素的總數量（即滿足p[A[j]] < p[A[i]]的j的個數）。

2. c數組：記錄「在某個位置上所有歷史元素的下標之和」。

   • 當我們處理元素j時，會在c數組中h[A[j]]的位置加j（表示該位置新增元素的下標是j）。
   • query(pos-1, c)的結果是：所有「位置小于當前pos」的歷史元素的下標總和（即滿足p[A[j]] < p[A[i]]的j的總和）。

3.根據案例的具體實現流程：

步驟 1：處理i=1（A[1]=2）

• pos = h[A[1]] = h[2] = 3（A[1]=2在B中的位置是 3）。
• 更新b和c：在位置 3 分別加 1 和 1（i=1）。
  • b數組狀態：b[3] = 1（其他位置 0）。
  • c數組狀態：c[3] = 1（其他位置 0）。
• 計算貢獻：query(2, b) = 0（沒有位置小于 3 的歷史元素），所以ans += 1*0 - 0 = 0。
• 當前ans = 0。

步驟 2：處理i=2（A[2]=4）

• pos = h[A[2]] = h[4] = 1（A[2]=4在B中的位置是 1）。
• 更新b和c：在位置 1 分別加 1 和 2（i=2）。
  • b數組狀態：b[1]=1，b[3]=1。
  • c數組狀態：c[1]=2，c[3]=1。
• 計算貢獻：query(0, b) = 0（沒有位置小于 1 的歷史元素），所以ans += 2*0 - 0 = 0。
• 當前ans = 0。

步驟 3：處理i=3（A[3]=1）

• pos = h[A[3]] = h[1] = 2（A[3]=1在B中的位置是 2）。
• 更新b和c：在位置 2 分別加 1 和 3（i=3）。
  • b數組狀態：b[1]=1，b[2]=1，b[3]=1。
  • c數組狀態：c[1]=2，c[2]=3，c[3]=1。
• 計算貢獻：query(1, b) = 1（位置 1 有 1 個元素，即j=2），query(1, c) = 2（j=2的下標和）。
  • 貢獻為?3*1 - 2 = 1，ans += 1。
• 當前ans = 1。

步驟 4：處理i=4（A[4]=3）

• pos = h[A[4]] = h[3] = 4（A[4]=3在B中的位置是 4）。
• 更新b和c：在位置 4 分別加 1 和 4（i=4）。
• 計算貢獻：query(3, b) = 3（位置 1、2、3 共有 3 個元素，即j=1,2,3），query(3, c) = 2+3+1=6（這些j的下標和）。
  • 貢獻為?4*3 - 6 = 6，ans += 6。
• 當前ans = 1 + 6 = 7（與樣例輸出一致）。