By yusijia

Updated:

Contents
  1. 1. 分析：

分析：

　　根据题目给的测试数据其实就可以知道是用冒泡排序来排的，所以可以转化为
求逆序数对的问题，和树状数组hdu2299的那道题差不多，只是这里不需要离散化，
直接用线段树就ok了，hdu1394也差不多，都是求逆序数
输入第i个数后查找前面输入的数中有多少比他大的数，就是在线段树中查找[i+1,n]
单个点上出现了哪些数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

#define Lson(x) (x<<1)
#define Rson(x) (Lson(x)|1)
#define Mid(x,y) ((x+y)>>1)
const int MAXN = 1010;
int n;

struct Node{
    int left;
    int right;
    int sum;
};

Node node[4 * MAXN];

void push_up(int pos)
{
    node[pos].sum = node[Lson(pos)].sum + node[Rson(pos)].sum;
}

void build_tree(int left, int right, int pos)//建一棵空树
{
    node[pos].left = left;
    node[pos].right = right;
    node[pos].sum = 0;
    if(left == right)
        return ;
    int mid = Mid(node[pos].left, node[pos].right);
    build_tree(left, mid, Lson(pos));
    build_tree(mid + 1, right, Rson(pos));
    push_up(pos);
}

int query(int left, int right, int pos)
{
    if(node[pos].left == node[pos].right)
        return node[pos].sum;
    int mid = Mid(node[pos].left, node[pos].right);
    if(right <= mid)
        return query(left, right, Lson(pos));
    else if(left > mid)
        return query(left, right, Rson(pos));
    else
        return query(left, mid, Lson(pos)) + query(mid + 1,  right, Rson(pos));
}

void update(int index, int pos)
{
    if(node[pos].left == node[pos].right){
        node[pos].sum++;
        return ;
    }
    int mid = Mid(node[pos].left, node[pos].right);
    if(index <= mid)
        update(index, Lson(pos));
    else
        update(index, Rson(pos));
    push_up(pos);
}

int main()
{
    int x, ans;
    while(scanf("%d", &n) != EOF){
        build_tree(1, n, 1);
        ans = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &x);
            if(x != n)
                ans += query(x + 1, n, 1);
            update(x, 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}
Contents
  1. 1. 分析：