1 /*给出n个原始顺序的数，再给出要排成目标状态顺序，每次从第一个数列中选择三个，把这三个数中最右边的数放在最左边，然后其他两个数右 2 移一个单位，为你从原始状态能不能排序成目标状态。 3 本人YY的结论，从特殊到一般，虽然一般的只是手证了数值比较小的：结论应该就是1到n的n个数的全排列，分成相等的奇排序和偶排序，且个数一样，同个集合中的排列可以互相转换 4 比如1 2 3 4的全排1 2 3 4 5 1 4 2 3 6 1 3 4 2 7 4 1 3 2 8 4 2 1 3 9 4 3 2 110 2 4 3 111 2 1 4 312 2 3 1 413 3 4 1 2(可由4 1 3 2变成，一样的)14 3 2 4 115 3 1 2 416 这个偶排序占了12个，其他十二个是奇排序17 所以这道题直接比较两个数列的奇偶性18 */19 #include
     
      20 #include
      
       21 #include
       
        22 using namespace std;23 const int maxn=100010;24 int a[maxn],b[maxn],c[maxn];25 int n;26 struct point27 {28     int num,index;29 }p[maxn];30 int cmp(const point a,const point b)31 {32     return a.num
        
         0)50     {51        ans+=c[x];52        x=x-lowbit(x);53     }54     return ans;55 }56 int main()57 {58     int i,j;59     while(scanf("%d",&n)!=EOF)60     {61         memset(c,0,sizeof(c));62         for(i=1;i<=n;i++)63         {64             scanf("%d",&p[i].num);65             p[i].index=i;66         }67         sort(p+1,p+n+1,cmp);68         for(i=1;i<=n;i++)69             b[p[i].index]=i;70             71         int ans1=0,ans2=0;72         for(i=1;i<=n;i++)73         {74             updata(b[i],1);75             ans1=ans1+(sum(n)-sum(b[i]));//sum(p[i])是前面比b[i]小的数的个数76         }77         memset(c,0,sizeof(c));78         memset(p,0,sizeof(p));79         memset(b,0,sizeof(b));80         for(i=1;i<=n;i++)81         {82             scanf("%d",&p[i].num);83             p[i].index=i;84         }85         sort(p+1,p+n+1,cmp);86         for(i=1;i<=n;i++)87             b[p[i].index]=i;88         89         for(i=1;i<=n;i++)90         {91             updata(b[i],1);92             ans2=ans2+(sum(n)-sum(b[i]));93         }94         printf("%d %d\n",ans1,ans2);95         if(ans1%2==ans2%2) printf("Possible\n");96         else printf("Impossible\n");97     }98     return 0;99 } PS：这道题置换群也可以破 有奇数个有偶数个元素的轮换就是不可以   有偶数个有偶数个元素的轮换就是可以