Bài toán này chắc là có nhiều lời giải khác nhau, và đây là lời giải mà mình tìm được.
Trước tiên, mình kí hiệu: $f(x,y,z,t)$ là tổng cần tính, và $g(x,y)=f(x,y,x,y)$.
Giả sử trong mọi truy vấn, $x=z$ và $y=t$ (nói cách khác, ta chỉ cần tính $g(x,y)$. Bài toán
này đơn giản hơn nhiều, và có thể giải bằng thuật toán Mo. Cụ thể, giả sử ta biết $g(l,r)$,
để tính $g(l,r+1)$, để ý rằng $a_{r+1}$ đóng góp vào kết quả một lượng bằng
$\sum_{i=l}^{r} |a_i-a_{r+1}|$. Tổng này có thể tách ra thành các $a_i$ mà $a_i\le a_{r+1}$
và ngược lại, và ta dễ dàng quản lý bằng một cây Fenwick, với độ phức tạp chuyển là $O(\log n)$.
Để chuyển trạng thái sang $g(l,r-1)$, ta cũng làm tương tự: ta chỉ cần trừ đi đóng góp của $a_r$
khỏi kết quả.
Quay về bài toán ban đầu, ta sẽ thử tách $f(x,y,z,t)$ thành phép tính với các $g(l,r)$ nào đó.
Không mất tính tổng quát, giả sử $y\le t$. Ta có thể xét ba trường hợp như sau.
**Trường hợp 1:** $y<z$ (hai đoạn $[x,y]$ và $[z,t]$ không giao). Xét giá trị $g(x,t)$: trong đây,
nó sẽ chứa tổng $f(x,y,z,t)$, nhưng sẽ tính dư tổng các $|a_i-a_j|$ với $(i,j)$ là một trong ba điều kiện:
1. $x\le i\le t$ và $y+1\le j\le z-1$;
2. $x\le i,j\le y$;
3. $z\le i,j\le t$.
Để khắc phục, ta trừ đi $g(x,z-1)$ và $g(y+1,t)$. Nhưng, lại để ý rằng ta trừ hai lần các
cặp $(i,j)$ mà $y+1\le i,j\le z-1$, nên ta cộng lại một lần $g(y+1,z-1)$ vào. Tóm gọn lại,
trong trường hợp này, $f(x,y,z,t)=g(x,t)-g(x,z-1)-g(y+1,t)+g(y+1,z-1)$.
**Trường hợp 2:** $z\le x$ (đoạn $[z,t]$ bao trọn đoạn $[x,y]$). Xét tổng $g(z,y)+g(x,t)$:
chắc chắn nó sẽ chứa $f(x,y,z,t)$, nhưng lại tính cả hai đoạn không cần thiết là $[z,x-1]$
và $[y+1,t]$, nên rốt cuộc ta có $f(x,y,z,t)=g(z,y)+g(x,t)-g(z,x-1)-g(y+1,t)$.
**Trường hợp 3:** $x<z\le y$ (hai đoạn giao một phần). Trường hợp này tương đối giống trường hợp 1,
và $f(x,y,z,t)=g(x,t)-g(x,z-1)-g(y+1,t)+g(z,y)$.
Nếu bạn đọc không hiểu trường hợp nào thì mình cũng khuyến khích tự nháp ra và ~cực khổ~ kiểm tra
rằng mình tính bù trừ không sai.
Khi này, ta đã có thể cài đặt Mo như đoạn trên để giải bài toán cuối cùng, tuy nhiên ta còn phải
chọn kích thước của block - $B$. Nhớ lại trong thuật toán Mo kinh điển, con trỏ phải di chuyển
$O(\frac{n}{B} \cdot n)$ lần, còn con trỏ trái di chuyển $O(Q\cdot B)$ lần, với $Q$ là số
đoạn (trong trường hợp tệ nhất, $Q=4\cdot q$, do có thể có một vài đoạn rỗng mà ta không cần
tính đáp án). Để độ phức tạp tổng là nhỏ nhất, ta chọn $B$ sao cho
$\frac{n}{B} \cdot n = Q\cdot B$, suy ra $B$ xấp xỉ $160$, nhưng ta có thể chọn hẳn $B=200$.
Độ phức tạp thời gian của thuật toán là $O(n\cdot\sqrt{q}\cdot\log{n})$.
tuongll
Created at
1 likes