官方题解：https://media.hihocoder.com/contests/challenge34/tutorials-previewed.pdf
题目链接：http://hihocoder.com/problemset/problem/1781
题意问对于给定序列A，是否存在一个整数k, 使得A冒泡k轮后变成序列B.
这题一种做法是像官方题解一样写个计算区间最值的数据结构。
而我是另一种做法，通过的逆序数 来判断A怎样能变化到B。
例子
首先我举一个例子：
对于序列 A
8 7 5 1 9 2 6 4 3
其每个位置的逆序数是：
0 1 2 3 0 4 3 5 6 （*）
接着对A冒泡一轮，得到：
7 5 1 8 2 6 4 3 9
这时每个位置的逆序数是：
0 1 2 0 3 2 4 5 0 （**）
那么序列（*）和序列（**） 直接有啥联系呢？
（**）=（*）每个数减-1，并向左平移一格 ，且最多减到0.
证明
现在来证明，每冒泡一轮 所有位置的逆序数-1，并向左移一格。
引理1：对于每轮冒泡排序，若一个位置的前面存在比他大的数， 则他一定会他前面的某个比他大的数进行有且仅有一次交换
这个引理大家自已脑补一下，应该很容易理解是对的。
引理2：若一个位置的前面存在比他大的数，则个位置的逆序数大于0
这个废话，我就不解释了。
证：因为任意一个逆序大于1位置，都与比他大的数交换一次，交换后首先逆序数必然减一，其次，交换后为位置肯定前移1格。 故结论成立。
解题思路
有了这个规律，显然我可以直接O(n)求出任意一轮A的逆序数 与B比较。
再利用【逆序数和】每轮的都会递减的单调性。就可以用二分比较逆序数和的方式，在O(n logn)时间定位b.
或者做一个O(n)预处理，算出n-1轮中，每轮的逆序数和，这样可以把查询的时间复杂度降低至O(n)
当然因为还要对数据进行O(n logn)离散化和求逆序数的原因，所以无论你写哪种最终复杂度都是O(n logn)。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<stack>
#include<math.h>
using namespace std;
#define lowbit(x) (x&(-x))
int a[],b[];
int s1[],s2[];
int c[];
int N=;
int cot[];
int getsum(int x)
{
int sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
void add(int x)
{
while(x<=N)
{
c[x]++;
x+=lowbit(x);
}
}
vector<int>que;
int getid(int x)
{
return lower_bound(que.begin(),que.end(),x)-que.begin()+;
}
void cal(int n,int a[],int ans[])
{
int i;
memset(c,,sizeof(c));
for(i=; i<=n; i++)
{
ans[i]=(i-)-getsum(a[i]);
add(a[i]);
}
}
int main()
{
int i,j,t,n,x,y,k,op,q;
long long m;
// freopen("1.in","r",stdin);
//freopen("2.out","w",stdout);
scanf("%d",&t);
for(int cas=; cas<=t; cas++)
{
scanf("%d",&n);
memset(s1,,sizeof(s1));
memset(cot,,sizeof(cot));
que.clear();
for(i=; i<=n; i++)
{
scanf("%d",&a[i]);
que.push_back(a[i]);
}
for(i=; i<=n; i++)
{
scanf("%d",&b[i]);
que.push_back(b[i]);
}
sort(que.begin(),que.end());
m=unique(que.begin(),que.end())-que.begin();
que.resize(m);
int ans=-;
for(i=; i<=n; i++)
{
a[i]=getid(a[i]);
b[i]=getid(b[i]);
}
cal(n,a,s1);
cal(n,b,s2);
long long sum=;
k=;
for(i=; i<=n; i++)
{
cot[s1[i]]++;
k=max(s1[i],k);
sum+=s2[i];
printf("%d ",s1[i]);
}
m=;
for(i=k+; i>; i--)
{
m=m+cot[i];
sum-=m;
if(sum<=)
{
break;
}
}
if(sum==)
{
i--;
for(j=; j<=n; j++)
{
if(max(s1[j+i]-i,)!=s2[j])
{
break;
}
}
if(j>n)
{
sort(a+,a+n+);
sort(b+,b+n+);
for(j=; j<=n; j++)
{
if(a[j]!=b[j])
{
break;
}
}
if(j>n)
{
ans=i;
}
}
}
printf("Case #%d: %d\n",cas,ans);
}
return ; }
AC代码