?

題目傳送門

1 /* 2 題意：給了兩行的數(shù)字，相同的數(shù)字連線，問中間交點的個數(shù) 3 逆序數(shù)：第一行保存每個數(shù)字的位置，第二行保存該數(shù)字在第一行的位置，接下來就是對它求逆序數(shù) 4 用歸并排序或線段樹求。想到了就簡單了:) 5 */ 6 #include <cstdio> 7 #include <algorithm> 8 #include <cstring> 9 #include <cmath> 10 #include <vector> 11 using namespace std; 12 13 typedef long long ll; 14 const int MAXN = 1e5 + 10; 15 const int INF = 0x3f3f3f3f; 16 int p[MAXN], a[MAXN]; 17 int L[MAXN/2+10], R[MAXN/2+10]; 18 ll ans; 19 20 void Merge(int *a, int p, int q, int r) 21 { 22 int n1 = q - p + 1, n2 = r - q; 23 for (int i=1; i<=n1; ++i) L[i] = a[p+i-1]; 24 for (int i=1; i<=n2; ++i) R[i] = a[q+i]; 25 L[n1+1] = INF; R[n2+1] = INF; 26 27 int i = 1, j = 1; 28 for (int k=p; k<=r; ++k) 29 { 30 if (L[i] <= R[j]) a[k] = L[i++]; 31 else {a[k] = R[j++]; ans += n1 - i + 1;} 32 } 33 } 34 35 void MergeSort(int *a, int p, int r) 36 { 37 if (p < r) 38 { 39 int q = (p + r) / 2; 40 MergeSort (a, p, q); 41 MergeSort (a, q + 1, r); 42 Merge (a, p, q, r); 43 } 44 } 45 46 int main(void) //UVALive 6508 Permutation Graphs 47 { 48 // freopen ("I.in", "r", stdin); 49 50 int t; scanf ("%d", &t); 51 while (t--) 52 { 53 int n; scanf ("%d", &n); 54 for (int i=1; i<=n; ++i) 55 { 56 int x; scanf ("%d", &x); p[x] = i; 57 } 58 for (int i=1; i<=n; ++i) 59 { 60 int x; scanf ("%d", &x); a[i] = p[x]; 61 } 62 63 ans = 0; 64 MergeSort (a, 1, n); 65 printf ("%lld\n", ans); 66 } 67 68 return 0; 69 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/4597813.html

總結(jié)

以上是生活随笔為你收集整理的逆序数 UVALive 6508 Permutation Graphs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。