Register | Login

Solutions of Inversions query 2

Select solution language All Tiếng Việt English Other

Write solution here.

---

tuongll    Created at    9 likes

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; }`