codefoce E2. Array Optimization by Deque(逆序对，树状数组，贪心)

题目：Problem - E2 - Codeforces

大意：用双段队列按已知顺序去存一些数，要求存完之后逆序对数最小（ai>aj&&i

思路：每次可以在装入后就可以交换一次新产生的逆序对，可知新装入的数在队列中，最终要待在哪个位置其实是确定的

（装在队列前：就装在所有比自己小的数（n1个）之后）

（装在队列后：就装在所有比自己大的数（n2个）前面）

每次装入都比较一下n1和n2的大小即可（用树状数组维护）

#include
#include
#include
using namespace std;
const int maxn=1e6;
int tree[maxn+10],a[1001000],b[1010000],inf=0x3f3f3f3f;
struct pp
{
	int num,ii;
	friend bool operator <(const pp &x,const pp &y)
	{
		return x.num0)
	{
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}
int main()
{
	int n,m,j,i,w,z=0;
	long long sum=0;
	scanf("%d",&w);
	while(w--)
	{
		memset(tree,0,sizeof(tree));
		scanf("%d",&n);
		for(i=1; i<=n; i++)
		{
			scanf("%d",&a[i]);
			q[i].num=a[i];
			q[i].ii = i;
		}
        
		sort(q+1,q+1+n);
		q[0].num=-inf,z=0,sum=0;
		for(i=1; i<=n; i++)
		{
			if(q[i].num !=q[i-1].num)	z++;
			b[q[i].ii]=z;
		}

		for(i=1; i<=n; i++)
		{
			sum+=min(sum1(b[i]-1),sum1(n)-sum1(b[i]));
			update(b[i],1);
		}
		printf("%lldn",sum);
	}
	return 0;
}