题目大意

求循环移动大小为n的数组后得到n个数组中的最小逆序对数(数组中数小于n)
传送门

a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)

思路:

用$O(n logn)$复杂度求出原数组逆序数(利用类似桶排序的思想，从1到n，每加入一个数，就在sum[a[i]]处+1，用一个数每次加上sum[a[i]+1]~sum[n],遍历后此数就代表了原数组逆序对数(可以用线段树，zkw，BIT等维护))后,就可以用O(1)的复杂度分别递推出其他解(每循环移动1个，逆序对数增加n-a[i]，减少a[i]+1)

PS

由于me喜欢从1到n，而题中数据从0到n-1，me给a[i]都自增1，O(1)推式子时变成了增加n-a[i]，减少a[i]-1(由于自增的缘故，需少减2)

Code

普通线段树

Time: 78ms

//hdu 1394
#include<iostream>
#include<cstdio>
#include<cstring>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define min(a,b) ((a)<(b)?(a):(b))
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=2e5+10;
int sum[maxn<<2]={0},a[maxn]={0},n;
void update(int,int,int,int,int);
int query(int,int,int,int,int);
void PushUP(int);
int main()
{
	while(~scanf("%d",&n))
	{
		cls(sum,0);
		int s=0;
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",&i[a]);
			i[a]++;//因为数中有0，都加上1。 
			s+=query(a[i]+1,n,1,n,1);
			update(a[i],1,1,n,1);
		}
		int mi=s;
		for(int i=1;i<n;i++)
		{
			mi-=a[i]-1+a[i]-n;
			s=min(s,mi);
		}
		printf("%d\n",s);
	}
	return 0;
}
void update(int p,int val,int l,int r,int rt)
{
	if(l==r)
	{
		sum[rt]+=val;
		return;
	}
	int m=(l+r)>>1;
	if(p<=m) update(p,val,lson);
	else update(p,val,rson);
	PushUP(rt);
}
int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R) return sum[rt];
	int m=(l+r)>>1,ret=0;
	if(L<=m) ret+=query(L,R,lson);
	if(R>m) ret+=query(L,R,rson);
	return ret;
}
void PushUP(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

zkw线段树(非递归线段树)

Time: 62ms

//spaceskynet 2017-09-02 zkw hdu 1394
#include<iostream>
#include<cstdio>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b))
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=2e4+10;
int sum[maxn<<1],a[maxn],n,M=1;
void update(int,int);
int query(int,int);
int main()
{
	while(~scanf("%d",&n))
	{
		cls(sum,0);
		int s=0;
		for(M=1;M<=n+1;M<<=1);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			a[i]++;
			s+=query(a[i]+1,n);
			update(a[i],1);
		}
		int mi=s;
		for(int i=1;i<n;i++)
		{
			mi-=a[i]-1+a[i]-n;
			s=min(s,mi);
		}
		printf("%d\n",s);
	}
	return 0;
}
void update(int p,int val)
{
	sum[p+=M]+=val;
	while(p)
	{
		p>>=1;
		sum[p]=sum[p<<1]+sum[p<<1|1];
	}
}
int query(int l,int r)
{
	int ret=0;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
	{
		if(~l&1) ret+=sum[l^1];
		if(r&1) ret+=sum[r^1];
	}
	return ret;
}

BIT

Time: 31ms

//spaceskynet 2017-09-02 BIT
#include<iostream>
#include<cstdio>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b))
#define cls(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-(x))) 
using namespace std;
const int maxn=6e3+10;
int sum[maxn]={0},a[maxn]={0},n;
void update(int,int);
int query(int);
int getsum(int,int);
int main()
{
	while(~scanf("%d",&n))
	{
		cls(sum,0);
		int s=0;
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",&a[i]);
			a[i]++;//因为数中有0，都加上1。 
			s+=getsum(a[i]+1,n);
			update(a[i],1);
		}
		int mi=s;
		for(int i=1;i<n;i++)
		{
			mi-=a[i]-1+a[i]-n;
			s=min(s,mi);
		}
		printf("%d\n",s);
	}
	return 0;
}
void update(int p,int val)
{
	for(int i=p;i<=n;i+=lowbit(i))
	{
		sum[i]+=val;
	}
}
int query(int p)
{
	int ret=0;
	for(int i=p;i>0;i-=lowbit(i))
	{
		ret+=sum[i];
	}
	return ret;
}
int getsum(int l,int r)
{
	return query(r)-query(l-1);
}

总结

总的来说，$普通线段树>zkw线段树>BIT$。
所以说，常数较小的BIT是不错的选择(毕竟加上差分，线段树的题，BIT也可以完成大部分了)。

**%%BIT**