**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.
lenhanbo
Created at
2 likes