P6186 bubble sort (tree array + thinking)

1. The number of exchanges in each round of bubble sorting is equal to N - x, and X is the number of numbers that meet the following conditions: there is no larger number in front of this number We say that this number does not participate in the exchange in the current round of bubble sorting

2. The total number of rounds of bubble sort exchange is the total number of reverse order pairs

3. Each round of exchange will reduce the number on the left of each number by 1 until it is 0

4. For a number, if x numbers are larger than him, then the number will be exchanged in x + 1

Next, we can obtain the number of reverse pairs after the k-th round by subtracting the number of reverse pairs subtracted from the previous k-th round from the total number of reverse pairs. We can use the tree array to maintain the prefix sum of the difference. Specifically, the first position is the total number of reverse pairs, and the subsequent position i + 1 is the number of reduced reverse pairs stored in the i-th round (i.e. n - x_i)

Finally, we just need to consider the exchange:

Let's make the b array the number of numbers larger than it before each number

If a[x] < a[x + 1], exchange a[x] and a[x + 1], and exchange b[x] and b[x + 1], so that b[x + 1] increases by 1. Then we consider the impact of this exchange on the number of reverse pairs. This operation will increase the number of reverse pairs in rounds 1 ~ b[x + 1], so that the total number of reverse pairs increases by 1

If a[x] > a[x + 1], exchange a[x] and a[x + 1], and exchange b[x] and b[x + 1], so that b[x] is reduced by 1. Then we consider the impact of this exchange on the number of reverse pairs. This operation will reduce the number of reverse pairs in rounds 1 ~ b[x], so that the total number of reverse pairs is reduced by 1

The code implementation is as follows:

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <unordered_map>
#include <vector>
#include <stack>
#include <time.h>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define ll long long
#define ull unsigned long long
#define eps 1e-8
// #define MOD 1000000007
#define debug(a) cout << #a << "=" << a << endl;
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 2e5 + 10;
int n, m, a[N], b[N], c[N], d[N];
void modify(int x, int k) {
    for (; x <= n; x += x & -x)
        c[x] += k;
}
int ask(int x) {
    int ans = 0;
    for (; x; x -= x & -x)
        ans += c[x];
    return ans;
}
signed main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    IOS;
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = i - 1 - ask(a[i]);
        ++d[b[i]];
        res += b[i];
        modify(a[i], 1);
    }
    mem(c, 0);
    modify(1, res);
    int t = 0;
    for (int i = 1; i <= n; ++i) {
        t += d[i - 1];
        modify(i + 1, -(n - t));
    }
    for (int i = 1; i <= m; ++i) {
        int op, x;
        cin >> op >> x;
        x = min(x, n - 1);
        if (op == 1) {
            if (a[x] < a[x + 1]) {
                swap(a[x], a[x + 1]);
                swap(b[x], b[x + 1]);
                ++b[x + 1];
                modify(1, 1);
                modify(b[x + 1] + 1, -1);
            }else {
                swap(a[x], a[x + 1]);
                swap(b[x], b[x + 1]);
                modify(1, -1);
                modify(b[x] + 1, 1);
                --b[x];
            }
        }else
            cout << ask(x + 1) << "\n";
    }
}

The following is the proof of the previous 1 ~ 4 conclusions:

Let's start with an example:

5 2 3 1 4

For 3, one element (5) in front is larger than this element, so 2 531 4 - > 2 351 4 - > 2 331 54 - > 2 331 45, 3 is "passive exchange", because the number larger than 3 before 3 will be exchanged with 3, and 3 after exchange must not be exchanged with the number larger than him, so the current round of 3 cannot realize active exchange For this number, each round of bubbles will say that it is larger than him, and the number in front of him will be put behind (conclusions 3 and 4). The contribution of this number to reducing the reverse order is 1 All previous numbers in the array are smaller than this number. After a round of bubbling, the contribution to reducing the reverse order pair is 0 Therefore, the number of each round of bubbling in reverse order is n - x (conclusion 1)

Since each collar exchange will only reduce one reverse order pair, and no new reverse order pair will be added in the bubbling process, the total exchange times of bubbling sorting is the total number of reverse order pairs (conclusion 2)

Tags: Algorithm data structure

Posted by moboter on Tue, 17 May 2022 23:30:21 +0300