Ta nhận thấy rằng, mỗi truy vấn có thể quy về thành hai phép cập nhật gán phần tử. Cụ thể,
đặt $A[x]=u$ và $A[y]=v$ (trước khi hoán đổi), ta chỉ cần xử lý hai phép gán $A[x]:=v$ và
$A[y]:=u$, và bài toán trở nên đơn giản hơn.
Gọi $cnt$ là số nghịch đảo trong mảng $A$, $cnt$ sau khi cập nhật $A[i]:=x$ thay đổi
như sau:
+ $cnt$ trừ đi số lượng $j$ sao cho $j<i$ và $A[j]>A[i]$;
+ $cnt$ tăng một lượng bằng số lượng $j$ sao cho $j<i$ và $A[j]>x$;
+ $cnt$ trừ đi số $j$ sao cho $j>i$ và $A[i]>A[j]$;
+ $cnt$ tăng một lượng bằng số $j$ sao cho $j>i$ và $x>A[j]$.
Để thực hiện điều này, ta chia mảng $A$ thành $B$ block, mỗi block sẽ có một cây
BIT quản lý tần số xuất hiện các giá trị trong block đó. Khi đó, để tính số lượng $j$
thỏa mãn từng điều kiện (với $j$ không nằm cùng block với $i$), ta chỉ cần duyệt qua các
block và thực hiện get trên các cây BIT tương ứng. Ngoài ra, để xét các $j$ nằm trong cùng
block với $i$, ta chỉ cần duyệt qua các phần tử của block đó để tính lại $cnt$.
Cuối cùng, ta cần chọn giá trị $B$ phù hợp. Để ý rằng độ phức tạp thời gian xử lý mỗi phép
cập nhật là $O(2\times B\times \log{n} + n/B)$. Để thời gian được tối ưu, ta chọn $B$ sao
cho hai hạng tử bằng nhau, và ta tính được ta nên chia $A$ thành xấp xỉ $55$ block, mỗi
block chứa xấp xỉ $1800$ phần tử.
Code mẫu:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define debug(x) cout << #x << " = " << x << '\n'
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
const ll mod = 998244353;
const int inf32 = 2e9;
const ll inf64 = 7e18;
struct BIT {
int n, sum;
vector<int> bit;
void init(int size){
n = size, sum = 0;
bit.resize(n + 1);
for (int i = 0; i <= n; ++i)
bit[i] = 0;
}
void update(int i, int val){
for (; i <= n; i += (i & -i))
bit[i] += val;
sum += val;
}
int get(int i){
int res = 0;
for (; i; i -= (i & -i))
res += bit[i];
return res;
}
int get(int l, int r){
if (l == 1) return get(r);
if (r == n) return sum - get(l - 1);
return 0;
}
} bit[501];
ll inv[501]; // inv[id] = số nghịch đảo trong block id
ll cnt = 0;
int n, q, a[mxn], M;
const int S = 2e3;
// số lượng số > val trong các block trước bl
inline int count_gr(int bl, int val){
int res = 0;
for (int block = 0; block < bl; ++block){
if (block * S + S - 1 > n - 1) break;
res += bit[block].get(val + 1, n);
}
return res;
}
// số lượng số < val trong các block sau bl
inline int count_ls(int bl, int val){
int res = 0;
for (int block = bl + 1; block < M; ++block){
if (block * S + S - 1 > n - 1) break;
res += bit[block].get(1, val - 1);
}
return res;
}
void point_update(int id, int val){
int block = id / S;
cnt -= inv[block];
cnt -= (count_gr(block, a[id]) + count_ls(block, a[id]));
cnt += (count_gr(block, val) + count_ls(block, val));
int l = block * S, r = min(n - 1, l + S - 1);
for (int i = l; i < id; ++i)
inv[block] = inv[block] - (a[i] > a[id]) + (a[i] > val);
for (int i = id + 1; i <= r; ++i)
inv[block] = inv[block] - (a[id] > a[i]) + (val > a[i]);
bit[block].update(a[id], -1);
bit[block].update(val, 1);
a[id] = val;
cnt += inv[block];
}
void solve(){
cin >> n >> q;
for (int i = 0; i < n; ++i)
a[i] = i + 1;
for (int block = 0; block < S; ++block){
bit[block].init(n);
int l = block * S, r = min(n - 1, l + S - 1);
if (l > n - 1) break;
++M; // số lượng block
for (int i = l; i <= r; ++i){
bit[block].update(a[i], 1);
}
}
int x, y, tmp_x, tmp_y;
while(q--){
cin >> x >> y;
--x, --y;
tmp_x = a[x], tmp_y = a[y];
point_update(x, tmp_y);
point_update(y, tmp_x);
cout << cnt << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
4 likes