sjtu_OJ/1634.cpp at master · q4x3/sjtu_OJ · GitHub

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/**
 * 堆排+归并+快排计数
 * 快排计数方法很神奇
 **/
#include <iostream>

using namespace std;

long long int ans;
int dt[100233], pre[100233], nxt[100233];
int N, k;

void merge(int lo, int mi, int hi, int* a) {
    int* A = a + lo;
    int lb = mi - lo;
    int* B = new int[lb];
    int* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    int* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            ++ ans;
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

void mergeSort(int lo, int hi, int* a) {
    if(hi - lo < 2) return;
    int mi = (lo + hi) >> 1;
    mergeSort(lo, mi, a);
    mergeSort(mi, hi, a);
    merge(lo, mi, hi, a);
}

void up(int node) {
    if(node == 1) return;
    ++ ans;
    if(dt[node] < dt[node >> 1]) {
        swap(dt[node], dt[node >> 1]);
        up(node >> 1);
    }
}

void down(int node, int size) {
    if(node == size || (node << 1) > size) return;
    if((node << 1 | 1) > size) {
        ++ ans;
        if(dt[node << 1] < dt[node]) swap(dt[node << 1], dt[node]);
    } else {
        ans += 2;
        if(dt[node << 1] <= dt[node << 1 | 1]) {
            if(dt[node] > dt[node << 1]) {
                swap(dt[node], dt[node << 1]);
                down(node << 1, size);
            }
        } else {
            if(dt[node] > dt[node << 1 | 1]) {
                swap(dt[node], dt[node << 1 | 1]);
                down(node << 1 | 1, size);
            }
        }
    }
}

void build() {
    for(int i = 1;i <= N;++ i)
        up(i);
}

void quick() {
    for (int i = 1; i <= N; i++)
    {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[0] = 1;
    pre[N + 1] = N;
    for (int i = N; i >= 1; i--)
    {
        int k = dt[i];
        ans += (long long int)(nxt[k] - pre[k] - 2);
        nxt[pre[k]] = nxt[k];
        pre[nxt[k]] = pre[k];
    }
}

int main() {
    scanf("%d%d", &N, &k);
    for(int i = 1;i <= N;++ i)
        scanf("%d", &dt[i]);
    if(k == 1) {
        build();
        for(int i = N;i > 1;-- i) {
            swap(dt[i], dt[1]);
            down(1, i - 1);
        }
        printf("%lld\n", ans);
    }
    if(k == 2) {
        mergeSort(1, N + 1, dt);
        printf("%lld\n", ans);
    }
    if(k == 3) {
        quick();
        printf("%lld\n", ans);
    }
}