# 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 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: