Permutation Graphs
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
1 #include<stdio.h> 2 #include<string.h> 3 4 int temp[100005],a[100005],b[100005],c[100005],b1[100005]; 5 long long num; 6 7 void merg_sort(int a[],int l,int r) 8 { 9 int i,j,len=r-l,p1,p2; 10 if(len<=1) 11 return; 12 int mid=l+len/2; 13 merg_sort(a,l,mid); 14 merg_sort(a,mid,r); 15 p1=l,p2=mid; 16 for(i=l;i<r;i++) 17 { 18 if(p1==mid) 19 { 20 temp[i]=a[p2]; 21 p2++; 22 } 23 else if(p2==r) 24 { 25 temp[i]=a[p1]; 26 p1++; 27 } 28 else 29 { 30 if(a[p1]<=a[p2]) 31 { 32 temp[i]=a[p1]; 33 p1++; 34 } 35 else 36 { 37 temp[i]=a[p2]; 38 p2++; 39 num=num+mid-p1; 40 } 41 } 42 } 43 for(i=l;i<r;i++) 44 a[i]=temp[i]; 45 return; 46 } 47 48 int main() 49 { 50 int T; 51 int n,i,j,k; 52 scanf("%d",&T); 53 while(T--) 54 { 55 num=0; 56 scanf("%d",&n); 57 for(i=1;i<=n;i++) 58 scanf("%d",&b[i]); 59 for(i=1;i<=n;i++) 60 b1[b[i]]=i; 61 62 for(i=1;i<=n;i++) 63 scanf("%d",&c[i]); 64 for(i=1;i<=n;i++) 65 a[i]=b1[c[i]]; 66 67 /*for(i=1;i<=n;i++) 68 printf("%d ",a[i]);*/ 69 merg_sort(a,1,n+1); 70 printf("%lld ",num); 71 } 72 return 0; 73 }