此题对于我来说甚是巧妙啊 ,线段树可以这么用,这次参考了胡浩神的线段树写法:
对于此题:
1. 求出原始序列的逆序数
2. 当把第i个数移动到序列末尾时,原来小于a[i]的逆序数数将不在是逆序数,大于a[i]的非逆序数将成为逆序数
显然在(0---n-1)序列中,比它小的数有a[i]个(0---a[i]-1);比它大的数有n-a[i]-1个(a[i]+1----n-1);
下面解决问题1:
首先建一个空树,所有的sum都为0;
然后每读入一个数,都在比此数大的区间内查找sum的和(因为插入的顺序就是当前数的下标!)
最后总的sum就是原始序列的逆序数;
code
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FU(i,a) for(int i(1); i <= (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FORD(i,a,b) for(int i(a);i >= (b); i--) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 5555; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int sum[maxn<<2]; void PushUP(int rt){ //更新 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt){ //建树 sum[rt]=0; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); } void update(int p,int l,int r,int rt){ //单点更新 if(l==r){ sum[rt]++; return ; } int m=(l+r)>>1; if(p<=m) update(p,lson); else update(p,rson); PushUP(rt); } int query(int ql,int qr,int l,int r,int rt){ if(ql<=l && qr>=r) return sum[rt]; int m=(l+r)>>1; int ret=0; if(ql<=m) ret+=query(ql,qr,lson); if(qr>m) ret+=query(ql,qr,rson); return ret; } int a[maxn]; int main() { int n; while(~SD(n)){ build(0,n-1,1); int fres=0; FOR(i,0,n-1){ SD(a[i]); fres+=query(a[i],n-1,0,n-1,1); update(a[i],0,n-1,1); } int ret=fres; FOR(i,0,n-1){ fres+=n-(a[i]<<1)-1; ret=min(ret,fres); } printf("%d\n",ret); } return 0; }