Ta chia các truy vấn thành hai loại: truy vấn với bước "lớn" ($d>\sqrt{n}$) và với bước nhỏ
($d\leq\sqrt{n}$). Khi truy vấn có bước lớn, ta có thể cập nhật trâu mảng $A$, do số phần
tử ta cập nhật không vượt quá $O(n/d)=O(\sqrt{n})$.
Với các truy vấn bước nhỏ, ta xét bài toán thế sau: Cho mảng $A$ gồm $n$ phần tử, ban đầu
các phần tử đều là $0$, cùng với $q$ truy vấn $(l,r)$: tăng $A_l$ lên $1$, $A_{l+1}$
lên $2$,…, $A_r$ lên $r-l+1$. Cho biết mảng $A$ sau $q$ truy vấn (nói cách khác, bài toán
với $d=1$).
Để làm bài toán này, ta thấy rằng trong một truy vấn, $A_i$ tăng một lượng bằng
$i-(l-1)$. Trong đó, phần $-(l-1)$ tương ứng với tăng đoạn lên một hằng số, và có kỹ thuật
mảng cộng dồn khá phổ biến để xử lý điều này. Còn với phần tăng $i$, do mỗi $A_i$ chỉ có thể
tăng $i$ nên ta chỉ cần lưu lại $A_i$ đã được cộng vào một lượng $i$ bao nhiêu lần, chẳng hạn
trong một mảng $cnt$, trên đó ta cũng có thể thực hiện kỹ thuật mảng cộng dồn nói trên (tăng đoạn
$[l,r]$ của mảng $cnt$ lên $1$). Nếu chưa hiểu, bạn có thể tham khảo đoạn code để giải bài toán
này ở dưới:
```cpp
int l, r;
for (int _ = 0; _ < q; ++_){
cin >> l >> r;
co[l] -= (l - 1);
if (r < n) co[r + 1] += (l - 1);
cnt[l] += 1;
if (r < n) cnt[r + 1] -= 1;
}
for (int i = 1; i <= n; ++i){
co[i] += co[i - 1];
cnt[i] += cnt[i - 1];
A[i] = co[i] + i * cnt[i];
}
```
Ý tưởng giải với $d=1$ có thể tổng quát hóa thành giải với mọi $d\leq\sqrt{n}$. Để làm điều này,
ta chỉ cần tạo $\sqrt{n}$ mảng $co$ và $cnt$ để giải riêng với từng $d$ để cộng lại vào mảng
$A$ cuối cùng. Tuy nhiên, phải để ý cộng/trừ đúng giá trị.
Độ phức tạp thời gian của thuật toán là $O(\sqrt{n}\times(n+q))$. Code mẫu (sử dụng mảng
chỉ số $0$ để tiện chia block độ dài $d$):
```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 = 1e9 + 7;
const int inf32 = 2e9;
const ll inf64 = 7e18;
int n, q, S;
ll a[mxn], pref[2][320][mxn];
void solve(){
cin >> n >> q;
S = sqrt(n);
for (int _ = 0, l, r, d; _ < q; ++_){
cin >> l >> r >> d;
r -= ((r - l) % d);
--l, --r;
if (d > S){
for (int i = l; i <= r; i += d){
a[i] += 1ll * ((i - l) / d + 1);
}
} else {
// cập nhật co
int u = (l / d) + 1;
pref[0][d][l] -= (u - 1);
if (r + d < n) pref[0][d][r + d] += (u - 1);
// cập nhật cnt
pref[1][d][l] += 1;
if (r + d < n) pref[1][d][r + d] -= 1;
}
}
for (int d = 1; d <= S; ++d){
for (int i = 0; i < n; ++i){
if (i - d >= 0){
pref[0][d][i] += pref[0][d][i - d];
pref[1][d][i] += pref[1][d][i - d];
}
ll val = (i / d) + 1;
a[i] += pref[0][d][i] + val * pref[1][d][i];
}
}
for (int i = 0; i < n; ++i)
cout << a[i] << ' ';
cout << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
3 likes