So giá chợ nổi (Đề tự luyện HSG Tin 12 – Bài 5)
Đề bài
So giá chợ nổi. Có $N$ chiếc ghe xếp thành hàng, ghe thứ $i$ bán loại trái cây $a_i$. Đoạn ghe liên tiếp $[l, r]$ gọi là so giá được nếu mọi loại trái cây có mặt trong đoạn đều được bán bởi ít nhất hai ghe trong đoạn. Thầy Sơn có $Q$ câu hỏi: với mỗi cặp $L, R$, đếm số cặp $(l, r)$ với $L \le l \le r \le R$ mà đoạn $[l, r]$ so giá được.
Dữ liệu vào: dòng đầu $N, Q$ ($1 \le N, Q \le 2 \cdot 10^5$); dòng hai gồm $a_1, \dots, a_N$ ($1 \le a_i \le 10^9$); $Q$ dòng sau mỗi dòng một cặp $L, R$ ($1 \le L \le R \le N$).
Kết quả: $Q$ dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng.
- Subtask 1 (10%): $N, Q \le 100$.
- Subtask 2 (20%): $N \le 3000$.
- Subtask 3 (20%): $Q \le 5$.
- Subtask 4 (20%): $L = 1$ với mọi câu hỏi.
- Subtask 5 (30%): không có ràng buộc gì thêm.
8 3
7 5 3 5 5 5 3 3
1 8
2 7
3 610
5
3Cả hàng có 10 đoạn so giá được: $[2,7]$, $[2,8]$, $[3,7]$, $[3,8]$, $[4,5]$, $[4,6]$, $[4,8]$, $[5,6]$, $[5,8]$, $[7,8]$. Trong $[2, 7]$ có $[2,7]$, $[3,7]$, $[4,5]$, $[4,6]$, $[5,6]$. Trong $[3, 6]$ có $[4,5]$, $[4,6]$, $[5,6]$.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài So giá chợ nổiLời mở đầu
Đây là bài "trùm cuối" của đề, nên mình sẽ đi thật chậm. Bài có hai lớp khó chồng lên nhau: (1) đếm được các đoạn so giá được một cách nhanh, và (2) trả lời nhiều câu hỏi trên các đoạn con $[L, R]$ khác nhau. Ta gỡ lớp thứ nhất bằng một cách nhìn "theo từng vị trí bên phải", rồi gỡ lớp thứ hai bằng một kỹ thuật segment tree khá đặc biệt.
Nhận xét 1 – đổi "so giá được" thành "bằng 0"
Cố định đầu phải $r$. Với mỗi $l \le r$, đặt $f_r(l)$ = số loại trái cây chỉ có đúng một ghe trong đoạn $[l, r]$ (loại "lẻ loi"). Khi đó:
$$[l, r] \text{ so giá được} \iff f_r(l) = 0.$$
Nhận xét 2 – mỗi loại "lẻ loi" trên một đoạn $l$ liên tiếp
Xét một loại $v$. Gọi $p_1$ là lần xuất hiện cuối cùng của $v$ trong $[1, r]$, $p_2$ là lần xuất hiện ngay trước $p_1$ (bằng $0$ nếu không có). Loại $v$ có đúng một ghe trong $[l, r]$ khi và chỉ khi đoạn chứa $p_1$ mà không chứa $p_2$, tức là $p_2 < l \le p_1$. Vậy:
$$f_r(l) = \text{số loại } v \text{ mà } l \in (p_2(v),\ p_1(v)].$$
Mỗi loại góp $+1$ cho cả một đoạn các vị trí $l$. Hình dưới vẽ với dãy $a = 5, 3, 5, 3, 3, 7, 7, 5$ và $r = 8$:
Mỗi loại trái cây phủ một dải $(p_2, p_1]$. $f_r(l)$ là số dải phủ lên vị trí $l$.
Nhận xét 3 – khi $r$ tăng thì chỉ có 2 phép cộng trên đoạn
Chuyển từ $r - 1$ sang $r$, chỉ có loại $v = a_r$ thay đổi. Gọi $p_1$ = prv[r] (lần trước của $v$), $p_2$ = prv[p1]:
- dải cũ của $v$ là $(p_2, p_1]$ phải bỏ đi: cộng $-1$ trên đoạn $[p_2 + 1, p_1]$ (nếu $p_1 > 0$);
- dải mới của $v$ là $(p_1, r]$: cộng $+1$ trên đoạn $[p_1 + 1, r]$.
Một mẹo nhỏ cho gọn: cho các vị trí $l > r$ (chưa tới) mang sẵn giá trị $1$. Khi $r$ tới, vị trí $r$ có $f_r(r) = 1$ (chỉ một ghe) — vừa khớp sẵn, nên phép $+1$ chỉ cần làm trên $[p_1 + 1, r - 1]$. Quan trọng hơn: các vị trí chưa tới không bao giờ bằng 0, nên không bị đếm nhầm.
Nhận xét 4 – đếm số 0 = đếm số phần tử nhỏ nhất
$f_r(l) \ge 0$ luôn luôn. Vậy số vị trí có $f_r(l) = 0$ chính là số phần tử đạt giá trị nhỏ nhất, với điều kiện giá trị nhỏ nhất bằng $0$. Một segment tree lưu (min, số phần tử đạt min) và hỗ trợ cộng trên đoạn (lazy) làm được việc này trong $O(\log N)$. Đây là "chìa khoá" đầu tiên: ta không cần biết từng $f_r(l)$, chỉ cần min và số lượng min.
Mô phỏng dưới đây cho các bạn xem mảng $f_r$ thay đổi thế nào khi quét $r$ từ trái sang phải (ô mờ là vị trí chưa tới, mang giá trị 1; ô xanh là số 0):
Năm cách làm tương ứng năm subtask:
Cách 1Vét cạn từng câu hỏi – O(Q·N²) · 10%
Với mỗi câu hỏi $[L, R]$, ta thử mọi đầu trái $l$, rồi kéo đầu phải $r$ từ $l$ tới $R$. Khi thêm ghe $r$ vào, tăng c[a[r]]; giữ biến ones = số loại đang có đúng 1 ghe: nếu c vừa thành 1 thì ones++, vừa thành 2 thì ones--. Đoạn $[l, r]$ so giá được khi ones == 0. Mỗi câu hỏi tốn $O(N^2)$.
Vì $a_i$ lên tới $10^9$, bản C++ nén giá trị (sắp xếp, xoá trùng, lower_bound) để dùng mảng đếm; bản Python dùng luôn từ điển.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
// nen gia tri ve 0..k-1 de dem bang mang
vector<int> vals(a.begin() + 1, a.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 1; i <= n; i++) a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
vector<int> c(vals.size(), 0);
while (q--) {
int L, R;
scanf("%d %d", &L, &R);
long long res = 0;
for (int l = L; l <= R; l++) {
int ones = 0; // so loai dang co dung 1 ghe
for (int r = l; r <= R; r++) {
c[a[r]]++;
if (c[a[r]] == 1) ones++;
else if (c[a[r]] == 2) ones--;
if (ones == 0) res++;
}
for (int r = l; r <= R; r++) c[a[r]]--; // xoa dem cho lan sau
}
printf("%lld\n", res);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [0] + data[2:2 + n]
out = []
pos = 2 + n
for _ in range(q):
L = int(data[pos]); R = int(data[pos + 1]); pos += 2
res = 0
for l in range(L, R + 1):
c = {}
ones = 0 # so loai dang co dung 1 ghe
for r in range(l, R + 1):
x = a[r]
k = c.get(x, 0) + 1
c[x] = k
if k == 1:
ones += 1
elif k == 2:
ones -= 1
if ones == 0:
res += 1
out.append(res)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Cách 2Bảng đáp án cho mọi đầu trái – O(N² + Q) · 30%
Khi $N \le 3000$ nhưng $Q$ lớn, ta không thể vét cạn mỗi câu, nhưng có thể tính sẵn. Gọi $C(l, r)$ = số đoạn so giá được nằm trong $[l, r]$. Phân loại theo đầu trái:
$$C(l, r) = C(l + 1, r) + \#\{r' \le r : [l, r'] \text{ so giá được}\}.$$
Ta cho $l$ chạy từ $N$ về $1$, giữ một mảng row[r] = $C(l, r)$. Với mỗi $l$, kéo $r$ từ $l$ tới $N$ như Cách 1, đếm goodPrefix = số $r' \le r$ mà $[l, r']$ so giá được, rồi row[r] += goodPrefix. Xong một $l$ thì trả lời luôn các câu hỏi có $L = l$: đáp án là row[R]. Tổng $O(N^2 + Q)$, bộ nhớ chỉ $O(N + Q)$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<int> vals(a.begin() + 1, a.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 1; i <= n; i++) a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
vector<vector<pair<int,int>>> byL(n + 1); // cau hoi nhom theo L: (R, chi so)
for (int i = 0; i < q; i++) {
int L, R;
scanf("%d %d", &L, &R);
byL[L].push_back({R, i});
}
vector<long long> row(n + 1, 0), ans(q);
// row[r] = so doan so gia duoc nam trong [l, r] (l giam dan tu n ve 1)
vector<int> c(vals.size(), 0);
for (int l = n; l >= 1; l--) {
int ones = 0;
long long goodPrefix = 0; // so r' <= r ma [l, r'] so gia duoc
for (int r = l; r <= n; r++) {
c[a[r]]++;
if (c[a[r]] == 1) ones++;
else if (c[a[r]] == 2) ones--;
if (ones == 0) goodPrefix++;
row[r] += goodPrefix;
}
for (int r = l; r <= n; r++) c[a[r]]--;
for (auto &p : byL[l]) ans[p.second] = row[p.first];
}
for (int i = 0; i < q; i++) printf("%lld\n", ans[i]);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
mp = {}
a = [0] * (n + 1)
for i in range(n):
a[i + 1] = mp.setdefault(data[2 + i], len(mp)) # nen gia tri
byL = [[] for _ in range(n + 1)] # cau hoi nhom theo L
pos = 2 + n
for i in range(q):
L = int(data[pos]); R = int(data[pos + 1]); pos += 2
byL[L].append((R, i))
row = [0] * (n + 1) # row[r] = so doan so gia duoc nam trong [l, r]
ans = [0] * q
c = [0] * len(mp)
for l in range(n, 0, -1):
ones = 0
good = 0 # so r' <= r ma [l, r'] so gia duoc
for r in range(l, n + 1):
x = a[r]
k = c[x] + 1
c[x] = k
if k == 1:
ones += 1
elif k == 2:
ones -= 1
if ones == 0:
good += 1
row[r] += good
for r in range(l, n + 1):
c[a[r]] = 0
for R, i in byL[l]:
ans[i] = row[R]
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Cách 3Quét r, segment tree đếm min, làm riêng từng câu – O(Q·N log N) · 30%
Đây là lúc dùng Nhận xét 1–4. Với một câu hỏi $[L, R]$, ta chỉ quan tâm các vị trí $l \in [L, R]$. Dựng segment tree trên các vị trí đó, mọi giá trị ban đầu bằng 1. Quét $r$ từ $L$ tới $R$:
- $p_1$ =
prv[r]: cộng $+1$ trên $[\max(L, p_1 + 1),\ r - 1]$; - nếu $p_1 \ge L$: cộng $-1$ trên $[\max(L, p_2 + 1),\ p_1]$ với $p_2$ =
prv[p1]; - nếu min của cả cây bằng 0 thì cộng số phần tử đạt min vào đáp án (đó là số đoạn so giá được kết thúc tại $r$).
(Vị trí $l < L$ bị bỏ qua nên các đoạn cộng phải "kẹp" lại từ $L$. Dùng prv của cả dãy vẫn đúng, vì $f_r(l)$ chỉ phụ thuộc các ghe từ $l$ trở đi.)
Vì chỉ cần thông tin ở gốc nên cây không cần hàm truy vấn, và lazy không cần đẩy xuống: mỗi nút giữ lz[x] = lượng đã cộng cho cả đoạn của nút, và mn[x] = min(mn[con trái], mn[con phải]) + lz[x]. Số phần tử đạt min: cộng cnt của (các) con có min nhỏ nhất.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, a[MAXN], prv[MAXN];
int mn[4 * MAXN], cnt[4 * MAXN], lz[4 * MAXN];
void build(int x, int l, int r) {
mn[x] = 1; cnt[x] = r - l + 1; lz[x] = 0; // vi tri chua toi: gia tri 1
if (l == r) return;
int m = (l + r) / 2;
build(2 * x, l, m);
build(2 * x + 1, m + 1, r);
}
void update(int x, int l, int r, int ql, int qr, int v) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { mn[x] += v; lz[x] += v; return; }
int m = (l + r) / 2;
update(2 * x, l, m, ql, qr, v);
update(2 * x + 1, m + 1, r, ql, qr, v);
int A = mn[2 * x], B = mn[2 * x + 1];
mn[x] = min(A, B) + lz[x]; // lz[x] cua nut x khong day xuong
cnt[x] = (A <= B ? cnt[2 * x] : 0) + (B <= A ? cnt[2 * x + 1] : 0);
}
// dem so doan so gia duoc [l, r] voi L <= l <= r <= R
long long sweep(int L, int R) {
build(1, L, R);
long long res = 0;
for (int r = L; r <= R; r++) {
int p1 = prv[r];
if (max(L, p1 + 1) <= r - 1) update(1, L, R, max(L, p1 + 1), r - 1, +1);
if (p1 >= L) update(1, L, R, max(L, prv[p1] + 1), p1, -1);
if (mn[1] == 0) res += cnt[1]; // so l co f(l) = 0
}
return res;
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
map<int, int> last;
for (int i = 1; i <= n; i++) {
auto it = last.find(a[i]);
prv[i] = (it == last.end() ? 0 : it->second);
last[a[i]] = i;
}
while (q--) {
int L, R;
scanf("%d %d", &L, &R);
printf("%lld\n", sweep(L, R));
}
return 0;
}import sys
def sweep(L, R, prv, pre):
# dem so doan so gia duoc [l, r] voi L <= l <= r <= R; pre[r] = so doan co r' <= r
n = R - L + 1
size = 1
while size < n:
size *= 2
INF = 1 << 30
mn = [INF] * (2 * size)
cnt = [0] * (2 * size)
lz = [0] * (2 * size)
for i in range(n):
mn[size + i] = 1; cnt[size + i] = 1 # vi tri chua toi: gia tri 1
for k in range(size - 1, 0, -1):
A = mn[2 * k]; B = mn[2 * k + 1]
mn[k] = A if A < B else B
cnt[k] = (cnt[2 * k] if A <= B else 0) + (cnt[2 * k + 1] if B <= A else 0)
def update(l, r, v): # cong v vao vi tri l..r (trong [L, R])
l += size - L; r += size - L + 1
l0 = l; r0 = r - 1
while l < r:
if l & 1:
mn[l] += v; lz[l] += v; l += 1
if r & 1:
r -= 1; mn[r] += v; lz[r] += v
l >>= 1; r >>= 1
for k in (l0 >> 1, r0 >> 1): # tinh lai cac to tien (lz khong day xuong)
while k:
A = mn[2 * k]; B = mn[2 * k + 1]
mn[k] = (A if A < B else B) + lz[k]
cnt[k] = (cnt[2 * k] if A <= B else 0) + (cnt[2 * k + 1] if B <= A else 0)
k >>= 1
res = 0
for r in range(L, R + 1):
p1 = prv[r]
lo = p1 + 1 if p1 + 1 > L else L
if lo <= r - 1:
update(lo, r - 1, 1)
if p1 >= L:
p2 = prv[p1]
update(p2 + 1 if p2 + 1 > L else L, p1, -1)
if mn[1] == 0:
res += cnt[1] # so l co f(l) = 0
pre[r] = res
return res
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
prv = [0] * (n + 1)
last = {}
for i in range(1, n + 1):
x = data[1 + i]
prv[i] = last.get(x, 0)
last[x] = i
pre = [0] * (n + 1)
out = []
pos = 2 + n
for _ in range(q):
L = int(data[pos]); R = int(data[pos + 1]); pos += 2
out.append(sweep(L, R, prv, pre))
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Cách 4Khi mọi L = 1 – một lần quét + tổng tiền tố – O((N + Q) log N) · 50%
Nếu mọi câu hỏi đều có $L = 1$ thì chỉ cần quét một lần trên cả dãy như Cách 3, ghi lại pre[r] = số đoạn so giá được có đầu phải $\le r$. Đáp án câu hỏi $[1, R]$ chính là pre[R]. Các câu hỏi còn lại (khi có $L > 1$) vẫn làm như Cách 3.
pre[R] - pre[L-1]. Sai! Hiệu đó vẫn đếm các đoạn $[l, r]$ có $l < L \le r$ (bắt đầu trước $L$ nhưng kết thúc sau $L$). Bộ test bắt lỗi này ở mọi subtask trừ subtask 4. (Ví dụ của đề cố ý để cách sai này vẫn ra đúng cả ba câu hỏi, vì ở đó không có đoạn so giá được nào bắt đầu trước $L$ mà kết thúc trong $[L, R]$.)#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q, a[MAXN], prv[MAXN];
int mn[4 * MAXN], cnt[4 * MAXN], lz[4 * MAXN];
void build(int x, int l, int r) {
mn[x] = 1; cnt[x] = r - l + 1; lz[x] = 0; // vi tri chua toi: gia tri 1
if (l == r) return;
int m = (l + r) / 2;
build(2 * x, l, m);
build(2 * x + 1, m + 1, r);
}
void update(int x, int l, int r, int ql, int qr, int v) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { mn[x] += v; lz[x] += v; return; }
int m = (l + r) / 2;
update(2 * x, l, m, ql, qr, v);
update(2 * x + 1, m + 1, r, ql, qr, v);
int A = mn[2 * x], B = mn[2 * x + 1];
mn[x] = min(A, B) + lz[x]; // lz[x] cua nut x khong day xuong
cnt[x] = (A <= B ? cnt[2 * x] : 0) + (B <= A ? cnt[2 * x + 1] : 0);
}
// dem so doan so gia duoc [l, r] voi L <= l <= r <= R; pre[r] = so doan co r' <= r
long long sweep(int L, int R, vector<long long> &pre) {
build(1, L, R);
long long res = 0;
for (int r = L; r <= R; r++) {
int p1 = prv[r];
if (max(L, p1 + 1) <= r - 1) update(1, L, R, max(L, p1 + 1), r - 1, +1);
if (p1 >= L) update(1, L, R, max(L, prv[p1] + 1), p1, -1);
if (mn[1] == 0) res += cnt[1]; // so l co f(l) = 0
pre[r] = res;
}
return res;
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
map<int, int> last;
for (int i = 1; i <= n; i++) {
auto it = last.find(a[i]);
prv[i] = (it == last.end() ? 0 : it->second);
last[a[i]] = i;
}
vector<int> qL(q), qR(q);
bool allL1 = true;
for (int i = 0; i < q; i++) {
scanf("%d %d", &qL[i], &qR[i]);
if (qL[i] != 1) allL1 = false;
}
vector<long long> pre(n + 1, 0);
if (allL1) { // subtask 4: quet 1 lan, tra loi bang pre[R]
sweep(1, n, pre);
for (int i = 0; i < q; i++) printf("%lld\n", pre[qR[i]]);
} else { // con lai: quet rieng tung cau hoi (Cach 3)
for (int i = 0; i < q; i++) printf("%lld\n", sweep(qL[i], qR[i], pre));
}
return 0;
}import sys
def sweep(L, R, prv, pre):
# dem so doan so gia duoc [l, r] voi L <= l <= r <= R; pre[r] = so doan co r' <= r
n = R - L + 1
size = 1
while size < n:
size *= 2
INF = 1 << 30
mn = [INF] * (2 * size)
cnt = [0] * (2 * size)
lz = [0] * (2 * size)
for i in range(n):
mn[size + i] = 1; cnt[size + i] = 1 # vi tri chua toi: gia tri 1
for k in range(size - 1, 0, -1):
A = mn[2 * k]; B = mn[2 * k + 1]
mn[k] = A if A < B else B
cnt[k] = (cnt[2 * k] if A <= B else 0) + (cnt[2 * k + 1] if B <= A else 0)
def update(l, r, v): # cong v vao vi tri l..r (trong [L, R])
l += size - L; r += size - L + 1
l0 = l; r0 = r - 1
while l < r:
if l & 1:
mn[l] += v; lz[l] += v; l += 1
if r & 1:
r -= 1; mn[r] += v; lz[r] += v
l >>= 1; r >>= 1
for k in (l0 >> 1, r0 >> 1): # tinh lai cac to tien (lz khong day xuong)
while k:
A = mn[2 * k]; B = mn[2 * k + 1]
mn[k] = (A if A < B else B) + lz[k]
cnt[k] = (cnt[2 * k] if A <= B else 0) + (cnt[2 * k + 1] if B <= A else 0)
k >>= 1
res = 0
for r in range(L, R + 1):
p1 = prv[r]
lo = p1 + 1 if p1 + 1 > L else L
if lo <= r - 1:
update(lo, r - 1, 1)
if p1 >= L:
p2 = prv[p1]
update(p2 + 1 if p2 + 1 > L else L, p1, -1)
if mn[1] == 0:
res += cnt[1] # so l co f(l) = 0
pre[r] = res
return res
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
prv = [0] * (n + 1)
last = {}
for i in range(1, n + 1):
x = data[1 + i]
prv[i] = last.get(x, 0)
last[x] = i
qs = [(int(data[2 + n + 2 * i]), int(data[3 + n + 2 * i])) for i in range(q)]
pre = [0] * (n + 1)
if all(L == 1 for L, R in qs): # subtask 4: quet 1 lan, tra loi bang pre[R]
sweep(1, n, prv, pre)
out = [pre[R] for L, R in qs]
else: # con lai: quet rieng tung cau hoi (Cach 3)
out = [sweep(L, R, prv, pre) for L, R in qs]
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Cách 5Cộng dồn lịch sử trên segment tree – O((N + Q) log N) · 100%
Giờ tới nút thắt cuối: câu hỏi có $L$ tuỳ ý, $Q$ lớn. Ta vẫn quét $r$ một lần duy nhất trên cả dãy, nhưng đổi cách đếm. Với mỗi vị trí $l$, hãy tưởng tượng một "cuốn sổ" $c(l)$: mỗi khi quét xong một $r$ mà $f_r(l) = 0$, ta ghi thêm một vạch vào sổ của $l$. Như vậy sau khi quét tới $r = R$:
$$c_R(l) = \#\{r \le R : f_r(l) = 0\} = \#\{r : l \le r \le R,\ [l, r] \text{ so giá được}\}.$$
(Điều kiện $r \ge l$ tự động đúng, vì khi $r < l$ thì vị trí $l$ "chưa tới", mang giá trị $1 \ne 0$ — mẹo ở Nhận xét 3 phát huy tác dụng ở đây!) Do đó:
Mô phỏng: hàng thứ hai là $f_r(l)$, hàng thứ ba là cuốn sổ $c(l)$. Ô xanh là những vị trí vừa được ghi thêm vạch. Tới $r = R$, cộng các cuốn sổ trong $[L, R]$ là ra đáp án.
Làm sao "ghi vạch" cho mọi số 0 cùng lúc?
Mỗi bước $r$, ta phải tăng $c(l)$ cho tất cả $l$ có $f_r(l) = 0$ — có thể rất nhiều vị trí, không thể làm từng cái. Nhưng theo Nhận xét 4, các vị trí đó chính là các vị trí đạt min (khi min = 0). Vậy ta cần một segment tree, mỗi nút $x$ lưu:
mn[x],cnt[x]: min của $f$ trên đoạn và số vị trí đạt min (như Cách 3);hs[x]$= \sum c(l)$ trên đoạn của nút (tổng các cuốn sổ);- hai thẻ lazy:
lzA[x]= lượng cộng vào $f$ chưa đẩy xuống, vàlzT[x]= số lần "ghi vạch" chưa đẩy xuống, áp dụng cho các vị trí đạt min của nút.
"Ghi vạch" cho cả cây: nếu mn[1] == 0 thì hs[1] += cnt[1], lzT[1] += 1. Chỉ $O(1)$!
Khi đẩy thẻ từ nút $x$ xuống hai con, câu hỏi là: con nào chứa những vị trí đạt min của $x$? Đó là (các) con có min nhỏ nhất. Ta so sánh min của hai con trước khi cộng lzA (gọi là pm). Con nào có mn == pm thì nhận lzT lần ghi vạch (hs += cnt * lzT); sau đó cả hai con cùng nhận lzA. Vì sao đúng? Mọi phép cộng còn treo ở $x$ đều cộng đều cho cả đoạn của $x$, nên trong suốt thời gian thẻ còn treo, con nào "giữ min" thì vẫn giữ min — thứ tự cộng và ghi vạch xen kẽ nhau cũng không làm thay đổi việc con nào nhận vạch.
lzT cho cả hai con (không so min), con có min lớn hơn sẽ bị ghi vạch cho những vị trí $f \ne 0$. Bộ test bắt lỗi này gần như ở mọi test (xem bảng cuối bài). Một lỗi khác cũng hay gặp: khởi tạo các vị trí chưa tới bằng $0$ thay vì $1$ — khi đó các $l > r$ bị ghi vạch oan.Toàn bộ lời giải: đọc dữ liệu, tính prv bằng map, nhóm câu hỏi theo $R$; quét $r = 1 \dots N$: hai phép cộng đoạn, ghi vạch nếu min = 0, rồi trả lời các câu hỏi có $R = r$ bằng tổng hs trên $[L, r]$.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q;
int a[MAXN], prv[MAXN], qL[MAXN], headQ[MAXN], nxtQ[MAXN];
long long ans[MAXN];
// cay phan doan tren vi tri l: f(l) = so loai chi xuat hien 1 lan trong [l, r]
int mn[4 * MAXN], cnt[4 * MAXN], lzA[4 * MAXN], lzT[4 * MAXN];
long long hs[4 * MAXN]; // hs = tong so lan f(l) == 0 tinh den hien tai
void build(int x, int l, int r) {
mn[x] = 1; cnt[x] = r - l + 1; // vi tri chua toi: gia tri 1
if (l == r) return;
int m = (l + r) / 2;
build(2 * x, l, m);
build(2 * x + 1, m + 1, r);
}
// cong a vao doan cua nut x; t lan "ghi so" cho cac vi tri dat min, neu min cua x == pm
void apply(int x, int add, int t, int pm) {
if (t && mn[x] == pm) {
hs[x] += (long long)cnt[x] * t;
lzT[x] += t;
}
mn[x] += add;
lzA[x] += add;
}
void push(int x) {
if (lzA[x] == 0 && lzT[x] == 0) return;
int pm = min(mn[2 * x], mn[2 * x + 1]);
apply(2 * x, lzA[x], lzT[x], pm);
apply(2 * x + 1, lzA[x], lzT[x], pm);
lzA[x] = lzT[x] = 0;
}
void pull(int x) {
int L = 2 * x, R = 2 * x + 1;
mn[x] = min(mn[L], mn[R]);
cnt[x] = (mn[L] == mn[x] ? cnt[L] : 0) + (mn[R] == mn[x] ? cnt[R] : 0);
hs[x] = hs[L] + hs[R];
}
void update(int x, int l, int r, int ql, int qr, int v) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { apply(x, v, 0, 0); return; }
push(x);
int m = (l + r) / 2;
update(2 * x, l, m, ql, qr, v);
update(2 * x + 1, m + 1, r, ql, qr, v);
pull(x);
}
long long query(int x, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return hs[x];
push(x);
int m = (l + r) / 2;
return query(2 * x, l, m, ql, qr) + query(2 * x + 1, m + 1, r, ql, qr);
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
map<int, int> last; // vi tri xuat hien gan nhat cua moi loai
for (int i = 1; i <= n; i++) {
auto it = last.find(a[i]);
prv[i] = (it == last.end() ? 0 : it->second);
last[a[i]] = i;
}
for (int r = 1; r <= n; r++) headQ[r] = -1;
for (int i = 0; i < q; i++) {
int L, R;
scanf("%d %d", &L, &R);
qL[i] = L;
nxtQ[i] = headQ[R]; headQ[R] = i; // nhom cau hoi theo R
}
build(1, 1, n);
for (int r = 1; r <= n; r++) {
int p1 = prv[r];
if (p1 + 1 <= r - 1) update(1, 1, n, p1 + 1, r - 1, +1); // a[r] la loai moi
if (p1 > 0) update(1, 1, n, prv[p1] + 1, p1, -1); // a[p1] het "le loi"
if (mn[1] == 0) apply(1, 0, 1, 0); // ghi so cac l co f(l) = 0
for (int i = headQ[r]; i != -1; i = nxtQ[i]) ans[i] = query(1, 1, n, qL[i], r);
}
string out;
char buf[24];
for (int i = 0; i < q; i++) {
int len = sprintf(buf, "%lld\n", ans[i]);
out.append(buf, len);
}
fputs(out.c_str(), stdout);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = data[2:2 + n]
prv = [0] * (n + 1)
last = {}
for i in range(1, n + 1):
x = a[i - 1]
prv[i] = last.get(x, 0)
last[x] = i
headQ = [-1] * (n + 1)
nxtQ = [-1] * q
qL = [0] * q
pos = 2 + n
for i in range(q):
L = int(data[pos]); R = int(data[pos + 1]); pos += 2
qL[i] = L
nxtQ[i] = headQ[R]; headQ[R] = i # nhom cau hoi theo R
# cay phan doan lap (kieu tu duoi len), la thu l (1..n) o chi so size + l - 1
LOG = 1
while (1 << LOG) < n:
LOG += 1
size = 1 << LOG
INF = 1 << 30
mn = [INF] * (2 * size)
cnt = [0] * (2 * size)
hs = [0] * (2 * size)
lzA = [0] * (2 * size)
lzT = [0] * (2 * size)
for i in range(n):
mn[size + i] = 1; cnt[size + i] = 1 # vi tri chua toi: gia tri 1
for k in range(size - 1, 0, -1):
l = mn[2 * k]; r = mn[2 * k + 1]
if l < r: mn[k] = l; cnt[k] = cnt[2 * k]
elif r < l: mn[k] = r; cnt[k] = cnt[2 * k + 1]
else: mn[k] = l; cnt[k] = cnt[2 * k] + cnt[2 * k + 1]
def push(k):
A = lzA[k]; T = lzT[k]
if A == 0 and T == 0:
return
c = 2 * k; d = c + 1
m1 = mn[c]; m2 = mn[d]
if T:
if m1 <= m2:
hs[c] += cnt[c] * T; lzT[c] += T
if m2 <= m1:
hs[d] += cnt[d] * T; lzT[d] += T
if A:
mn[c] = m1 + A; lzA[c] += A
mn[d] = m2 + A; lzA[d] += A
lzA[k] = 0; lzT[k] = 0
def pull(k):
c = 2 * k
l = mn[c]; r = mn[c + 1]
if l < r: mn[k] = l; cnt[k] = cnt[c]
elif r < l: mn[k] = r; cnt[k] = cnt[c + 1]
else: mn[k] = l; cnt[k] = cnt[c] + cnt[c + 1]
hs[k] = hs[c] + hs[c + 1]
def update(l, r, v): # cong v vao [l, r] (1-indexed)
l += size - 1; r += size # nua mo [l, r)
for i in range(LOG, 0, -1):
if ((l >> i) << i) != l: push(l >> i)
if ((r >> i) << i) != r: push((r - 1) >> i)
l2 = l; r2 = r
while l2 < r2:
if l2 & 1:
mn[l2] += v; lzA[l2] += v; l2 += 1
if r2 & 1:
r2 -= 1; mn[r2] += v; lzA[r2] += v
l2 >>= 1; r2 >>= 1
for i in range(1, LOG + 1):
if ((l >> i) << i) != l: pull(l >> i)
if ((r >> i) << i) != r: pull((r - 1) >> i)
def query(l, r): # tong hs tren [l, r]
l += size - 1; r += size
for i in range(LOG, 0, -1):
if ((l >> i) << i) != l: push(l >> i)
if ((r >> i) << i) != r: push((r - 1) >> i)
s = 0
while l < r:
if l & 1:
s += hs[l]; l += 1
if r & 1:
r -= 1; s += hs[r]
l >>= 1; r >>= 1
return s
ans = [0] * q
for r in range(1, n + 1):
p1 = prv[r]
if p1 + 1 <= r - 1:
update(p1 + 1, r - 1, 1) # a[r] la loai moi
if p1 > 0:
update(prv[p1] + 1, p1, -1) # a[p1] het "le loi"
if mn[1] == 0: # ghi so cac l co f(l) = 0
hs[1] += cnt[1]; lzT[1] += 1
i = headQ[r]
while i != -1:
ans[i] = query(qL[i], r)
i = nxtQ[i]
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Các bạn chạy tay từng dòng để thấy thẻ lzT được đẩy xuống thế nào (dữ liệu nhỏ: $N \le 6$, $Q \le 3$; hàng f thật và c thật là giá trị thật của từng vị trí, tính ra từ cây kể cả các thẻ còn treo):
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – vét cạn từng câu hỏi | Đúng | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – bảng O(N²) | Đúng | Đúng | TLE | TLE | TLE | 30 |
| Cách 3 – quét r + đếm min, làm riêng từng câu | Đúng | TLE | Đúng | TLE | TLE | 30 |
| Cách 4 – L = 1 dùng tổng tiền tố, còn lại như Cách 3 | Đúng | TLE | Đúng | Đúng | TLE | 50 |
| Cách 5 – cộng dồn lịch sử (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: đáp án / tổng lịch sử kiểu int | Đúng | Đúng | 3/7 | 4/7 | 3/9 | 60 |
| Sai: vị trí chưa tới khởi tạo bằng 0 | 0/7 | 0/7 | 0/7 | 0/7 | 0/9 | 0 |
| Sai: đẩy thẻ ghi vạch cho cả hai con | 1/7 | 0/7 | 0/7 | 0/7 | 0/9 | 1,4 |
Sai: trả lời bằng pre[R] - pre[L-1] | 1/7 | 0/7 | 1/7 | Đúng | 0/9 | 24,3 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 37 test (subtask 1: 7 test, subtask 2: 7 test, subtask 3: 7 test, subtask 4: 7 test, subtask 5: 9 test), chấm kiểu "đúng test nào được điểm test đó". Lời giải chuẩn chạy tối đa khoảng 0,45 giây. Mọi test của subtask 2 có $Q = 50\,000$ để chặn việc quét riêng từng câu; mọi test subtask 4, 5 có $Q = 2 \cdot 10^5$; nhiều test chỉ có 2–3 loại trái cây nên đáp án lên tới khoảng $2 \cdot 10^{10}$, ai dùng int sẽ mất điểm. Hai lỗi "khởi tạo bằng 0" và "đẩy thẻ cho cả hai con" gần như mất trắng — chi tiết nhỏ nhưng là sống còn với bài này. Bản Python của lời giải chuẩn nên nộp bằng PyPy 3.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- 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