# Bài toán
Cho mảng \( A \) gồm \( n \) phần tử ban đầu bằng 0. Có \( q \) truy vấn, mỗi truy vấn là một đoạn \((l, r)\). Với mỗi truy vấn, ta phải cập nhật:
$$
A_i = A_i + (i - l + 1), \quad \text{với } l \leq i \leq r
$$
Yêu cầu: Sau khi thực hiện tất cả \( q \) truy vấn, in ra mảng \( A \).
---
# Phân tích bài toán
Với truy vấn \((l, r)\), các phần tử từ \( l \) đến \( r \) được cộng thêm một dãy số tăng dần bắt đầu từ 1 ở vị trí \( l \), tăng dần 1 đơn vị tại mỗi vị trí tiếp theo.
Với số lượng truy vấn \( q \) và độ dài mảng \( n \) lớn (có thể đến \(10^5\)), cập nhật từng phần tử theo từng truy vấn theo cách trực tiếp là không khả thi (độ phức tạp \(O(nq)\)).
Cần tìm cách tối ưu để cập nhật nhanh và hiệu quả.
---
# Mô hình toán học
Ta có:
$$
A_i = \sum_{\substack{(l,r):\ l \le i \le r}} (i - l + 1) = \sum_{\substack{(l,r):\ l \le i \le r}} (i + 1 - l)
$$
Tuy vậy, mình sẽ mô tả một cách dễ hiểu như sau:
Như đã học, trước tiên bạn cần cập nhật mảng hiệu lên 1 đơn vị như bình thường.
Đến đây, mảng của mình vẫn chưa như output bài toán.
Tiếp theo, các bạn dễ dàng nhận thấy rằng tổng cộng dồn của mảng hiệu vừa cập nhật là một dãy tịnh tiến.
Ví dụ: với \( l = 2, r = 4, n = 5 \)
Ta có mảng hiệu lần 1: \(0 \; 1 \; 1 \; 1 \; 0\) (sau khi đã cộng dồn mảng hiệu lần 1)
Tiếp tục thực hiện cộng dồn mảng hiệu lần 2, ta được mảng sau:
\(0 \; 1 \; 2 \; 3 \; 3\)
Nhìn kỹ mảng, ta thấy rằng mảng đã được cộng theo cấp số cộng 1, tuy nhiên phần tử thứ 5 trong mảng là 3 (là phần thừa).
**Mục tiêu:** Cần loại bỏ phần thừa sau đó. Ta có thể làm cách nào?
- Cách đơn giản nhất là tạo một mảng hiệu khác lưu:
\(0 \; 0 \; 0 \; 0 \; -3\) chạy từ \(r + 1\).
Nhờ vậy ta có thể cộng 2 mảng để triệt tiêu phần tử thừa, như vậy đến đây bài toán đã được giải quyết.
Sau đây là code tham khảo của mình:
```cpp
// dona10khoa_nhd - Nguyen ho dang khoa - 25TIN CHUYÊN LƯƠNG THẾ VINH - ĐỒNG NAI
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b,x) for (ll i = (a); i < (b); i += (x))
const int N = 1e5 + 5;
ll d[N], g[N];
int main() {
fastio;
ll n, q;
cin >> n >> q;
while (q--) {
ll l, r;
cin >> l >> r;
d[l]++; // Bắt đầu tăng từ l
d[r + 1]--; // Kết thúc tăng tại r
g[r + 1] -= (r - l + 1); // Trừ phần dư sau đoạn [l..r]
}
// Cộng dồn lần 1
FOR(i, 1, n + 1, 1) {
d[i] += d[i - 1];
g[i] += g[i - 1];
}
// Cộng dồn lần 2 để tạo dãy tăng đều
FOR(i, 1, n + 1, 1) {
d[i] += d[i - 1];
cout << d[i] + g[i] << " ";
}
cout << "\n";
}
```
dona10khoa_nhd
Created at
1 likes