Register | Login

Solutions of Inversions query 3

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

Write solution here.

---

lenhanbo    Created at    5 likes

**Ta sẽ chia bài toán ra từng subtask.** Để thuận tiện hơn, ta sẽ gọi B($i$) là chỉ số block của vị trí $i$ 1. Giả sử $Q$ $=$ 1 : + Ta có thể duyệt từ $l$ đến $r$ rồi đếm số lượng phần tử $>$$A_i$ bằng cấu trúc dữ liệu như Fenwick tree hoặc Segment tree. 2. Giả sử $N$$\leq$1000 : + Gọi $f$$(i,j)$ là số lượng phần tử $A_x > A_j$ trong đoạn [$i$$\dots$$j$]. + Gọi $dp$$(i,j)$ là số nghịch đảo trong đoạn [$i$$\dots$$j$]. + Ta có $dp$$(l,r)$ $=$ $\sum_{i=l}^r$ $f$$(l,i)$. + Ta có thể chuẩn bị 2 mảng trong $O$($n$$^2$) và truy vấn trong $O$($1$). 3. Từ $(1)$ và $(2)$, ta có thể chia căn như sau : + Đầu tiên ta sẽ chia mảng thành $\sqrt{n}$ block. + Với mỗi block ta sẽ sort lại. + Gọi $g(i,j)$ là số lượng phần tử $A_x$ $>$ $A_i$ ($B$($x$) $=$ $j$). + Ta có thể tính $g(i,j)$ bằng hàm [lower_bound](https://en.cppreference.com/w/cpp/algorithm/lower_bound) trong c++. + Từ đó, ta có thể tính 2 mảng ở như $(2)$ nhưng thay vì dùng chỉ số phần tử thì ta tính với **chỉ số block**. Độ phức tạp cho bước này là $O(n$ $\times$ $\sqrt{n}$ $\times$ $log(n))$. + Khi truy vấn, ta dễ dàng tính được số nghịch đảo trong đoạn block [$B(l)+1$$\dots$$B(r)-1$]. + Gọi $pref(i,j)$ $=$ $\sum_{k=1}^j$ $g(i,k)$.Ta có thể tính nhanh nghịch đảo của 2 phần dư với phần block ($P/S$: đối với phần dư bên trái thì phải xử lí ngược với phần dư bên phải). + Đối với nghịch đảo giữa 2 phần dư thì ta có thể duyệt qua từng phần tử rồi dùng cấu trúc dữ liệu như Fenwick/Segment tree. + Tổng độ phức tạp là $O($ $(n + q)$ $\times$ $\sqrt{n}$ $\times$ $log(\sqrt{n}))$. 4. Tới đây vẫn chưa kết thúc, với độ phức tạp của (3) thì ta có thể bị **TLE** với bộ test đủ mạnh. + Tới đây ta vẫn có thể tối ưu được nữa, phần còn lại xin mời bạn đọc thử sức.