http://acm.hdu.edu.cn/showproblem.php?pid=1394
这道题属于利用线段树求解一个序列的逆序数的应用。由于题目要求有5000个数，普通方法求解逆序数必然导致超时( 时间为n*(n-1)/2 )。
那么，利用线段树又如何求解呢？
这里思维有些巧，假设有序列5 3 4 1 2。
我们首先在线段[5,5]的位置上插入一个1，表示[5,5]这一线段有一个数，这个数就是5。
接下来我们要插入3，在插入3之前，我们先查找一下[4,n]这一区间，看其中有多少个1，有多少个1，就表示4~n之内有多少个数在之前已经出现过了。这个值表示3的逆序数
同理，一直插完最后一个数，我们便可以得到整个序列的逆序数。
View Code
1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 using namespace std;
5
6 struct node
7 {
8 int l;
9 int r;
10 int val;
11 };
12
13 node tree[25000];
14 int n,num[5001];
15
16 void build(int i,int l,int r)
17 {
18 tree[i].l=l;
19 tree[i].r=r;
20 tree[i].val=0;
21 if(l==r)
22 return;
23 int mid=(l+r)/2;
24 build(2*i,l,mid);
25 build(2*i+1,mid+1,r);
26 }
27
28 void updata(int i,int l,int r,int w)
29 {
30 if(tree[i].l>r || tree[i].r<l)
31 return;
32 if(tree[i].l>=l && tree[i].r<=r)
33 {
34 tree[i].val+=w;
35 return;
36 }
37 updata(2*i,l,r,w);
38 updata(2*i+1,l,r,w);
39 tree[i].val=tree[2*i].val+tree[2*i+1].val;
40 }
41
42 int find(int i,int l,int r)
43 {
44 if(tree[i].l>r || tree[i].r<l)
45 return 0;
46 if(tree[i].l>=l && tree[i].r<=r)
47 {
48 return tree[i].val;
49 }
50 return find(2*i,l,r)+find(2*i+1,l,r);
51 }
52
53 int main()
54 {
55 int i;
56 freopen("in.txt","r",stdin);
57 while(scanf("%d",&n)!=EOF)
58 {
59 build(1,0,n-1);
60 int ans=0;
61 for(i=1;i<=n;i++)
62 {
63 scanf("%d",&num[i]);
64 ans+=find(1,num[i]+1,n-1);
65 updata(1,num[i],num[i],1);
66 }
67 int min=ans;
68 for(i=1;i<n;i++)
69 {
70 ans=ans-num[i]+(n-1-num[i]);
71 if(ans<min)
72 min=ans;
73 }
74 printf("%d\n",min);
75 }
76 return 0;
77 }