【NWERC 2015-G】Guessing Camels 树状数组+逆序对+计数

题目链接：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：⑧行啊每次名词都听过但是都不懂啊。我康康百度。树套树也可。