Cập nhật cấp số cộng trên đoạn

Hướng tiếp cận

Bài toán yêu cầu cộng một cấp số cộng vào một đoạn của mảng nhiều lần, sau đó in mảng kết quả. Với mảng hiệu bậc một thông thường, ta chỉ xử lý được cập nhật hằng số trên đoạn ($A[i]$ += $v$). Để xử lý cập nhật tuyến tính theo $i$, ta dùng mảng hiệu bậc hai: lấy hiệu một lần nữa từ mảng hiệu bậc một. Khi đó một cấp số cộng trên đoạn trở thành chỉ $O(1)$ thao tác trên mảng hiệu bậc hai.

Nhận xét quan trọng

1. Mảng hiệu bậc một $B[i]=A[i]-A[i-1]$ (với $A[0]=0$). Cập nhật $A[i]$ += $a+(i-l)·d$ trên $i\in [l,r]$ sẽ làm:
   • $B[l]$ tăng thêm $a$ (vì $A[l]$ tăng thêm $a$ trong khi $A[l-1]$ không đổi).
   • Với $l+1\le i\le r$: $B[i]$ tăng thêm $d$ (vì hiệu của hai số hạng liên tiếp trong cấp số cộng là $d$).
   • $B[r+1]$ giảm $a+(r-l)·d$ (vì $A[r+1]$ không đổi, còn $A[r]$ tăng thêm $a+(r-l)·d$).
2. Trên $B$, cập nhật "cộng $d$ cho mọi $i\in [l+1,r]$" lại là một cập nhật hằng số trên đoạn — ta xử lý bằng mảng hiệu bậc hai $C[i]=B[i]-B[i-1]$.
3. Vậy mỗi thao tác chỉ tác động lên $O(1)$ vị trí của $C$.

Thuật toán

Khởi tạo mảng $C[1..n+2]=0$. Với mỗi thao tác $(l,r,a,d)$:

1. — báo cho $B[l]$ tăng thêm $a$.
2. — báo cho $B[l+1]$ tăng thêm $d$ thay vì $a$ (chênh lệch là $d-a$).
3. , tức là trừ đi $a+(r-l+1)·d$ — báo cho $B[r+1]$ giảm $a+(r-l)·d$ (so với $B[r]$ vốn tăng $d$, chênh lệch là $-(a+(r-l)·d)-d$).
4. — báo cho $B[r+2]$ trở về $0$ (so với $B[r+1]$).

Sau khi xử lý hết $q$ thao tác, lấy tổng tiền tố hai lần:

• $B[i]=B[i-1]+C[i]$ với $i=1,\dots ,n$.
• $A[i]=A[i-1]+B[i]$ với $i=1,\dots ,n$.

In ra $A[1],A[2],\dots ,A[n]$.

Vì sao bốn phép cộng là đúng? Khi lấy tổng tiền tố $B=\text{prefix}(C)$:

• $B[l]=a$ (chỉ $C[l]$ đóng góp).
• $B[l+1]=a+(d-a)=d$.
• $B[i]=d$ với $l+1\le i\le r$ (không có $C$ nào khác trong đoạn này).
• $B[r+1]=d-(a+(r-l+1)·d)=-(a+(r-l)·d)$.
• $B[r+2]=-(a+(r-l)·d)+(a+(r-l)·d)=0$.

Lấy tổng tiền tố thêm một lần ra $A$:

• $A[l]=a$, $A[l+1]=a+d$, ..., $A[r]=a+(r-l)·d$ — đúng cấp số cộng.
• $A[r+1]=a+(r-l)·d+B[r+1]=0$, $A[r+2]=0$, ...

Đúng như mong đợi: chỉ đoạn $[l,r]$ bị thay đổi và bị cộng đúng cấp số cộng.

Lưu ý tràn số: Giá trị $a+(r-l)·d$ có thể lớn cỡ ${10}^9+2·{10}^5·{10}^9\approx 2·{10}^{14}$, và sau $q$ cập nhật giá trị tích lũy có thể đến $~4·{10}^{19}$ — vượt khỏi long long. Tuy nhiên đề bài đã đảm bảo kết quả cuối nằm trong long long, nên với phép tính modulo $2^{64}$ (đặc trưng của số có dấu trong C/C++) các kết quả trung gian "tràn" sẽ tự khử lẫn nhau khi tổng tiền tố và cho ra kết quả đúng. Để an toàn, ta dùng kiểu long long (hoặc unsigned long long) cho mảng $C$.

Độ phức tạp

• Thời gian: $O(n+q)$.
• Bộ nhớ: $O(n)$.