Bài 38: Chia căn (sqrt decomposition) và thuật toán Mo trong C++ và Python: truy vấn đoạn, đếm số giá trị phân biệt
Lời mở đầu
Ở bài 31 và bài 37 em đã có trong tay cây Fenwick, cây phân đoạn và lazy propagation: mỗi thao tác chỉ tốn $O(\log n)$. Nhưng cây phân đoạn có một điểm yếu: nó chỉ làm được khi đáp án của một đoạn ghép được từ đáp án của hai nửa. Hỏi “trong đoạn $[l, r]$ có bao nhiêu số $\ge x$” hay “có bao nhiêu giá trị khác nhau” thì hai nửa không ghép được đơn giản như thế, và cây phân đoạn bắt đầu trở nên rất cồng kềnh.
Bài này dạy hai kỹ thuật có chung một con số thần kỳ là $\sqrt{n}$. Chia căn (sqrt decomposition) cắt dãy thành khoảng $\sqrt{n}$ khối, mỗi khối giữ sẵn một chút thông tin, nên mỗi truy vấn chỉ phải đụng tới $O(\sqrt{n})$ thứ. Thuật toán Mo thì đọc hết truy vấn rồi sắp xếp lại thứ tự, sau đó trượt cửa sổ $[l, r]$ bằng đúng kỹ thuật hai con trỏ ở bài 17. Cả hai đều chậm hơn $O(\log n)$ một chút, nhưng bù lại code ngắn, dễ nghĩ và dễ sửa cho rất nhiều dạng bài. Để đọc bài này thoải mái, em nên nhớ cách ước lượng số phép tính ở bài 9 và mảng cộng dồn ở bài 13.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Ý tưởng chia căn: tổng đoạn và cập nhật điểm
Bắt đầu bằng bài toán quen thuộc nhất. Cho dãy $a_1, a_2, \ldots, a_n$ và $q$ thao tác ($n, q \le 2 \cdot 10^5$), mỗi thao tác là một trong hai loại:
1 i x: gán $a_i = x$;2 l r: in ra $a_l + a_{l+1} + \cdots + a_r$.
Duyệt trực tiếp thì mỗi câu hỏi tốn $O(n)$; dùng mảng cộng dồn thì mỗi lần gán lại tốn $O(n)$. Bài 31 đã giải bằng cây Fenwick, còn hôm nay ta giải bằng một ý tưởng “thô” hơn nhiều mà vẫn đủ nhanh.
Chia dãy thành các khối. Chọn một số $B$ (kích thước khối) rồi cắt dãy thành các đoạn liên tiếp dài $B$: khối 0 gồm các chỉ số $0..B-1$, khối 1 gồm $B..2B-1$,… (trong code ta đánh số từ 0, khối cuối có thể ngắn hơn). Phần tử có chỉ số $i$ nằm trong khối $i / B$ (chia lấy phần nguyên). Với mỗi khối $b$, ta lưu sẵn $s_b$ = tổng các phần tử của khối.
- Gán $a_i = x$: chỉ khối $i / B$ bị đổi tổng, và tổng đổi đúng một lượng $x - a_i$. Vậy
s[i / B] += x - a[i]; a[i] = x;là xong, $O(1)$. - Hỏi tổng $[l, r]$: đoạn $[l, r]$ gồm ba phần: một ít phần tử lẻ ở đầu trái (thuộc khối bị cắt dở), một dãy khối nằm trọn ở giữa, và một ít phần tử lẻ ở đầu phải. Phần tử lẻ thì cộng từng cái, còn khối nằm trọn thì cộng luôn $s_b$, một phép cộng thay cho $B$ phép.
Hình 1. Dãy 10 phần tử, $B = \lfloor\sqrt{10}\rfloor = 3$, được 4 khối (khối 0 tới khối 3, dưới mỗi khối là tổng $s_b$). Truy vấn tổng $[3, 10]$: phần tử 3 là phần lẻ bên trái (vàng), khối 1 và khối 2 nằm trọn (xanh), phần tử 10 là phần lẻ bên phải.
Vì sao lại là $\sqrt{n}$? Mỗi đầu lẻ có không quá $B - 1$ phần tử, số khối nằm trọn không quá $n / B$. Một câu hỏi tốn khoảng $2B + \frac{n}{B}$ phép cộng. Nếu $B$ nhỏ thì có quá nhiều khối, nếu $B$ lớn thì phần lẻ quá dài. Hai vế $B$ và $\frac{n}{B}$ cân bằng khi $B = \sqrt{n}$, lúc đó một câu hỏi tốn $O(\sqrt{n})$. Với $n = 2 \cdot 10^5$: $\sqrt{n} \approx 447$, mỗi câu hỏi chừng $1300$ phép cộng, $2 \cdot 10^5$ câu hỏi tổng cộng khoảng $2{,}7 \cdot 10^8$ phép đơn giản: C++ chạy trong khoảng một giây.
Em hãy bấm Tiếp để xem một phép gán rồi một câu hỏi tổng đi qua các khối thế nào. Thử đổi đoạn hỏi cho nằm gọn trong một khối, hoặc bắt đầu đúng ở đầu khối, để thấy phần lẻ biến mất:
Trong code, cả ba phần được viết bằng ba vòng while nối tiếp nhau, dùng chung con trỏ l chạy từ trái sang phải. Vòng đầu cộng lẻ cho tới khi l rơi đúng vào đầu một khối (l % B == 0); vòng giữa nhảy cả khối khi khối đó còn nằm trọn (l + B - 1 <= r); vòng cuối cộng nốt phần còn lại. Đề cho vị trí đếm từ 1 nên ta trừ 1 trước khi gọi hàm.
Xem code C++ / Python: chia căn: gán một phần tử, hỏi tổng đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q, B;
vector<long long> a, s; // s[b] = tổng các phần tử của khối b
void update(int i, long long x){ // gán a[i] = x
s[i / B] += x - a[i]; // tổng khối đổi đúng một lượng x - a[i]
a[i] = x;
}
long long query(int l, int r){ // tổng a[l..r] (chỉ số từ 0)
long long res = 0;
while(l <= r && l % B != 0) res += a[l++]; // đầu trái lẻ
while(l + B - 1 <= r){ res += s[l / B]; l += B; } // các khối nằm trọn
while(l <= r) res += a[l++]; // đầu phải lẻ
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
B = max(1, (int)sqrt(n));
a.assign(n, 0); s.assign(n / B + 1, 0);
for(int i = 0; i < n; i++){ cin >> a[i]; s[i / B] += a[i]; }
while(q--){
int t; long long x, y;
cin >> t >> x >> y;
if(t == 1) update(x - 1, y);
else cout << query(x - 1, y - 1) << "\n";
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
s = [0] * (n // B + 1) # s[b] = tổng khối b
for i in range(n):
s[i // B] += a[i]
out, p = [], 2 + n
for _ in range(q):
t, x, y = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
if t == 1: # gán a[x] = y
i = x - 1
s[i // B] += y - a[i]
a[i] = y
else: # tổng a[x..y]
l, r = x - 1, y - 1
bl, br = l // B, r // B
if bl == br:
out.append(sum(a[l:r + 1]))
else: # lẻ trái + các khối trọn + lẻ phải
out.append(sum(a[l:(bl + 1) * B]) + sum(s[bl + 1:br]) + sum(a[br * B:r + 1]))
print('\n'.join(map(str, out)))
main()Khung chạy tay dưới đây làm đúng ví dụ ở Hình 1. Em để ý ô s nào sáng xanh lá: đó là các khối được cộng nguyên, và chú ý sau phép gán ta hỏi lại đúng đoạn cũ, đáp án giảm đúng $5 - (-2) = 7$.
[l, r] (chỉ số từ 0) đều đi theo cùng một dáng:while(l <= r && l % B != 0){ /* xử lý lẻ phần tử l */ l++; }
while(l + B - 1 <= r){ /* xử lý nguyên khối l / B */ l += B; }
while(l <= r){ /* xử lý lẻ phần tử l */ l++; }(int)sqrt(n) có thể bằng 1, còn nếu em lỡ viết sqrt(n) / 2 thì $B = 0$ và phép chia i / B làm chương trình chết ngay: luôn viết B = max(1, …).2. Mảng tổng khối phải có ít nhất $\lceil n / B \rceil$ ô; khai báo
n / B + 1 ô là an toàn.3. Tổng có thể vượt
int (ví dụ $2 \cdot 10^5$ số cỡ $10^9$), nên s[] và biến kết quả dùng long long.while mà dùng sum(a[l:…]) và sum(s[…]): hàm sum trên lát cắt chạy bằng C bên trong nên nhanh hơn vòng lặp Python nhiều lần. Đây là mẹo chung cho mọi bài chia căn bằng Python: đẩy càng nhiều việc vào hàm có sẵn (sum, min, max, bisect) càng tốt.Phần 2Cộng cả đoạn: nhãn khối
Nâng cấp bài toán: thao tác 1 l r x giờ là cộng $x$ vào mọi phần tử $a_l, \ldots, a_r$, còn 2 l r vẫn hỏi tổng. Nếu cộng từng phần tử thì một thao tác tốn $O(n)$. Ở bài 37 cây phân đoạn giải bằng nhãn lazy; chia căn có một phiên bản đơn giản hơn nhiều: nhãn khối.
Mỗi khối $b$ giữ thêm một số lz[b]: “mọi phần tử của khối này còn được cộng thêm lz[b] mà chưa ghi vào từng a[i]”. Như vậy giá trị thật của phần tử $i$ là a[i] + lz[i / B], còn s[b] luôn là tổng thật của khối (đã tính cả nhãn).
- Cộng đoạn: phần tử lẻ thì
a[i] += xvàs[i / B] += x; khối nằm trọn thì chỉlz[b] += xvàs[b] += x * B. Không đụng vào từng phần tử của khối. - Hỏi tổng: phần tử lẻ cộng
a[i] + lz[i / B]; khối nằm trọn cộngs[b].
Cả hai thao tác vẫn đúng khuôn ba vòng lặp, nên vẫn $O(\sqrt{n})$. Ví dụ với $a = (1, 2, \ldots, 8)$, $B = 2$, thao tác “cộng 10 vào đoạn $[2, 7]$”:
| Khối | Vị trí | a[i] lưu trong mảng | lz | s (tổng thật) | Đã làm gì |
|---|---|---|---|---|---|
| 0 | 1, 2 | 1, 12 | 0 | 13 | vị trí 2 là phần lẻ trái: cộng thẳng vào a |
| 1 | 3, 4 | 3, 4 | 10 | 27 | nằm trọn: chỉ dán nhãn, s += 10 · 2 |
| 2 | 5, 6 | 5, 6 | 10 | 31 | nằm trọn: chỉ dán nhãn, s += 10 · 2 |
| 3 | 7, 8 | 17, 8 | 0 | 25 | vị trí 7 là phần lẻ phải: cộng thẳng vào a |
Bảng 1. Sau khi cộng 10 vào đoạn $[2, 7]$. Mảng a ở khối 1 và 2 vẫn là 3, 4, 5, 6, nhưng giá trị thật là 13, 14, 15, 16 nhờ nhãn lz = 10. Hỏi tổng $[3, 4]$ chỉ cần đọc s = 27; hỏi tổng $[4, 5]$ thì cộng $(4 + 10) + (5 + 10) = 29$.
Xem code C++ / Python: chia căn: cộng đoạn, hỏi tổng đoạn bằng nhãn khối (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q, B;
vector<long long> a, s, lz; // lz[b]: lượng đã cộng cho CẢ khối b, chưa cộng vào từng a[i]
void add(int l, int r, long long x){
while(l <= r && l % B != 0){ a[l] += x; s[l / B] += x; l++; }
while(l + B - 1 <= r){ lz[l / B] += x; s[l / B] += x * B; l += B; } // dán nhãn cả khối
while(l <= r){ a[l] += x; s[l / B] += x; l++; }
}
long long query(int l, int r){
long long res = 0;
while(l <= r && l % B != 0){ res += a[l] + lz[l / B]; l++; } // giá trị thật = a[i] + nhãn khối
while(l + B - 1 <= r){ res += s[l / B]; l += B; }
while(l <= r){ res += a[l] + lz[l / B]; l++; }
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
B = max(1, (int)sqrt(n));
a.assign(n, 0); s.assign(n / B + 1, 0); lz.assign(n / B + 1, 0);
for(int i = 0; i < n; i++){ cin >> a[i]; s[i / B] += a[i]; }
while(q--){
int t, l, r;
cin >> t >> l >> r;
if(t == 1){ long long x; cin >> x; add(l - 1, r - 1, x); }
else cout << query(l - 1, r - 1) << "\n";
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
nb = n // B + 1
s, lz = [0] * nb, [0] * nb
for i in range(n):
s[i // B] += a[i]
out, p = [], 2 + n
for _ in range(q):
t, l, r = int(data[p]), int(data[p + 1]) - 1, int(data[p + 2]) - 1; p += 3
if t == 1:
x = int(data[p]); p += 1
bl, br = l // B, r // B
if bl == br:
for i in range(l, r + 1): a[i] += x
s[bl] += x * (r - l + 1)
else:
for i in range(l, (bl + 1) * B): a[i] += x
s[bl] += x * ((bl + 1) * B - l)
for b in range(bl + 1, br): # dán nhãn cả khối
lz[b] += x; s[b] += x * B
for i in range(br * B, r + 1): a[i] += x
s[br] += x * (r - br * B + 1)
else:
bl, br = l // B, r // B
if bl == br:
res = sum(a[l:r + 1]) + lz[bl] * (r - l + 1)
else:
res = sum(a[l:(bl + 1) * B]) + lz[bl] * ((bl + 1) * B - l)
res += sum(s[bl + 1:br])
res += sum(a[br * B:r + 1]) + lz[br] * (r - br * B + 1)
out.append(res)
print('\n'.join(map(str, out)))
main()a[i], giá trị thật vẫn là a[i] + lz. Nhưng nếu thao tác là gán cả đoạn (a[i] = x) thì khác: trước khi sửa lẻ một phần tử của khối đang có nhãn gán, em phải ghi nhãn xuống mọi phần tử của khối đó rồi xoá nhãn (tốn $O(B)$, vẫn ổn). Quên bước này là lỗi kinh điển của bài gán đoạn.Một biến thể còn dễ hơn: cộng đoạn, hỏi một điểm. Lúc đó chẳng cần s[], giá trị của điểm $i$ chính là a[i] + lz[i / B], mỗi câu hỏi $O(1)$. Em sẽ tự cài ở bài tập 2.
Phần 3Chọn kích thước khối, so sánh với cây phân đoạn
Ở phần 1 ta chọn $B = \sqrt{n}$ vì hai vế chi phí $B$ và $\frac{n}{B}$ cân bằng nhau. Nhưng không phải bài nào hai vế cũng “nặng” như nhau. Quy tắc chung: viết chi phí của một thao tác theo $B$, rồi chọn $B$ để hai vế lớn nhất bằng nhau. Xét bài toán sau, một bài mà cây phân đoạn bình thường không làm được:
Bài toán. Cho dãy $n$ số và $q$ thao tác: 1 i x gán $a_i = x$; 2 l r x đếm xem trong $a_l, \ldots, a_r$ có bao nhiêu số $\ge x$.
Cây phân đoạn bế tắc vì biết “nửa trái có 3 số $\ge 5$, nửa phải có 2 số $\ge 5$” chẳng giúp gì khi câu hỏi sau hỏi $x = 7$. Chia căn thì có cách rất tự nhiên: mỗi khối giữ thêm một bản sao đã sắp xếp tăng dần. Với khối nằm trọn, số phần tử $\ge x$ tìm được bằng tìm kiếm nhị phân (lower_bound) trong $O(\log B)$.
- Hỏi: phần lẻ so sánh từng số, $O(B)$; mỗi khối trọn một lần tìm kiếm nhị phân, tổng $O(\frac{n}{B} \log B)$.
- Gán: tìm vị trí giá trị cũ trong bản sao của khối, thay bằng giá trị mới rồi đẩy nó trượt về đúng chỗ (giống một lượt sắp xếp chèn), $O(B)$.
Chi phí câu hỏi là $B + \frac{n}{B}\log B$: cân bằng khi $B \approx \sqrt{n \log n}$. Thực tế với $n = 10^5$ em lấy $B$ trong khoảng 300–1000 đều chạy tốt; nếu thao tác gán nhiều hơn câu hỏi thì nghiêng về $B$ nhỏ, câu hỏi nhiều hơn thì nghiêng về $B$ lớn.
Xem code C++ / Python: chia căn: đếm số ≥ x trong đoạn, có gán phần tử (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q, B;
vector<int> a;
vector<vector<int>> blk; // blk[b]: các phần tử của khối b, luôn giữ tăng dần
int query(int l, int r, int x){ // đếm số a[i] >= x với l <= i <= r
int res = 0;
while(l <= r && l % B != 0) res += (a[l++] >= x);
while(l + B - 1 <= r){
vector<int> &v = blk[l / B];
res += v.end() - lower_bound(v.begin(), v.end(), x); // tìm kiếm nhị phân trong khối
l += B;
}
while(l <= r) res += (a[l++] >= x);
return res;
}
void update(int i, int x){ // gán a[i] = x, giữ khối vẫn tăng dần
vector<int> &v = blk[i / B];
int p = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); // chỗ của giá trị cũ
v[p] = x;
while(p > 0 && v[p - 1] > v[p]){ swap(v[p - 1], v[p]); p--; }
while(p + 1 < (int)v.size() && v[p + 1] < v[p]){ swap(v[p + 1], v[p]); p++; }
a[i] = x;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
B = max(1, (int)sqrt(n));
a.resize(n); blk.assign(n / B + 1, {});
for(int i = 0; i < n; i++){ cin >> a[i]; blk[i / B].push_back(a[i]); }
for(auto &v : blk) sort(v.begin(), v.end());
while(q--){
int t; cin >> t;
if(t == 1){ int i, x; cin >> i >> x; update(i - 1, x); }
else { int l, r, x; cin >> l >> r >> x; cout << query(l - 1, r - 1, x) << "\n"; }
}
return 0;
}import sys
from math import isqrt
from bisect import bisect_left, insort
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
blk = [sorted(a[i:i + B]) for i in range(0, n, B)] # mỗi khối đã sắp tăng
out, p = [], 2 + n
for _ in range(q):
if data[p] == b'1':
i, x = int(data[p + 1]) - 1, int(data[p + 2]); p += 3
v = blk[i // B]
v.pop(bisect_left(v, a[i])) # bỏ giá trị cũ
insort(v, x) # chèn giá trị mới
a[i] = x
else:
l, r, x = int(data[p + 1]) - 1, int(data[p + 2]) - 1, int(data[p + 3]); p += 4
bl, br = l // B, r // B
if bl == br:
res = sum(1 for i in range(l, r + 1) if a[i] >= x)
else:
res = sum(1 for i in range(l, (bl + 1) * B) if a[i] >= x)
for b in range(bl + 1, br):
v = blk[b]
res += len(v) - bisect_left(v, x)
res += sum(1 for i in range(br * B, r + 1) if a[i] >= x)
out.append(res)
print('\n'.join(map(str, out)))
main()Vậy khi nào nên chọn chia căn, khi nào chọn cây? Bảng dưới đây tóm tắt kinh nghiệm thi cử:
| Tiêu chí | Chia căn | Cây phân đoạn / Fenwick |
|---|---|---|
| Một thao tác | $O(\sqrt{n})$, đôi khi $O(\sqrt{n \log n})$ | $O(\log n)$ |
| $n = q = 2 \cdot 10^5$ | ≈ $10^8$ phép, C++ khoảng 0,3–1 giây | ≈ $7 \cdot 10^6$ phép, rất nhanh |
| Điều kiện | chỉ cần xử lý được “nguyên khối” và “từng phần tử” | đáp án đoạn phải ghép được từ hai nửa |
| Độ dài code, dễ sửa | ngắn, ba vòng lặp, rất dễ đổi bài | dài hơn, lazy dễ sai |
| Hợp với | đếm số $\ge x$, đảo đoạn, bước nhảy, thông tin “không ghép được” | tổng, min, max, gcd, cộng/gán đoạn |
Bảng 2. Chia căn và cây phân đoạn. Nếu bài toán ghép được hai nửa thì cây phân đoạn thường là lựa chọn an toàn hơn về thời gian; chia căn toả sáng khi thông tin của đoạn khó ghép hoặc khi cần viết nhanh, ít lỗi.
Phần 4Thuật toán Mo: sắp xếp truy vấn, dịch hai con trỏ
Bài toán. Cho dãy $n$ số ($|a_i| \le 10^9$) và $q$ câu hỏi, mỗi câu hỏi l r: đoạn $a_l, \ldots, a_r$ có bao nhiêu giá trị khác nhau? Không có thao tác sửa dãy. ($n, q \le 2 \cdot 10^5$.)
Nếu chỉ có một đoạn thì quá dễ: dùng mảng đếm cnt[v] và biến distinct. Hơn nữa, nếu ta đang có đáp án của đoạn $[l, r]$ thì sang các đoạn “hàng xóm” chỉ tốn $O(1)$:
- add(i) (đưa $a_i$ vào cửa sổ):
cnt[a[i]]++, nếu nó vừa từ 0 lên 1 thìdistinct++; - del(i) (bỏ $a_i$ ra khỏi cửa sổ):
cnt[a[i]]--, nếu nó vừa về 0 thìdistinct--.
Đây chính là cửa sổ trượt của bài 17. Nếu các câu hỏi có $l$ tăng dần và $r$ tăng dần thì hai con trỏ đi một mạch từ trái sang phải, tổng chỉ $O(n + q)$. Rắc rối là câu hỏi đến theo thứ tự lung tung: đoạn sau có thể ở tít đầu bên kia, mỗi lần chuyển mất $O(n)$, tổng $O(nq)$ quá chậm.
Ý tưởng của Mo: đề không bắt trả lời ngay từng câu, nên ta được phép đọc hết câu hỏi rồi đổi thứ tự xử lý (gọi là xử lý offline), miễn cuối cùng in đáp án đúng thứ tự đề cho. Thứ tự Mo chọn:
- chia trục vị trí thành các khối dài $B \approx \sqrt{n}$;
- sắp xếp câu hỏi theo khối chứa $l$ tăng dần; cùng khối thì theo $r$ tăng dần;
- giữ cửa sổ $[l, r]$ hiện tại (ban đầu rỗng: $l = 0, r = -1$), với mỗi câu hỏi theo thứ tự mới thì dịch hai đầu cửa sổ từng bước một bằng
add/delcho tới khi khớp, rồi ghi đáp án vàoans[id].
Trong cùng một khối của $l$, đầu phải $r$ chỉ đi tới, còn đầu trái $l$ chỉ lắc qua lắc lại trong phạm vi một khối, tức không quá $B$ bước mỗi câu. Phần 5 sẽ đếm cụ thể. Trước hết em xem Mo chạy thật trên một ví dụ nhỏ, chú ý bảng cnt thay đổi ra sao ở mỗi bước:
Code dưới đây đúng y như mô phỏng, thêm hai chi tiết sẽ giải thích ở phần 5: nén số (vì $a_i$ tới $10^9$, không lập mảng cnt cỡ đó được) và mẹo chẵn lẻ khi sắp xếp. Bản Python viết thẳng bốn vòng lặp trong thân hàm thay vì gọi add/del, vì lời gọi hàm trong Python khá đắt.
Xem code C++ / Python: thuật toán Mo: đếm số giá trị phân biệt trong đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q, B, distinctCnt = 0;
vector<int> a, cnt;
void add(int i){ if(cnt[a[i]]++ == 0) distinctCnt++; } // a[i] vào cửa sổ
void del(int i){ if(--cnt[a[i]] == 0) distinctCnt--; } // a[i] ra khỏi cửa sổ
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
a.resize(n);
for(auto &x : a) cin >> x;
vector<int> v = a; // nén số: giá trị -> 0..k-1
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(auto &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin();
cnt.assign(v.size(), 0);
B = max(1, (int)sqrt(n));
vector<int> L(q), R(q), id(q), ans(q);
for(int k = 0; k < q; k++){ cin >> L[k] >> R[k]; L[k]--; R[k]--; id[k] = k; }
sort(id.begin(), id.end(), [&](int x, int y){
int bx = L[x] / B, by = L[y] / B;
if(bx != by) return bx < by;
return (bx & 1) ? R[x] > R[y] : R[x] < R[y]; // mẹo chẵn lẻ
});
int l = 0, r = -1; // cửa sổ rỗng
for(int t : id){
while(r < R[t]) add(++r); // mở rộng trước
while(l > L[t]) add(--l);
while(r > R[t]) del(r--); // thu hẹp sau
while(l < L[t]) del(l++);
ans[t] = distinctCnt;
}
for(int k = 0; k < q; k++) cout << ans[k] << "\n";
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
comp = {}
a = [comp.setdefault(int(x), len(comp)) for x in data[2:2 + n]] # nén số bằng dict
L = [int(x) - 1 for x in data[2 + n:2 + n + 2 * q:2]]
R = [int(x) - 1 for x in data[3 + n:3 + n + 2 * q:2]]
B = max(1, isqrt(n))
def key(k): # (khối của l, r) với mẹo chẵn lẻ
b = L[k] // B
return (b, R[k] if b % 2 == 0 else -R[k])
order = sorted(range(q), key=key)
cnt = [0] * len(comp)
ans = [0] * q
l, r, d = 0, -1, 0 # d = số giá trị phân biệt
for k in order: # viết thẳng vòng lặp, không gọi hàm: nhanh hơn
ql, qr = L[k], R[k]
while r < qr:
r += 1; v = a[r]
if cnt[v] == 0: d += 1
cnt[v] += 1
while l > ql:
l -= 1; v = a[l]
if cnt[v] == 0: d += 1
cnt[v] += 1
while r > qr:
v = a[r]; cnt[v] -= 1
if cnt[v] == 0: d -= 1
r -= 1
while l < ql:
v = a[l]; cnt[v] -= 1
if cnt[v] == 0: d -= 1
l += 1
ans[k] = d
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Khung chạy tay theo dõi từng dòng: mỗi lần con trỏ dịch, code nhảy vào add hoặc del. Bản này để dễ nhìn nên chưa dùng nén số và mẹo chẵn lẻ, giá trị chỉ từ 1 đến 9.
sort(id.begin(), id.end(), [&](int x, int y){
if(L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return R[x] < R[y];
});
int l = 0, r = -1; // cửa sổ rỗng
for(int t : id){
while(r < R[t]) add(++r); // mở rộng trước
while(l > L[t]) add(--l);
while(r > R[t]) del(r--); // thu hẹp sau
while(l < L[t]) del(l++);
ans[t] = /* đáp án của cửa sổ */;
}add, del và biến đáp án. Câu hỏi để tự kiểm tra: “thêm hoặc bớt một phần tử ở mép cửa sổ, em có cập nhật đáp án trong $O(1)$ được không?” Được thì gần như chắc chắn dùng được Mo.del sẽ bớt những phần tử chưa từng được thêm, cnt bị âm. Với bài đếm phân biệt có khi vẫn may mắn ra đúng, nhưng với bài như tổng $cnt^2$ hay đếm cặp thì sai ngay. Ngoài ra, Mo cơ bản chỉ dùng cho bài không có thao tác sửa dãy và cho phép trả lời offline.Phần 5Độ phức tạp của Mo và các mẹo tối ưu
Đếm số bước dịch con trỏ. Gọi $B$ là kích thước khối, có $\frac{n}{B}$ khối.
- Con trỏ phải $r$: trong một khối của $l$, $r$ chỉ tăng nên đi tối đa $n$ bước; sang khối mới nó có thể lùi về, thêm tối đa $n$ bước nữa. Tổng: $O(\frac{n}{B} \cdot n)$.
- Con trỏ trái $l$: giữa hai câu hỏi cùng khối, $l$ dịch không quá $B$ bước; khi đổi khối thì dịch không quá $2B$. Tổng: $O(qB)$ (cộng thêm $O(n)$ cho các lần đổi khối).
Tổng cộng $O\left(\frac{n^2}{B} + qB\right)$. Chọn $B = \sqrt{n}$ được $O((n + q)\sqrt{n})$. Nếu $q$ khác $n$ nhiều, chọn $B = \frac{n}{\sqrt{q}}$ thì hai vế cân bằng, được $O(n\sqrt{q})$. Với $n = q = 2 \cdot 10^5$: khoảng $2 \cdot 2 \cdot 10^5 \cdot 447 \approx 1{,}8 \cdot 10^8$ lần gọi add/del, mỗi lần chỉ vài phép tính: C++ chạy chừng 0,5–1 giây.
Hình 2. Chín câu hỏi với $n = 25$, $B = 5$, vẽ thành các điểm $(l, r)$. Đường nét đứt là đường đi của “cửa sổ” theo thứ tự Mo: đi lên trong từng dải, mỗi lần sang dải mới thì tụt xuống.
Mô phỏng dưới đây dùng đúng dữ liệu của Hình 2. Em bấm Tiếp để thấy chi phí từng lần chuyển, rồi so tổng số bước của thứ tự đề cho, thứ tự Mo và Mo chẵn lẻ. Thử tự nhập các câu hỏi “đầu này, đầu kia” xen kẽ để thấy thứ tự đề cho tệ cỡ nào:
Mẹo 1: sắp $r$ xen kẽ chẵn lẻ. Trong thứ tự Mo cơ bản, cuối mỗi khối $r$ đang ở rất xa bên phải, sang khối sau lại lùi về gần $l$ rồi chạy lên lại. Nếu ở khối chẵn ta sắp $r$ tăng, khối lẻ sắp $r$ giảm, thì $r$ đi lên ở khối này và quét xuống luôn ở khối sau, đỡ được gần một nửa quãng đường của $r$. Chỉ cần sửa một dòng trong hàm so sánh: return (bx & 1) ? R[x] > R[y] : R[x] < R[y];. Trên dữ liệu lớn, mẹo này thường giúp nhanh hơn 20–40%.
Mẹo 2: nén số. Mảng cnt đánh chỉ số theo giá trị, mà $a_i$ tới $10^9$ (hoặc âm) thì không thể lập mảng cỡ đó. Nhưng bài đếm phân biệt chỉ quan tâm hai số bằng nhau hay không, nên ta đổi mỗi giá trị về thứ hạng của nó trong danh sách các giá trị khác nhau: sắp xếp bản sao, xoá trùng bằng unique, rồi dùng lower_bound để tra thứ hạng (cách nén giá trị em đã gặp ở bài 31). Trong Python còn gọn hơn: comp.setdefault(x, len(comp)) gán số hiệu theo thứ tự xuất hiện, không cần sắp xếp. Đừng dùng map/dict thay cho mảng cnt bên trong add/del: nó được gọi hàng trăm triệu lần, chậm thêm một hằng số là quá giờ ngay.
| Kỹ thuật | Chuẩn bị | Mỗi thao tác | Tổng | Offline? |
|---|---|---|---|---|
| Duyệt trực tiếp | – | $O(n)$ | $O(nq)$ | không |
| Chia căn, tổng đoạn | $O(n)$ | $O(\sqrt{n})$ | $O(n + q\sqrt{n})$ | không |
| Chia căn, khối sắp xếp | $O(n \log n)$ | $O(\sqrt{n} \log n)$ | $O(q\sqrt{n}\log n)$ | không |
| Thuật toán Mo | $O(q \log q)$ sắp xếp | trung bình $O(\frac{n}{\sqrt{q}})$ bước | $O((n + q)\sqrt{n})$ | có, không sửa dãy |
| Cây phân đoạn | $O(n)$ | $O(\log n)$ | $O(n + q\log n)$ | không |
Bảng 3. Độ phức tạp các cách xử lý truy vấn đoạn đã học. Chia căn và Mo chậm hơn cây phân đoạn, nhưng giải được những bài mà đáp án không ghép được từ hai nửa.
sys.stdin.buffer, nén số bằng dict, viết vòng lặp trực tiếp, mẹo chẵn lẻ) nhưng vẫn chỉ an toàn khi $n, q$ cỡ $2 \cdot 10^4$–$3 \cdot 10^4$. Với giới hạn $10^5$ trở lên, thầy khuyên dùng C++ cho các bài Mo. Riêng các bài chia căn ở phần 1–3, Python vẫn ổn nếu em đẩy việc vào sum, min, bisect như đã làm.2. Đáp án của đoạn không ghép được từ hai nửa: số giá trị phân biệt, số giá trị xuất hiện đúng $k$ lần, tổng $cnt^2$, số cặp bằng nhau, số đoạn con có XOR bằng $k$…
3. Thêm hoặc bớt một phần tử ở mép cửa sổ thì cập nhật đáp án được trong $O(1)$.
4. $n, q \le 10^5$ đến $2 \cdot 10^5$, giới hạn thời gian 1–3 giây.
- Dấu trong đoạn (MULTI) (Trung bình)
- Tăng Đầu Giảm Cuối (ARRAYM) (Trung bình)
- Xâu Duy Nhất (Xauduynhat) (Trung bình)
- Hộp màu (COLORBOX) (Khá)
- Chênh Lệch Lớn Nhất (Khó)
- Đếm Phép Nhân (Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 3) (Khó)
Bài tậpLuyện chia căn và thuật toán Mo
Cho dãy $n$ số nguyên ($n, q \le 10^5$, $|a_i| \le 10^9$) và $q$ thao tác: 1 i x gán $a_i = x$; 2 l r in ra số nhỏ nhất trong $a_l, \ldots, a_r$. Hãy giải bằng chia căn.
8 4
4 7 2 9 5 1 8 6
2 2 6
1 6 10
2 2 6
2 6 81
2
6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
mn[b] là min của khối. Khác với tổng, khi gán một phần tử ta không sửa min theo kiểu “cộng thêm chênh lệch” được (nếu phần tử nhỏ nhất bị tăng lên thì min mới là ai?), nên cứ tính lại min của cả khối trong $O(B)$, vẫn ổn. Câu hỏi đi đúng khuôn ba vòng lặp. Ví dụ: đoạn $[2, 6]$ là 7 2 9 5 1, min = 1; sau khi gán $a_6 = 10$ thì min = 2; đoạn $[6, 8]$ là 10 8 6, min = 6.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, B;
vector<long long> a, mn; // mn[b] = min của khối b
void rebuild(int b){ // tính lại min của khối b: O(B)
mn[b] = LLONG_MAX;
for(int i = b * B; i < min(n, (b + 1) * B); i++) mn[b] = min(mn[b], a[i]);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
B = max(1, (int)sqrt(n));
a.resize(n); mn.assign(n / B + 1, LLONG_MAX);
for(int i = 0; i < n; i++){ cin >> a[i]; mn[i / B] = min(mn[i / B], a[i]); }
while(q--){
int t; long long x, y;
cin >> t >> x >> y;
if(t == 1){ a[x - 1] = y; rebuild((x - 1) / B); }
else {
int l = x - 1, r = y - 1;
long long res = LLONG_MAX;
while(l <= r && l % B != 0) res = min(res, a[l++]);
while(l + B - 1 <= r){ res = min(res, mn[l / B]); l += B; }
while(l <= r) res = min(res, a[l++]);
cout << res << "\n";
}
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
mn = [min(a[i:i + B]) for i in range(0, n, B)] # min của từng khối
out, p = [], 2 + n
for _ in range(q):
t, x, y = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
if t == 1:
i = x - 1
a[i] = y
b = i // B
mn[b] = min(a[b * B:(b + 1) * B]) # tính lại khối: O(B)
else:
l, r = x - 1, y - 1
bl, br = l // B, r // B
if bl == br:
out.append(min(a[l:r + 1]))
else:
res = min(min(a[l:(bl + 1) * B]), min(a[br * B:r + 1]))
if bl + 1 < br:
res = min(res, min(mn[bl + 1:br]))
out.append(res)
print('\n'.join(map(str, out)))
main()Cho dãy $n$ số nguyên ($n, q \le 2 \cdot 10^5$, $|a_i|, |x| \le 10^9$) và $q$ thao tác: 1 l r x cộng $x$ vào mọi phần tử $a_l, \ldots, a_r$; 2 i in ra giá trị hiện tại của $a_i$.
6 5
1 2 3 4 5 6
1 2 5 10
2 3
1 1 6 -1
2 6
2 113
5
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
a[i], khối nằm trọn chỉ lz[b] += x. Giá trị thật của $a_i$ là a[i] + lz[i / B], trả lời trong $O(1)$. Giá trị có thể tới $2 \cdot 10^5 \cdot 10^9$ nên dùng long long. Ví dụ: $a_3 = 3 + 10 = 13$, $a_6 = 6 - 1 = 5$, $a_1 = 1 - 1 = 0$. (Bài này cũng giải được bằng mảng hiệu kết hợp Fenwick như bài 31; ở đây ta luyện chia căn.)Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
int B = max(1, (int)sqrt(n));
vector<long long> a(n), lz(n / B + 1, 0);
for(auto &x : a) cin >> x;
while(q--){
int t; cin >> t;
if(t == 1){
int l, r; long long x;
cin >> l >> r >> x; l--; r--;
while(l <= r && l % B != 0) a[l++] += x;
while(l + B - 1 <= r){ lz[l / B] += x; l += B; } // cả khối: chỉ dán nhãn
while(l <= r) a[l++] += x;
} else {
int i; cin >> i; i--;
cout << a[i] + lz[i / B] << "\n"; // giá trị thật = a[i] + nhãn
}
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
lz = [0] * (n // B + 1)
out, p = [], 2 + n
for _ in range(q):
if data[p] == b'1':
l, r, x = int(data[p + 1]) - 1, int(data[p + 2]) - 1, int(data[p + 3]); p += 4
while l <= r and l % B:
a[l] += x; l += 1
while l + B - 1 <= r:
lz[l // B] += x; l += B
while l <= r:
a[l] += x; l += 1
else:
i = int(data[p + 1]) - 1; p += 2
out.append(a[i] + lz[i // B])
print('\n'.join(map(str, out)))
main()Có $n$ bóng đèn xếp hàng, ban đầu tất cả đều tắt ($n, q \le 10^5$). Có $q$ thao tác: 1 l r bấm công tắc mọi đèn từ $l$ tới $r$ (đèn đang tắt thì sáng, đang sáng thì tắt); 2 l r đếm số đèn đang sáng trong đoạn $[l, r]$.
8 5
1 2 6
2 1 8
1 4 8
2 1 8
2 5 65
4
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
fl[b] (cả khối đã bị đảo lẻ lần hay chưa) và on[b] là số đèn sáng thật của khối. Trạng thái thật của đèn $i$ là a[i] ^ fl[i / B]. Đảo nguyên khối: fl[b] ^= 1 và on[b] = độ dài khối − on[b]. Đảo lẻ một đèn: a[i] ^= 1 rồi tăng hoặc giảm on[b] theo trạng thái thật mới. Câu hỏi: phần lẻ cộng a[i] ^ fl, khối trọn cộng on[b]. Ví dụ: sau thao tác đầu đèn 2..6 sáng (5 đèn); sau thao tác thứ hai đèn 4, 5, 6 tắt, đèn 7, 8 sáng, còn 2, 3, 7, 8 sáng (4 đèn); đèn 5, 6 đều tắt.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, B;
vector<int> a, on, fl; // a[i]: trạng thái riêng, fl[b]: cả khối b đã bị đảo chưa, on[b]: số đèn sáng thật
int len(int b){ return min(n, (b + 1) * B) - b * B; }
void flipOne(int i){
int b = i / B;
a[i] ^= 1;
if((a[i] ^ fl[b]) == 1) on[b]++; else on[b]--;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
B = max(1, (int)sqrt(n));
a.assign(n, 0); on.assign(n / B + 1, 0); fl.assign(n / B + 1, 0);
while(q--){
int t, l, r;
cin >> t >> l >> r; l--; r--;
if(t == 1){
while(l <= r && l % B != 0) flipOne(l++);
while(l + B - 1 <= r){ int b = l / B; fl[b] ^= 1; on[b] = len(b) - on[b]; l += B; }
while(l <= r) flipOne(l++);
} else {
int res = 0;
while(l <= r && l % B != 0){ res += a[l] ^ fl[l / B]; l++; }
while(l + B - 1 <= r){ res += on[l / B]; l += B; }
while(l <= r){ res += a[l] ^ fl[l / B]; l++; }
cout << res << "\n";
}
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
B = max(1, isqrt(n))
nb = (n + B - 1) // B
a = [0] * n
on = [0] * nb # số đèn sáng thật của khối
fl = [0] * nb # nhãn đảo cả khối
ln = [min(n, (b + 1) * B) - b * B for b in range(nb)]
out, p = [], 2
for _ in range(q):
t, l, r = int(data[p]), int(data[p + 1]) - 1, int(data[p + 2]) - 1; p += 3
if t == 1:
i = l
while i <= r:
b = i // B
if i % B == 0 and i + B - 1 <= r: # cả khối nằm trọn
fl[b] ^= 1; on[b] = ln[b] - on[b]; i += B
else:
a[i] ^= 1
on[b] += 1 if a[i] ^ fl[b] else -1
i += 1
else:
res, i = 0, l
while i <= r:
b = i // B
if i % B == 0 and i + B - 1 <= r:
res += on[b]; i += B
else:
res += a[i] ^ fl[b]; i += 1
out.append(res)
print('\n'.join(map(str, out)))
main()Cho dãy $n$ số nguyên ($n, q \le 10^5$, $|a_i| \le 10^9$) và $q$ câu hỏi, mỗi câu gồm hai số $x, k$ ($1 \le x, k \le n$): tính $a_x + a_{x+k} + a_{x+2k} + \cdots$ (cộng tới khi chỉ số vượt quá $n$).
7
1 2 3 4 5 6 7
3
1 3
2 1
6 512
27
6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
suf[i] = a[i] + suf[i + k] (đi từ phải sang trái) trong $O(n)$, rồi mỗi câu hỏi đọc suf[x]. Có không quá $\sqrt{n}$ giá trị $k$ nhỏ nên tổng là $O((n + q)\sqrt{n})$. Ví dụ: $a_1 + a_4 + a_7 = 12$; $k = 1$ thì cộng hết từ $a_2$, được 27; $a_6 = 6$ vì $6 + 5 > 7$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
int q; cin >> q;
int B = max(1, (int)sqrt(n));
vector<long long> ans(q);
vector<vector<pair<int,int>>> byK(B + 1); // truy vấn có bước nhỏ, gom theo k
for(int j = 0; j < q; j++){
int x, k; cin >> x >> k; x--;
if(k <= B) byK[k].push_back({x, j});
else { // bước lớn: nhảy thẳng, tối đa n / k < √n bước
long long s = 0;
for(int i = x; i < n; i += k) s += a[i];
ans[j] = s;
}
}
vector<long long> suf(n);
for(int k = 1; k <= B; k++){
if(byK[k].empty()) continue;
for(int i = n - 1; i >= 0; i--) suf[i] = a[i] + (i + k < n ? suf[i + k] : 0);
for(auto [x, j] : byK[k]) ans[j] = suf[x];
}
for(int j = 0; j < q; j++) cout << ans[j] << "\n";
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(x) for x in data[1:1 + n]]
q = int(data[1 + n])
B = max(1, isqrt(n))
ans = [0] * q
byK = {}
p = 2 + n
for j in range(q):
x, k = int(data[p]) - 1, int(data[p + 1]); p += 2
if k <= B:
byK.setdefault(k, []).append((x, j))
else:
ans[j] = sum(a[x::k]) # bước lớn: ít hơn √n số hạng
for k, lst in byK.items(): # bước nhỏ: một mảng tổng hậu tố cho mỗi k
suf = a[:]
for i in range(n - 1 - k, -1, -1):
suf[i] += suf[i + k]
for x, j in lst:
ans[j] = suf[x]
print('\n'.join(map(str, ans)))
main()Cho dãy $n$ số nguyên ($n, q \le 10^5$, $|a_i| \le 10^9$) và $q$ câu hỏi l r: trong đoạn $a_l, \ldots, a_r$ có bao nhiêu giá trị xuất hiện đúng hai lần?
8 3
1 2 1 3 2 3 3 1
1 5
2 7
1 82
1
1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
two đếm số giá trị có cnt đúng bằng 2. Trong add và del: trước khi đổi cnt[v], nếu nó đang bằng 2 thì two--; sau khi đổi, nếu nó bằng 2 thì two++. Nhớ nén số vì $a_i$ tới $10^9$. Ví dụ: đoạn $[1, 5]$ = 1 2 1 3 2 có số 1 và số 2 xuất hiện hai lần; đoạn $[2, 7]$ = 2 1 3 2 3 3 chỉ có số 2; cả dãy có số 1 ba lần, số 3 ba lần, chỉ số 2 hai lần.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, B, two = 0;
vector<int> a, cnt;
void add(int i){ if(cnt[a[i]] == 2) two--; cnt[a[i]]++; if(cnt[a[i]] == 2) two++; }
void del(int i){ if(cnt[a[i]] == 2) two--; cnt[a[i]]--; if(cnt[a[i]] == 2) two++; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
a.resize(n);
for(auto &x : a) cin >> x;
vector<int> v = a;
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(auto &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin();
cnt.assign(v.size(), 0);
B = max(1, (int)sqrt(n));
vector<int> L(q), R(q), id(q), ans(q);
for(int k = 0; k < q; k++){ cin >> L[k] >> R[k]; L[k]--; R[k]--; id[k] = k; }
sort(id.begin(), id.end(), [&](int x, int y){
if(L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return ((L[x] / B) & 1) ? R[x] > R[y] : R[x] < R[y];
});
int l = 0, r = -1;
for(int t : id){
while(r < R[t]) add(++r);
while(l > L[t]) add(--l);
while(r > R[t]) del(r--);
while(l < L[t]) del(l++);
ans[t] = two;
}
for(int k = 0; k < q; k++) cout << ans[k] << "\n";
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
comp = {}
a = [comp.setdefault(int(x), len(comp)) for x in data[2:2 + n]]
L = [int(x) - 1 for x in data[2 + n:2 + n + 2 * q:2]]
R = [int(x) - 1 for x in data[3 + n:3 + n + 2 * q:2]]
B = max(1, isqrt(n))
order = sorted(range(q), key=lambda k: (L[k] // B, R[k] if (L[k] // B) % 2 == 0 else -R[k]))
cnt = [0] * len(comp)
ans = [0] * q
l, r, two = 0, -1, 0
for k in order:
ql, qr = L[k], R[k]
while r < qr:
r += 1; v = a[r]
if cnt[v] == 2: two -= 1
cnt[v] += 1
if cnt[v] == 2: two += 1
while l > ql:
l -= 1; v = a[l]
if cnt[v] == 2: two -= 1
cnt[v] += 1
if cnt[v] == 2: two += 1
while r > qr:
v = a[r]
if cnt[v] == 2: two -= 1
cnt[v] -= 1
if cnt[v] == 2: two += 1
r -= 1
while l < ql:
v = a[l]
if cnt[v] == 2: two -= 1
cnt[v] -= 1
if cnt[v] == 2: two += 1
l += 1
ans[k] = two
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Cho dãy $n$ số nguyên dương ($n, q \le 2 \cdot 10^5$, $1 \le a_i \le 10^6$). Với đoạn $[l, r]$, gọi $c_v$ là số lần giá trị $v$ xuất hiện trong đoạn. Sức mạnh của đoạn là $\sum_v c_v^2 \cdot v$. Trả lời $q$ câu hỏi l r.
6 3
1 2 1 3 2 1
1 3
2 5
1 66
12
20📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cur là sức mạnh của cửa sổ. Khi $c_v$ tăng từ $c$ lên $c + 1$, $c^2 v$ thành $(c+1)^2 v$, tức tăng thêm $(2c + 1)\,v$; khi giảm từ $c + 1$ về $c$ thì bớt đúng lượng đó. Vì $a_i \le 10^6$ nên dùng thẳng mảng cnt cỡ $10^6$, không cần nén. Đáp án có thể tới $n^2 \cdot 10^6 = 4 \cdot 10^{16}$: bắt buộc long long. Ví dụ đoạn $[1, 6]$: số 1 ba lần, số 2 hai lần, số 3 một lần: $9 \cdot 1 + 4 \cdot 2 + 1 \cdot 3 = 20$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, B, a[200005], cnt[1000005];
long long cur = 0; // tổng cnt[v]^2 * v của cửa sổ
void add(int i){ int v = a[i]; cur += (2LL * cnt[v] + 1) * v; cnt[v]++; } // (c+1)^2 - c^2 = 2c + 1
void del(int i){ int v = a[i]; cnt[v]--; cur -= (2LL * cnt[v] + 1) * v; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 0; i < n; i++) cin >> a[i];
B = max(1, (int)sqrt(n));
vector<int> L(q), R(q), id(q);
vector<long long> ans(q);
for(int k = 0; k < q; k++){ cin >> L[k] >> R[k]; L[k]--; R[k]--; id[k] = k; }
sort(id.begin(), id.end(), [&](int x, int y){
if(L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return ((L[x] / B) & 1) ? R[x] > R[y] : R[x] < R[y];
});
int l = 0, r = -1;
for(int t : id){
while(r < R[t]) add(++r);
while(l > L[t]) add(--l);
while(r > R[t]) del(r--);
while(l < L[t]) del(l++);
ans[t] = cur;
}
for(int k = 0; k < q; k++) cout << ans[k] << "\n";
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
L = [int(x) - 1 for x in data[2 + n:2 + n + 2 * q:2]]
R = [int(x) - 1 for x in data[3 + n:3 + n + 2 * q:2]]
B = max(1, isqrt(n))
order = sorted(range(q), key=lambda k: (L[k] // B, R[k] if (L[k] // B) % 2 == 0 else -R[k]))
cnt = [0] * (max(a) + 1)
ans = [0] * q
l, r, cur = 0, -1, 0
for k in order:
ql, qr = L[k], R[k]
while r < qr:
r += 1; v = a[r]
cur += (2 * cnt[v] + 1) * v; cnt[v] += 1
while l > ql:
l -= 1; v = a[l]
cur += (2 * cnt[v] + 1) * v; cnt[v] += 1
while r > qr:
v = a[r]; cnt[v] -= 1
cur -= (2 * cnt[v] + 1) * v; r -= 1
while l < ql:
v = a[l]; cnt[v] -= 1
cur -= (2 * cnt[v] + 1) * v; l += 1
ans[k] = cur
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Cho dãy $n$ số nguyên không âm ($n, q \le 10^5$, $0 \le a_i, k < 2^{20}$) và $q$ câu hỏi l r: đếm số đoạn con $[i, j]$ với $l \le i \le j \le r$ mà $a_i \oplus a_{i+1} \oplus \cdots \oplus a_j = k$ ($\oplus$ là phép XOR). Dòng đầu gồm $n, q, k$.
6 3 3
1 2 3 1 2 3
1 3
2 6
1 62
4
6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
add(i) cộng cnt[P[i] ^ k] vào đáp án rồi mới tăng cnt[P[i]]; del(i) giảm cnt[P[i]] trước rồi trừ cnt[P[i] ^ k] (thứ tự này quan trọng khi $k = 0$). Ví dụ đoạn $[1, 3]$ có hai đoạn con XOR bằng 3: $1 \oplus 2$ và $3$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, K, B, P[200005], cnt[1 << 20];
long long cur = 0; // số cặp x < y trong cửa sổ có P[x] ^ P[y] = K
void add(int i){ cur += cnt[P[i] ^ K]; cnt[P[i]]++; } // đếm trước, thêm sau
void del(int i){ cnt[P[i]]--; cur -= cnt[P[i] ^ K]; } // bớt trước, trừ sau
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q >> K;
for(int i = 1; i <= n; i++){ int x; cin >> x; P[i] = P[i - 1] ^ x; }
B = max(1, (int)sqrt(n + 1));
vector<int> L(q), R(q), id(q);
vector<long long> ans(q);
for(int k = 0; k < q; k++){ cin >> L[k] >> R[k]; L[k]--; id[k] = k; } // đoạn chỉ số tiền tố [l-1, r]
sort(id.begin(), id.end(), [&](int x, int y){
if(L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return ((L[x] / B) & 1) ? R[x] > R[y] : R[x] < R[y];
});
int l = 0, r = -1;
for(int t : id){
while(r < R[t]) add(++r);
while(l > L[t]) add(--l);
while(r > R[t]) del(r--);
while(l < L[t]) del(l++);
ans[t] = cur;
}
for(int k = 0; k < q; k++) cout << ans[k] << "\n";
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q, K = int(data[0]), int(data[1]), int(data[2])
P = [0] * (n + 1)
for i in range(1, n + 1):
P[i] = P[i - 1] ^ int(data[2 + i])
L = [int(x) - 1 for x in data[3 + n:3 + n + 2 * q:2]] # đoạn tiền tố [l-1, r]
R = [int(x) for x in data[4 + n:4 + n + 2 * q:2]]
B = max(1, isqrt(n + 1))
order = sorted(range(q), key=lambda k: (L[k] // B, R[k] if (L[k] // B) % 2 == 0 else -R[k]))
cnt = [0] * (1 << 20)
ans = [0] * q
l, r, cur = 0, -1, 0
for k in order:
ql, qr = L[k], R[k]
while r < qr:
r += 1; v = P[r]
cur += cnt[v ^ K]; cnt[v] += 1
while l > ql:
l -= 1; v = P[l]
cur += cnt[v ^ K]; cnt[v] += 1
while r > qr:
v = P[r]; cnt[v] -= 1
cur -= cnt[v ^ K]; r -= 1
while l < ql:
v = P[l]; cnt[v] -= 1
cur -= cnt[v ^ K]; l += 1
ans[k] = cur
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Có $n$ ô xếp thành hàng, ô $i$ có lò xo độ mạnh $a_i \ge 1$: viên bi rơi vào ô $i$ sẽ bật sang ô $i + a_i$, và rời bàn khi chỉ số vượt quá $n$ ($n, q \le 10^5$, $1 \le a_i \le n$). Có $q$ thao tác: 0 i x đổi độ mạnh ô $i$ thành $x$; 1 i thả bi vào ô $i$, in ra ô cuối cùng bi chạm vào trước khi rời bàn và số lần bật (tính cả lần bật ra khỏi bàn).
8 4
1 2 1 3 1 2 1 1
1 1
0 4 5
1 1
1 68 5
4 3
8 2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
nxt[i] là ô đầu tiên bi tới được ngoài khối của $i$, jumps[i] là số lần bật để tới đó, last[i] là ô cuối cùng trong khối trước khi ra. Tính trong mỗi khối từ phải sang trái: nếu $j = i + a_i$ đã ra khỏi khối thì nxt[i] = j, jumps[i] = 1, last[i] = i; ngược lại kế thừa từ ô $j$. Thả bi: mỗi bước nhảy hẳn qua một khối, $O(\frac{n}{B})$. Đổi độ mạnh: chỉ tính lại một khối, $O(B)$. Ví dụ: bi từ ô 1 đi 1 → 2 → 4 → 7 → 8 → ra ngoài (5 lần bật); sau khi $a_4 = 5$ thì 1 → 2 → 4 → ra ngoài (ô cuối là 4, 3 lần bật); bi từ ô 6 đi 6 → 8 → ra ngoài.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, B, a[200005], nxt[200005], jumps[200005], last[200005];
void rebuild(int b){ // tính lại khối b từ phải sang trái
int lo = b * B, hi = min(n, lo + B) - 1;
for(int i = hi; i >= lo; i--){
int j = i + a[i];
if(j > hi){ nxt[i] = j; jumps[i] = 1; last[i] = i; } // nhảy ra khỏi khối
else { nxt[i] = nxt[j]; jumps[i] = jumps[j] + 1; last[i] = last[j]; }
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 0; i < n; i++) cin >> a[i];
B = max(1, (int)sqrt(n));
for(int b = 0; b * B < n; b++) rebuild(b);
while(q--){
int t; cin >> t;
if(t == 0){ int i, x; cin >> i >> x; a[i - 1] = x; rebuild((i - 1) / B); }
else {
int i; cin >> i; i--;
int tot = 0, lastHole = i;
while(i < n){ tot += jumps[i]; lastHole = last[i]; i = nxt[i]; } // mỗi bước qua hẳn một khối
cout << lastHole + 1 << " " << tot << "\n";
}
}
return 0;
}import sys
from math import isqrt
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
B = max(1, isqrt(n))
nxt, jumps, last = [0] * n, [0] * n, [0] * n
def rebuild(b): # tính lại khối b từ phải sang trái
lo = b * B; hi = min(n, lo + B) - 1
for i in range(hi, lo - 1, -1):
j = i + a[i]
if j > hi:
nxt[i] = j; jumps[i] = 1; last[i] = i
else:
nxt[i] = nxt[j]; jumps[i] = jumps[j] + 1; last[i] = last[j]
for b in range((n + B - 1) // B):
rebuild(b)
out, p = [], 2 + n
for _ in range(q):
if data[p] == b'0':
i, x = int(data[p + 1]) - 1, int(data[p + 2]); p += 3
a[i] = x
rebuild(i // B)
else:
i = int(data[p + 1]) - 1; p += 2
tot, lh = 0, i
while i < n:
tot += jumps[i]; lh = last[i]; i = nxt[i]
out.append('%d %d' % (lh + 1, tot))
print('\n'.join(out))
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét