题意：
首先给你一个长度为n的序列v，你需要首先找出来逆序对（i<j && v[i]>v[j]）
然后把这个序列的最后一个元素放在第一个位置上，其他元素都向后移动一位。
一直这样操作，会得到n个序列，问你这n个序列中，哪个序列中的逆序对数最少，并输出
题解：
首先我们可以通过线段树得到最初哪个序列的逆序对数，其实也可以通过归并排序得到，因为我是练习线段树，所以用的线段树写的
线段树求逆序对数的话，我们可以求出来v[i]可以和v[j]形成的逆序对数，这个j的取值范围为1<=j<i，我们可以维护一个最小值，然后得到有多少j能和v[i]构成逆序对
这一点不懂可以看一下代码
对于其他序列，你会发现就只是把最后一个元素放在第一个位置上，其他元素都向后移动一位。
那么原来上一个序列的逆序对数会减少n-v[n]，因为对于v[n]元素，它是最后一个元素，那么肯定v[n]+1,v[n]+2...n都可以和v[n]构成逆序对
逆序对数会增加v[n]-1个，因为v[n]移动到第一个位置之后，那么1,2,3...v[n]-1都可以和v[n]构成一个逆序对数
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
#define ll long long
#define mem(a) memset(a,0,sizeof(a))
#define mem_(a) memset(a,-1,sizeof(a))
#define mem__(a) memset(a,INF,sizeof(a))
int lazy[maxn<<2],tree[maxn<<2],arr[maxn];
void push_up(int root)
{
tree[root]=min(tree[root<<1],tree[root<<1|1]);
}
void build(int root,int L,int R)
{
if(L==R)
{
tree[root]=arr[L];
return;
}
int mid=(L+R)>>1;
build(root<<1,L,mid);
build(root<<1|1,mid+1,R);
push_up(root);
}
void update(int root,int L,int R,int pos,int val)
{
if(L==R)
{
tree[root]=val;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)
update(root<<1,L,mid,pos,val);
else update(root<<1|1,mid+1,R,pos,val);
push_up(root);
}
int query(int root,int L,int R,int LL,int RR,int val)
{
if(LL<=L && R<=RR)
{
if(tree[root]>val)
{
return R-L+1;
}
if(L==R) return 0;
}
int mid=(L+R)>>1,ans=0;
if(LL<=mid) ans+=query(root<<1,L,mid,LL,RR,val);
if(RR>mid) ans+=query(root<<1|1,mid+1,R,LL,RR,val);
return ans;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int sum=0;
mem__(tree);
//update(1,1,n,1,2);
//printf("%d**\n",query(1,1,n,1,1,1));
for(int i=1;i<=n;++i)
{
//int x;
scanf("%d",&arr[i]);
if(i!=1)
{
sum+=query(1,1,n,1,i-1,arr[i]);
}
update(1,1,n,i,arr[i]);
arr[i]+=1;
}
int minn=sum;
//printf("%d***\n",sum);
for(int i=n;i>1;--i)
{
sum=sum+((arr[i]-1)-(n-arr[i]));
minn=min(sum,minn);
}
printf("%d\n",minn);
}
return 0;
}