HDU 1394 Minimum Inversion Number（線段樹求逆序數）
題目地址：HDU 1394
這題可以用線段樹來求逆序數。
這題的維護信息為每個數是否已經出現。每次輸入後，都從該點的值到n-1進行查詢，每次發現出現了一個數，由於是從該數的後面開始找的，這個數肯定是比該數大的。那就是一對逆序數，然後逆序數+1.最後求完所有的逆序數之後，剩下的就可以遞推出來了。因為假如目前的第一個數是x，那當把他放到最後面的時候，少的逆序數是本來後面比他小的數的個數。多的逆序數就是放到後面後前面比他大的數的個數。因為所有數都是從0到n-1.所以比他小的數就是x，比他大的數就是n-1-x。這樣的話每次的逆序數都可以用O(1)的時間計算出來。然後找最小的時候就可以了。
代碼如下：
#include
#include
#include
#include
#include
using namespace std;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int MAXN=6e3;
int sum[MAXN<<2], a[MAXN];
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 mid=l+r>>1;
build(lson);
build(rson);
}
void update(int p, int l, int r, int rt)
{
if(l==r)
{
sum[rt]++;
return ;
}
int mid=l+r>>1;
if(p<=mid) update(p,lson);
else update(p,rson);
PushUp(rt);
}
int query(int ll, int rr, int l, int r, int rt)
{
if(ll<=l&&rr>=r)
{
return sum[rt];
}
int mid=l+r>>1;
int ans=0;
if(ll<=mid) ans+=query(ll,rr,lson);
if(rr>mid) ans+=query(ll,rr,rson);
return ans;
}
int main()
{
int n, i, ans, y;
while(scanf("%d",&n)!=EOF)
{
build(0,n-1,1);
ans=0;
for(i=0; i
