洛谷 P1908 逆序对

Posted on Edited on In 
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
#include <iostream>
using namespace std;
using LL = long long;
const int N = 500000;
int n, q[N], tmp[N];
LL merge_sort(int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    LL ans = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            tmp[k++] = q[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i <= r; ++i, ++j) q[i] = tmp[j];
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> q[i];
    cout << merge_sort(0, n - 1) << endl;
    return 0;
}
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
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 500001;
int n, a[N], b[N];
LL ans;
struct Node {
    int l, r, v;
} tr[N << 2];
void pushup(int u) {
    tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v;
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void update(int u, int pos) {
    if (tr[u].l == tr[u].r) ++tr[u].v;
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (pos <= mid) update(u << 1, pos);
        else update(u << 1 | 1, pos);
        pushup(u);
    }
}
int query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].v;
    int mid = tr[u].l + tr[u].r >> 1;
    int ret = 0;
    if (l <= mid) ret = query(u << 1, l, r);
    if (r > mid) ret += query(u << 1 | 1, l, r);
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
    build(1, 1, n);
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        int pos = lower_bound(b + 1, b + len + 1, a[i]) - b;
        if (pos != n) ans += query(1, pos + 1, n);
        update(1, pos);
    }
    cout << ans << endl;
    return 0;
}
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
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 500001;
int n, a[N], b[N], t[N];
LL ans;
int lowbit(int x) {
    return x & -x;
}
int add(int x) {
    while (x <= n) {
        ++t[x];
        x += lowbit(x);
    }
}
int sum(int x) {
    int ret = 0;
    while (x) {
        ret += t[x];
        x -= lowbit(x);
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = i;
    sort(b + 1, b + n + 1, [&](int x, int y) {
        return a[x] == a[y] ? x > y : a[x] > a[y];
    });
    for (int i = 1; i <= n; ++i) {
        add(b[i]);
        ans += sum(b[i] - 1);
    }
    cout << ans << endl;
    return 0;
}
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
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
using LL = long long;
const int N = 500000;
struct Node {
    int val, fix;
    int cnt, siz;
    Node *ls, *rs;
    Node(int v) {
        val = v, fix = rand();
        ls = rs = nullptr;
        siz = cnt = 1;
    }
};
int n, s;
LL ans;
Node *root;
int siz(Node *&k) {
    return k ? k->siz : 0;
}
void pushup(Node *&k) {
    k->siz = siz(k->ls) + siz(k->rs) + k->cnt;
}
void zag(Node *&k2) {
    Node *k1 = k2->rs;
    k2->rs = k1->ls;
    k1->ls = k2;
    pushup(k2), pushup(k1);
    k2 = k1;
}
void zig(Node *&k2) { 
    Node *k1 = k2->ls;
    k2->ls = k1->rs;
    k1->rs = k2;
    pushup(k2), pushup(k1);
    k2 = k1;
}
void insert(Node *&node, int x) {
    if (!node) node = new Node(x);
    else if (x < node->val) {
        insert(node->ls, x);
        if (node->ls->fix < node->fix) zig(node);
        else ++node->siz;
    } else if (x > node->val) {
        insert(node->rs, x);
        if (node->rs->fix < node->fix) zag(node);
        else ++node->siz;
    } else ++node->cnt, ++node->siz;
}
int query(int x) { 
    int ret = 0;
    Node *node = root;
    while (node && node->val ^ x)
        if (node->val < x) node = node->rs;
        else { 
            ret += siz(node->rs) + node->cnt;
            node = node->ls;
        }
    if (node && node->val == x) return ret + siz(node->rs);
    else return ret;
}
int main() {
    ios::sync_with_stdio(false);
    srand(time(nullptr));
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        ans += query(s);
        insert(root, s);
    }
    cout << ans << endl;
    return 0;
}