#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int n,m,q; int num[1<<21],num1[1<<21]; long long a[55],b[55],c[55]; long long ans; long long temp,tempcnt; void merge_sort(int l,int r,int level) {     if(l==r) return;     int mid=(l+r)/2,i,j,k;     i=l;k=l;j=mid+1;     merge_sort(l,mid,n-1);     merge_sort(mid+1,r,n-1);     while(i<=mid && j<=r)     {         if(num[i]<=num[j])             num1[k++]=num[i++];         else         {             a[level]+=mid-i+1;             num1[k++]=num[j++];         }     }     while(i<=mid)         num1[k++]=num[i++];     while(j<=r)         num1[k++]=num[j++];     for(int o=l;o<=r;++o)         num[o]=num1[o];     temp=0;     tempcnt=0;     for(int o=l+1;o<=r;++o)     {         if(num[o]!=num[o-1])         {             if(tempcnt!=0)                 temp+=(tempcnt-1)*tempcnt/2;             tempcnt=0;         }         else         {             if(tempcnt==0)                 tempcnt=2;             else                 tempcnt++;         }     }     if(tempcnt!=0)         temp+=(tempcnt-1)*tempcnt/2;     c[level]+=temp; } int main() {     scanf("%d",&n);     temp=1;     b[0]=0;     for(int i=1;i<=n;i++)     {         temp*=2;         b[i]=temp*(temp-1)/2;         for(int j=0;j<i;j++)         {             b[j]*=2;             b[i]-=b[j];         }     }     for(int i=0;i<(1<<n);i++)         scanf("%d",&num[i]);     merge_sort(0,(1<<n)-1,n);     for(int i=n;i>=1;i--)         c[i]-=c[i-1];     scanf("%d",&m);     for(int i=0;i<m;i++)     {         scanf("%d",&q);         for(int j=0;j<=q;j++)         {             a[j]=b[j]-a[j];         }         ans=0;         for(int j=0;j<=n;j++)         {             ans+=a[j];         }         ans-=temp;         printf("%lld\n",ans);     }     return 0; } 第二题的一个思路，不知道对不对 思路：使用归并排序求逆序对，在计算过程中记录每一层的可能存在的最大逆序对数量b[]，实际的逆序对数量a[].相同值的元素吞掉的逆序对c[] 对于每2的q次方翻转的操作，相当于是翻转了0-q层，也就是说0-q层的a[]=b[]-a[]-c[] 然后最后对于0-n层求和即可 总复杂度为nlogn（归并排序）+mlogn（m次翻转，每次logn）