題目鏈接：https://vjudge.net/problem/Gym-101485G

Description

Jaap, Jan, and Thijs are on a trip to the desert after having attendedtheACMICPCWorldFinals2015inMorocco. The trip included a camel ride, and after returning from the ride, their guide invited them to a big camel race in the evening. Thecamelstheyrodewillalsoparticipateanditiscustomary to bet on the results of the race.

One of the most interesting bets involves guessing the complete order in which the camels will ?nish the race. This bet offers the biggest return on your money, since it is also the one that is the hardest to get right.

Jaap, Jan, and Thijs have already placed their bets, but the racewillnotstartuntilanhourfromnow, sotheyaregetting bored. They started wondering how many pairs of camels they have put in the same order. If camel c is before camel d onJaap’s,Jan’sandThijs’bet,itmeansthatallthreeofthem putcanddinthesameorder. Canyouhelpthemtocalculate the number of pairs of camels for which this happened?

Input

The input consists of: ? one line with an integer n (2 ≤ n ≤ 200000), the number of camels; ? one line with n integers a1,...,an (1 ≤ ai ≤ n for all i), Jaap’s bet. Here a1 is the camel in the ?rst position of Jaap’s bet, a2 is the camel in the second position, and so on; ? one line with Jan’s bet, in the same format as Jaap’s bet; ? one line with Thijs’ bet, in the same format as Jaap’s bet. The camels are numbered 1,...,n. Each camel appears exactly once in each bet.

Output

Output the number of pairs of camels that appear in the same order in all 3 bets.

燙腳中文題意

給你三組數，每組數有n個數。求三組數中有多少對數的前后順序在三組數中都相同。

思路

訓練的時候用了第一組數來枚舉，然后TLE8，當時也沒想到什么好的方法。

后來通過百度發現這是一個利用樹狀數組統計逆序對個數的問題。

還有一個非常巧妙的地方，是不符合要求的必然是1個(a,b)+2個(b,a)或1個(b,a)+2個(a,b)這樣的類型，這樣的話統計出來會出來2，所以最后統計完后對逆序對的個數除以2就好。

AC代碼

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int SIZE=200000+50;
 5 ll arr[3][SIZE];
 6 ll tree[SIZE];
 7 int n;
 8 int lowbit(int k){
 9     return k&-k;
10 }
11 void add(int x,int k){
12     while(x<=n){
13         tree[x]+=k;
14         x+=lowbit(x);
15     }
16 }
17 ll sum(int x){
18     ll ans=0;
19     while(x!=0){
20         ans+=tree[x];
21         x-=lowbit(x);
22     }
23     return ans;
24 }
25 int pos[SIZE];
26 ll CountInversions(int x,int y){
27     memset(tree,0,sizeof(tree));
28     for(int i=1;i<=n;i++){
29         pos[arr[x][i]]=i;
30     }
31     ll ans=0;
32     for(int i=n;i;i--){
33         ans+=sum(pos[arr[y][i]]);
34         add(pos[arr[y][i]],1);
35     }
36     return ans;
37 }
38 
39 
40 int main(){
41     scanf("%d",&n);
42     for(int i=0;i<3;i++){
43         for(int j=1;j<=n;j++){
44             scanf("%lld",&arr[i][j]);
45         }
46     }
47     ll invers=(CountInversions(0,1)+CountInversions(1,2)+CountInversions(2,0))/2ll;
48     ll tot=((ll)n*(ll)(n-1))/2ll;//這里一定要加ll!!不然會爆
49     printf("%lld
",tot-invers);
50 }

拓展&故事會

Hugin：這道CDQ分治啊沒有板子不會啊你看就沒有大二寫出這題大三都會了。

tudouuuuu：⑧行啊每次名詞都聽過但是都不懂啊。我康康百度。樹套樹也可。

總結

以上是生活随笔為你收集整理的【NWERC 2015-G】Guessing Camels 树状数组+逆序对+计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。