传送门：HDU1394
题意：给定1-n的一个排列，可以将前面任意多个数按顺序放到后面形成新的序列，问所有这些序列中逆序数最小值为多少。
思路：只要求出第一个序列的逆序数来，其他序列的逆序数就可以递推出来，因此重点在于第一个序列的逆序数怎么求，因为数据范围较小，可以考虑用树状数组或者线段树维护1-n每个点，出现过就更新为1，否则为0，则每个数产生的逆序数（即每个元素对总逆序数的贡献）就可以在输入的过程中进行求解。详见代码。
代码：
#include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<map> #define ll long long #define pi acos(-1) #define inf 0x3f3f3f3f #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; typedef pair<int,int>P; const int MAXN=50010; int num[MAXN<<2],a[MAXN]; void pushup(int rt) { num[rt]=num[rt<<1]+num[rt<<1|1]; } void build(int l,int r,int rt) { if(l==r) { num[rt]=0; return ; } int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int id,int l,int r,int rt) { if(l==r) { num[rt]++; return ; } int mid=(l+r)>>1; if(id<=mid)update(id,lson); else update(id,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return num[rt]; } int mid=(l+r)>>1; int ans=0; if(L<=mid)ans+=query(L,R,lson); if(R>mid)ans+=query(L,R,rson); return ans; } int main() { int n; while(~scanf("%d",&n)) { build(0,n-1,1); int sum=0; for(int i=0;i<n;i++) { scanf("%d",a+i); sum+=query(a[i],n-1,0,n-1,1);//求初始序列的逆序数 query（a[i]）求的是a[i]对总逆序数的贡献 update(a[i],0,n-1,1); } int ans=sum; for(int i=0;i<n;i++) { sum+=((n-a[i]-1)-a[i]);//递推求得其他序列的逆序数 ans=min(ans,sum); } printf("%d\n",ans); } return 0; }