902
HDU 1394 線段樹單點更新求逆序數
題意：給出含有0 ~n-1 N個數組成的序列，有N次操作，每次把第一個數放到數列的最後，問這幾次數列操作中最小的逆序數的值。
單點更新就可以，每一輸入一個數，先查詢有幾個比這個數大的，再將這個值插入線段樹中。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 5005
struct node
{
int l,r,val;
};
node tree[N<<2];
int num[N];
void build(int root,int l,int r)
{
tree[root].l=l;
tree[root].r=r;
tree[root].val=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
}
void update(int root,int pos,int val)
{
if(tree[root].l==tree[root].r)
{
tree[root].val=val;
return;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(pos<=mid)
update(root<<1,pos,val);
else
update(root<<1|1,pos,val);
tree[root].val=tree[root<<1].val+tree[root<<1|1].val;
}
int query(int root,int l,int r)
{
if(l<=tree[root].l&&r>=tree[root].r)
return tree[root].val;
int mid=(tree[root].l+tree[root].r)>>1,ret=0;
if(l<=mid)
ret+=query(root<<1,l,r);
if(r>mid)
ret+=query(root<<1|1,l,r);
return ret;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
build(1,1,n);
int sum=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&num[i]);
sum+=query(1,num[i]+1,n-1);
update(1,num[i],1);
}
int ans=1e8;
for(int i=1; i<=n; i++)
sum=sum-num[i]+(n-num[i]-1),ans=min(ans,sum);
printf("%d\n",ans);
}
return 0;
}
最後更新：2017-04-03 18:51:58