HDU1394-Minimum Inversion Number

题目大意：

多组样例，给定\(n\)个数，在依次将第一个数放置最后一个数后面的过程中，每次放置构成一种排列，求所有排列中的最小逆序数。

\(n \leq 5000\)。

思路:

先处理出不进行放置操作时的第一个排列的逆序数，即题目给的排列的逆序数，随后滑动窗口，依次进行先删去头部带来的贡献，再加上尾部带来的贡献的操作。

用权值线段树进行维护，需要单点修改，区间查询。

Code:

#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mid (l+r)/2
using namespace std;
const int maxn=2e5+10;
//权值线段树 单点修改 区间查询 
int t,x,y,n,m;
char s[10];
int q[maxn];
struct node{
	int tr[maxn],lazy[maxn];
	void pushup(int rt){
		tr[rt]=tr[rt<<1]+tr[rt<<1|1];
	}
	void pushdown(int l,int r,int rt){
		
	}
	void build(int l,int r,int rt){
		if(l==r){
			tr[rt]=0;
			return ;
		}
		build(lson);
		build(rson);
		pushup(rt);
	}
	void update(int L,int R,int l,int r,int rt,int val){
		if(L<=l&&r<=R){
			tr[rt]+=val;//表示这个数出现次数 
			return ;
		}
		if(L<=mid){
			update(L,R,l,mid,rt<<1,val);
		}
		if(R>mid){
			update(L,R,mid+1,r,rt<<1|1,val);
		}
		pushup(rt);
	}
	int query(int L,int R,int l,int r,int rt){
		if(L<=l&&r<=R){
			return tr[rt];
		}
		int sum=0;
		if(L<=mid){
			sum=(sum+query(L,R,lson));
		}
		if(R>mid){
			sum=(sum+query(L,R,rson));
		}
		return sum;
	}
}sgt;
int main(){
	while(scanf("%d",&n)!=EOF){
		sgt.build(0,n,1);
		for(int i=1;i<=n;++i){
			scanf("%d",&q[i]);
		}
		for(int i=n+1;i<=2*n;++i){
			q[i]=q[i-n];
		} 
		int ans=0;
		int minn=0x3f3f3f3f;
		
		sgt.update(q[1],q[1],0,n,1,1);//第一个滑动窗口 
		for(int i=2;i<=n;++i){
			ans=ans+sgt.query(q[i]+1,n,0,n,1);
			sgt.update(q[i],q[i],0,n,1,1);
		}
		minn=min(ans,minn);
		
		for(int i=n+1;i<=2*n;++i){//滑动窗口 
			sgt.update(q[i-n],q[i-n],0,n,1,-1); 
			if(q[i-n]-1>=0)ans=ans-sgt.query(0,q[i-n]-1,0,n,1);//删去头部 失去的贡献 
			ans=ans+sgt.query(q[i]+1,n,0,n,1);//增加尾部 得到的贡献 
			
			sgt.update(q[i],q[i],0,n,1,1);
			minn=min(ans,minn);
		}
		printf("%d\n",minn);
	}
	return 0;
}

HDU1394-Minimum Inversion Number

原文：https://www.cnblogs.com/quuns/p/14544071.html