DDOSvoid's Blog

Luogu P1908 逆序对

发表于 分类于
本文字数： 984 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P1908

Solution

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype> 
#define maxn 500010
#define gc getchar
#define lowbit(i) ((i) & (-i))
#define ll long long 
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
} 

int n, a[maxn];

int b[maxn], cnt; 
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}

int Bit[maxn];
inline void add(int i, int v) { while (i <= cnt) Bit[i] += v, i += lowbit(i); }

inline int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
} 

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    init_hash(); ll ans = 0; 
    for (int i = n; i; --i) {
        add(a[i], 1);
        ans += get_sum(a[i] - 1); 
    } cout << ans << endl; 
    return 0;
}