hdu 1394 Minimum Inversion Number(ワンポイント更新)

題意:N個の数をあげて、そのすべての形式の逆順序対の最小値を統計することを要求します.そのすべての形式は,配列の先頭の最初の数を配列の最後尾に絶えず置くことを意味する.
分析:主に線分樹を利用して逆序数を求め、空の木を建て、それから1つの点を挿入するたびに、統計がこの数より大きいのは何個か、すべての数が挿入されるまで、逆序樹の統計を終了した.
答えを出すには主に0からnの配列であれば,最初の数を最後に置くと,この数列に対して逆シーケンス数はy[i]を減少させ,n−1−y[i]を増加させるという結論を用いた.(このように考えると、最初の数であり、すべての数がその後ろにあるので、現在位置posがそれより大きい数もその後ろにあるので、最初の数が後ろになるとposが成立しない逆序数が成立するので、n-y[i]-1が多くなるが、posで成立する逆序数であるy[i]個も少なくなる)

// Time 46ms; Memory 340K

#include<iostream>
#include<cstdio>
#define maxn 1<<14

using namespace std;

int size,n,y[5010];
struct line
{
	int l,r;
	int n;
}a[maxn];

void init()
{
	int i;
	for(n=1;n<size;n<<=1);
	for(i=n;i<2*n;i++) 
	{
		a[i].l=a[i].r=i-n+1;
		a[i].n=0;
	}
	for(i=n-1;i>0;i--)
	{
		a[i].l=a[2*i].l;
		a[i].r=a[2*i+1].r;
		a[i].n=0;
	}
}
void insert(int i,int x)
{
	if(x>=a[i].l && x<=a[i].r) a[i].n++;
	if(a[i].l==a[i].r) return;
	int mid=(a[i].l+a[i].r)/2;
	if(x>mid) insert(2*i+1,x);
	else insert(2*i,x);
}
int find(int x,int y,int i)
{
	if(x<=a[i].l && y>=a[i].r)
	{
		return a[i].n;
	}
	int mid=(a[i].l+a[i].r)/2;
	int sum1=0,sum2=0;
	if(y>mid) sum1=find(x,y,2*i+1);
	if(x<=mid) sum2=find(x,y,2*i);
	return sum1+sum2;
}
int main()
{
	int j,sum,min;
	while(scanf("%d",&size)!=EOF)
	{
		init();
		sum=0;
		for(j=0;j<size;j++)
		{
			scanf("%d",&y[j]);
			y[j]++;
			insert(1,y[j]);
			sum+=find(y[j]+1,size,1);
		}
		min=sum;
		for(j=0;j<size-1;j++) 
		{
			sum-=y[j]-1;
			sum+=size-y[j];
			if(min>sum) min=sum;
		}
		printf("%d
",min);
	}
	return 0;
}