Chuyến ghe (Đề tự luyện HSG Tin quốc gia – Bài 4)
Đề bài
Chuyến ghe. Vựa của thầy Sơn có $N$ sọt trái cây xếp thành hàng, sọt $i$ chứa loại $a_i$. Có $Q$ đơn hàng độc lập $(l, r, k)$: phải chở hết các sọt $l..r$ theo đúng thứ tự, mỗi chuyến ghe chở một đoạn liên tiếp các sọt và đoạn đó có tối đa $k$ loại khác nhau. Với mỗi đơn, in số chuyến ít nhất.
Dữ liệu vào: dòng 1 gồm $N, Q$ $(1 \le N, Q \le 5\cdot 10^4)$; dòng 2 gồm $a_1..a_N$ $(1 \le a_i \le N)$; $Q$ dòng sau mỗi dòng gồm $l, r, k$ $(1 \le l \le r \le N,\ 1 \le k \le N)$.
Kết quả: $Q$ dòng, mỗi dòng là số chuyến ít nhất của đơn tương ứng.
- Subtask 1 (10%): $N, Q \le 1000$.
- Subtask 2 (15%): mọi đơn có cùng giá trị $k$.
- Subtask 3 (20%): $k \le 20$.
- Subtask 4 (25%): $k \ge 500$.
- Subtask 5 (30%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.
9 4
3 3 3 5 5 2 1 4 1
1 9 2
2 6 1
4 9 3
1 9 53
3
2
1$(1,9,2)$: 3 3 3 | 5 5 2 | 1 4 1. $(2,6,1)$: 3 3 | 5 5 | 2. $(4,9,3)$: 5 2 | 1 4 1. $(1,9,5)$: cả dãy chỉ có 5 loại.
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 Chuyến gheLời mở đầu
Đây là bài cuối, bài "phân loại" của đề. Đọc đề thì thấy rất hiền: chia đoạn $[l, r]$ thành ít đoạn nhất sao cho mỗi đoạn có không quá $k$ giá trị khác nhau. Cái khó nằm ở chỗ mỗi đơn hàng có một $k$ riêng: không có cấu trúc nào dựng một lần mà dùng được cho mọi $k$. Mình sẽ đi qua 5 cách, mỗi cách thêm một nhận xét, và cách cuối cùng ghép hai ý tưởng "ngược chiều nhau" bằng chia căn theo $k$.
Nhận xét 1: tham lam là tối ưu
Nếu một đoạn có không quá $k$ loại thì mọi đoạn con của nó cũng vậy. Từ đó: mỗi chuyến cứ bốc nhiều sọt nhất có thể là tối ưu. Thật vậy, giả sử một phương án tối ưu có chuyến đầu dừng sớm hơn tham lam; ta kéo dài chuyến đầu tới chỗ tham lam dừng, các chuyến sau chỉ bị "cắt bớt đầu" nên vẫn hợp lệ (đoạn con), số chuyến không tăng. Lặp lại lập luận cho từng chuyến.
Gọi $nx_k(i)$ là vị trí đầu tiên không bốc được nếu chuyến bắt đầu tại sọt $i$ (tức là sọt chứa loại thứ $k+1$ kể từ $i$; bằng $N+1$ nếu không có). Khi đó đáp án của đơn $(l, r, k)$ là số điểm trên dãy nhảy $$l \to nx_k(l) \to nx_k(nx_k(l)) \to \cdots$$ còn $\le r$. Chú ý: tham lam trên $[l, r]$ chính là tham lam trên cả dãy rồi cắt ở $r$ (chuyến cuối bị cắt ngắn).
Hình 1. Dãy minh họa 1 2 1 3 3 2 4 1 với $k = 2$: $1 \to 4 \to 7 \to 9$. Có 3 điểm $\le 8$ nên đáp án là 3.
Nhận xét 2: chuyến đầy chở ít nhất k sọt
Mọi chuyến (trừ chuyến cuối) đều chứa đúng $k$ loại (vì nó chỉ dừng khi gặp loại thứ $k+1$), nên chở ít nhất $k$ sọt. Suy ra số chuyến của một đơn không vượt quá $\lceil (r - l + 1)/k \rceil$. Khi $k$ lớn, số bước nhảy rất ít; khi $k$ nhỏ, số bước nhảy có thể lên tới $N$. Hai chế độ này cần hai kỹ thuật khác nhau, và đó chính là chìa khoá của bài.
Cách 1Mô phỏng trực tiếp – O(N·Q) · 10%
Với mỗi đơn, đi từ $l$ tới $r$, giữ mảng đếm cnt và số loại $d$ của chuyến hiện tại. Gặp một loại mới khi ghe đã đủ $k$ loại thì mở chuyến mới (xoá cnt của chuyến cũ bằng cách duyệt lại đoạn đó, để tổng chi phí vẫn là $O(r - l + 1)$). Với $N, Q \le 1000$ chỉ khoảng $10^6$ phép tính, nhưng với $N = Q = 5\cdot 10^4$ và các đơn dài thì lên tới $2{,}5 \cdot 10^9$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> a(n + 1), cnt(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (q--) {
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
int trips = 1, d = 0, start = l; // chuyen hien tai bat dau tai start, co d loai
for (int i = l; i <= r; i++) {
if (cnt[a[i]] == 0 && d == k) { // loai moi nhung ghe da du k loai -> chuyen moi
for (int j = start; j < i; j++) cnt[a[j]] = 0;
trips++; d = 0; start = i;
}
if (cnt[a[i]]++ == 0) d++;
}
for (int j = start; j <= r; j++) cnt[a[j]] = 0;
printf("%d\n", trips);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
cnt = [0] * (n + 1)
out = []; pos = 2 + n
for _ in range(q):
l = int(data[pos]); r = int(data[pos + 1]); k = int(data[pos + 2]); pos += 3
trips = 1; d = 0; start = l # chuyen hien tai bat dau tai start, co d loai
for i in range(l, r + 1):
v = a[i]
if cnt[v] == 0 and d == k: # loai moi nhung ghe da du k loai -> chuyen moi
for j in range(start, i):
cnt[a[j]] = 0
trips += 1; d = 0; start = i
if cnt[v] == 0:
d += 1
cnt[v] += 1
for j in range(start, r + 1):
cnt[a[j]] = 0
out.append(trips)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Cách 2Một giá trị k: hai con trỏ + nhảy theo khối – O(N + Q√N) · 25%
Tính $nx_k(i)$ cho mọi $i$ bằng hai con trỏ. Khi $i$ tăng, $nx_k(i)$ không giảm (bắt đầu muộn hơn thì kết thúc không sớm hơn). Ta giữ con trỏ $j$ = điểm dừng hiện tại cùng mảng đếm: tăng $j$ chừng nào sọt $j$ thuộc loại đã có hoặc ghe còn chỗ ($d < k$); ghi $nx_k(i) = j$; rồi bỏ sọt $i$ ra. Mỗi con trỏ chỉ đi tới, tổng $O(N)$.
Trả lời nhanh số bước nhảy. Nhảy từng bước thì một đơn có thể tốn $O(N)$ bước (khi $k = 1$). Ta dùng kỹ thuật nhảy theo khối (giống bài "lỗ hổng" kinh điển): chia vị trí thành các khối độ dài $B \approx \sqrt N$, với mỗi $i$ lưu
far[i]: điểm đầu tiên ra khỏi khối của $i$ khi nhảy liên tiếp từ $i$;num[i]: số bước để tới đó.
Tính từ phải sang trái: nếu $nx(i)$ đã ở khối khác thì far[i] = nx(i), num[i] = 1; ngược lại far[i] = far[nx(i)], num[i] = num[nx(i)] + 1. Khi trả lời đơn $(l, r)$: nhảy theo far chừng nào chưa vượt $r$ (mỗi lần qua ít nhất một khối, tối đa $N/B$ lần), rồi nhảy từng bước trong khối cuối (tối đa $B$ bước). Mỗi đơn tốn $O(\sqrt N)$.
Code dưới đây dùng cách này khi mọi đơn cùng $k$, còn lại quay về Cách 1, nên đạt $10 + 15 = 25\%$.
#include <bits/stdc++.h>
using namespace std;
const int B = 224;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> a(n + 1), cnt(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<int> L(q), R(q), K(q);
bool same = true;
for (int t = 0; t < q; t++) {
scanf("%d %d %d", &L[t], &R[t], &K[t]);
if (K[t] != K[0]) same = false;
}
if (!same) { // khong cung k: quay ve Cach 1
for (int t = 0; t < q; t++) {
int trips = 1, d = 0, start = L[t];
for (int i = L[t]; i <= R[t]; i++) {
if (cnt[a[i]] == 0 && d == K[t]) {
for (int j = start; j < i; j++) cnt[a[j]] = 0;
trips++; d = 0; start = i;
}
if (cnt[a[i]]++ == 0) d++;
}
for (int j = start; j <= R[t]; j++) cnt[a[j]] = 0;
printf("%d\n", trips);
}
return 0;
}
int k = K[0];
vector<int> nx(n + 2), far_(n + 2), num(n + 2);
int j = 1, d = 0; // hai con tro: nx[i] = diem bat dau chuyen sau
for (int i = 1; i <= n; i++) {
while (j <= n && (cnt[a[j]] > 0 || d < k)) { if (cnt[a[j]]++ == 0) d++; j++; }
nx[i] = j;
if (--cnt[a[i]] == 0) d--;
}
for (int i = n; i >= 1; i--) { // far_[i]: diem dau tien ra khoi khoi cua i
if (nx[i] > n || nx[i] / B != i / B) { far_[i] = nx[i]; num[i] = 1; }
else { far_[i] = far_[nx[i]]; num[i] = num[nx[i]] + 1; }
}
for (int t = 0; t < q; t++) {
int cur = L[t], c = 0;
while (far_[cur] <= R[t]) { c += num[cur]; cur = far_[cur]; }
while (cur <= R[t]) { c++; cur = nx[cur]; }
printf("%d\n", c);
}
return 0;
}import sys
def brute(n, a, L, R, K): # Cach 1
cnt = [0] * (n + 1); out = []
for t in range(len(L)):
l, r, k = L[t], R[t], K[t]
trips = 1; d = 0; start = l
for i in range(l, r + 1):
v = a[i]
if cnt[v] == 0 and d == k:
for j in range(start, i):
cnt[a[j]] = 0
trips += 1; d = 0; start = i
if cnt[v] == 0:
d += 1
cnt[v] += 1
for j in range(start, r + 1):
cnt[a[j]] = 0
out.append(trips)
return out
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1]); B = 224
a = [0] + [int(x) for x in data[2:2 + n]]
L = [int(x) for x in data[2 + n::3]]; R = [int(x) for x in data[3 + n::3]]; K = [int(x) for x in data[4 + n::3]]
if min(K) != max(K): # khong cung k: quay ve Cach 1
sys.stdout.write('\n'.join(map(str, brute(n, a, L, R, K))) + '\n'); return
k = K[0]; cnt = [0] * (n + 1)
nx = [0] * (n + 2); far_ = [0] * (n + 2); num = [0] * (n + 2)
j = 1; d = 0 # hai con tro: nx[i] = diem bat dau chuyen sau
for i in range(1, n + 1):
while j <= n:
v = a[j]
if cnt[v] == 0:
if d == k: break
d += 1
cnt[v] += 1; j += 1
nx[i] = j
cnt[a[i]] -= 1
if cnt[a[i]] == 0: d -= 1
for i in range(n, 0, -1): # far_[i]: diem dau tien ra khoi khoi cua i
y = nx[i]
if y > n or y // B != i // B:
far_[i] = y; num[i] = 1
else:
far_[i] = far_[y]; num[i] = num[y] + 1
out = []
for t in range(q):
cur = L[t]; r = R[t]; c = 0
while far_[cur] <= r:
c += num[cur]; cur = far_[cur]
while cur <= r:
c += 1; cur = nx[cur]
out.append(c)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Mô phỏng: nhập dãy, $k$, kích thước khối $B$ và một đơn $(l, r)$. Phần đầu là hai con trỏ tính $nx$, phần giữa dựng far/num, phần cuối là trả lời đơn hàng.
Cách 3Gom đơn hàng theo k – O(D·N + Q√N) · 45%
Cách 2 chỉ phụ thuộc $k$. Vậy ta đọc hết các đơn (xử lý offline), gom các đơn cùng $k$ lại, và với mỗi giá trị $k$ khác nhau chạy lại hai con trỏ + dựng far/num trong $O(N)$ rồi trả lời các đơn của nhóm đó. Nếu có $D$ giá trị $k$ khác nhau thì tổng là $O(D \cdot N + Q\sqrt N)$.
Ở subtask 3 ($k \le 20$) có $D \le 20$, chạy rất nhanh. Code này đúng cho mọi input và qua được subtask 1, 2, 3 (tổng $45\%$); nhưng ở subtask 4, 5 có hàng chục nghìn giá trị $k$ khác nhau thì $D \cdot N \approx 10^9$ trở lên, quá thời gian.
#include <bits/stdc++.h>
using namespace std;
const int B = 224;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> a(n + 1), cnt(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
vector<int> L(q), R(q), K(q), ans(q);
vector<vector<int>> byK(n + 1); // gom don hang theo k
for (int t = 0; t < q; t++) {
scanf("%d %d %d", &L[t], &R[t], &K[t]);
byK[K[t]].push_back(t);
}
vector<int> nx(n + 2), far_(n + 2), num(n + 2);
for (int k = 1; k <= n; k++) {
if (byK[k].empty()) continue;
int j = 1, d = 0;
for (int i = 1; i <= n; i++) {
while (j <= n && (cnt[a[j]] > 0 || d < k)) { if (cnt[a[j]]++ == 0) d++; j++; }
nx[i] = j;
if (--cnt[a[i]] == 0) d--;
}
for (int i = n; i >= 1; i--) {
if (nx[i] > n || nx[i] / B != i / B) { far_[i] = nx[i]; num[i] = 1; }
else { far_[i] = far_[nx[i]]; num[i] = num[nx[i]] + 1; }
}
for (int t : byK[k]) {
int cur = L[t], c = 0;
while (far_[cur] <= R[t]) { c += num[cur]; cur = far_[cur]; }
while (cur <= R[t]) { c++; cur = nx[cur]; }
ans[t] = c;
}
}
for (int t = 0; t < q; t++) printf("%d\n", ans[t]);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1]); B = 224
a = [0] + [int(x) for x in data[2:2 + n]]
L = [int(x) for x in data[2 + n::3]]; R = [int(x) for x in data[3 + n::3]]; K = [int(x) for x in data[4 + n::3]]
byK = {} # gom don hang theo k
for t in range(q):
byK.setdefault(K[t], []).append(t)
ans = [0] * q; cnt = [0] * (n + 1)
nx = [0] * (n + 2); far_ = [0] * (n + 2); num = [0] * (n + 2)
for k in sorted(byK):
j = 1; d = 0
for i in range(1, n + 1):
while j <= n:
v = a[j]
if cnt[v] == 0:
if d == k: break
d += 1
cnt[v] += 1; j += 1
nx[i] = j
cnt[a[i]] -= 1
if cnt[a[i]] == 0: d -= 1
for i in range(n, 0, -1):
y = nx[i]
if y > n or y // B != i // B:
far_[i] = y; num[i] = 1
else:
far_[i] = far_[y]; num[i] = num[y] + 1
for t in byK[k]:
cur = L[t]; r = R[t]; c = 0
while far_[cur] <= r:
c += num[cur]; cur = far_[cur]
while cur <= r:
c += 1; cur = nx[cur]
ans[t] = c
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Cách 4k lớn: quét offline + Fenwick – O((N + số bước nhảy)·log N) · 35%
Khi $k \ge 500$, theo Nhận xét 2 mỗi đơn chỉ có không quá $N/500 + 1 \le 101$ chuyến. Nếu tính được $nx_k(p)$ cho một cặp $(p, k)$ bất kỳ trong $O(\log N)$ thì ta nhảy từng bước cũng đủ nhanh. Vấn đề: $nx_k(p)$ là vị trí của "loại mới thứ $k+1$ kể từ $p$", làm sao tính nhanh khi $k$ thay đổi liên tục?
Nhận xét 3: đổi bài toán thành "phần tử nhỏ thứ m"
Gọi $prev_j$ là vị trí xuất hiện trước đó của loại $a_j$ ($0$ nếu $j$ là lần đầu). Kể từ $p$, sọt $j \ge p$ mang một loại mới khi và chỉ khi $prev_j < p$. Vậy $nx_k(p)$ là phần tử thứ $k+1$ (theo thứ tự tăng) của tập $\{\, j \ge p : prev_j < p \,\}$.
Xét tập $S_p = \{\, j : prev_j < p \,\}$ (bỏ điều kiện $j \ge p$). Mọi $j < p$ đều thuộc $S_p$ vì $prev_j < j < p$, tức là $S_p$ chứa đúng $p - 1$ phần tử nhỏ hơn $p$. Do đó:
Và khi $p$ tăng lên $1$, tập $S_p$ chỉ thêm đúng một phần tử: sọt $j$ có $prev_j = p$, tức $j = nxtOcc[p]$ (lần xuất hiện kế tiếp của loại $a_p$). Ban đầu $S_1$ là tập các vị trí xuất hiện lần đầu.
Nhận xét 4: các bước nhảy chỉ đi về phía phải
Một đơn đang đứng ở $p$ cần phiên bản $S_p$, nhảy tới $y = nx_k(p) > p$ thì cần phiên bản $S_y$ "muộn hơn". Vì $S_p$ chỉ lớn dần theo $p$, ta quét $p$ từ $1$ tới $N$ đúng một lần, giữ $S_p$ trên một cây Fenwick (BIT) đánh dấu các vị trí. Mỗi đơn được "xếp hàng chờ" tại bến nó đang đứng (danh sách liên kết head[p], link[t]). Khi quét tới $p$, mọi đơn đang chờ ở $p$: đếm thêm một chuyến, tìm $y$ bằng thao tác "phần tử nhỏ thứ $m$" trên BIT (nhảy nhị phân, $O(\log N)$), và nếu $y \le r$ thì chuyển đơn sang hàng chờ ở bến $y$ – quét sẽ tới đó sau.
Hình 2. Một lượt quét duy nhất phục vụ mọi bước nhảy của mọi đơn, vì bước nhảy luôn đi về phía phải, cùng chiều với chiều quét.
Độ phức tạp: $O\big((N + J)\log N\big)$ với $J$ là tổng số bước nhảy. Ở subtask 4, $J \le Q \cdot (N/500 + 1) \approx 5\cdot 10^6$: rất nhanh. Nhưng nếu $k$ nhỏ (ví dụ $k = 1$) thì $J$ có thể tới $N \cdot Q = 2{,}5 \cdot 10^9$. Code dưới đây áp dụng cho mọi đơn nên chỉ đạt subtask 1 và 4 ($10 + 25 = 35\%$).
#include <bits/stdc++.h>
using namespace std;
int n, q, LOG;
vector<int> bit;
void add(int i) { for (; i <= n; i += i & -i) bit[i]++; }
int kth(int m) { // phan tu nho thu m trong BIT
int pos = 0;
for (int pw = LOG; pw > 0; pw >>= 1)
if (pos + pw <= n && bit[pos + pw] < m) { pos += pw; m -= bit[pos]; }
return pos + 1;
}
int main() {
scanf("%d %d", &n, &q);
vector<int> a(n + 1), nxtOcc(n + 2, n + 1), last(n + 1, n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = n; i >= 1; i--) { nxtOcc[i] = last[a[i]]; last[a[i]] = i; }
vector<int> L(q), R(q), K(q), ans(q, 0), head(n + 2, -1), link(q, -1);
for (int t = 0; t < q; t++) {
scanf("%d %d %d", &L[t], &R[t], &K[t]);
link[t] = head[L[t]]; head[L[t]] = t;
}
bit.assign(n + 1, 0);
LOG = 1; while (LOG * 2 <= n) LOG *= 2;
int tot = 0;
vector<char> seen(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!seen[a[i]]) { seen[a[i]] = 1; add(i); tot++; }
for (int p = 1; p <= n; p++) {
if (p > 1 && nxtOcc[p - 1] <= n) { add(nxtOcc[p - 1]); tot++; }
for (int t = head[p]; t != -1; ) {
int nt = link[t];
ans[t]++;
int m = p + K[t];
int y = (m <= tot) ? kth(m) : n + 1;
if (y <= R[t]) { link[t] = head[y]; head[y] = t; }
t = nt;
}
}
for (int t = 0; t < q; t++) printf("%d\n", ans[t]);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
L = [int(x) for x in data[2 + n::3]]; R = [int(x) for x in data[3 + n::3]]; K = [int(x) for x in data[4 + n::3]]
nxtOcc = [n + 1] * (n + 2); last = [n + 1] * (n + 1)
for i in range(n, 0, -1):
nxtOcc[i] = last[a[i]]; last[a[i]] = i
ans = [0] * q; head = [-1] * (n + 2); link = [-1] * q
for t in range(q):
link[t] = head[L[t]]; head[L[t]] = t
bit = [0] * (n + 1); LOG = 1
while LOG * 2 <= n: LOG *= 2
tot = 0; seen = [False] * (n + 1)
for i in range(1, n + 1):
if not seen[a[i]]:
seen[a[i]] = True; tot += 1; j = i
while j <= n:
bit[j] += 1; j += j & -j
for p in range(1, n + 1):
if p > 1 and nxtOcc[p - 1] <= n:
j = nxtOcc[p - 1]; tot += 1
while j <= n:
bit[j] += 1; j += j & -j
t = head[p]
while t != -1:
nt = link[t]
ans[t] += 1
m = p + K[t]
if m <= tot: # phan tu nho thu m trong BIT
ps = 0; pw = LOG
while pw:
if ps + pw <= n and bit[ps + pw] < m:
ps += pw; m -= bit[ps]
pw >>= 1
y = ps + 1
if y <= R[t]:
link[t] = head[y]; head[y] = t
t = nt
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()Mô phỏng lượt quét: mỗi bước là một giá trị $p$; hàng "S" cho biết vị trí nào đang nằm trong $S_p$, bảng dưới cho biết mỗi đơn đang chờ ở bến nào.
Chạy tay từng dòng của code C++ Cách 4 (với dữ liệu nhỏ, mọi đơn đều đi theo lượt quét):
Cách 5Chia căn theo k – O(T·N + Q·(N/T)·log N) · 100%
Hai cách vừa rồi mạnh ở hai đầu ngược nhau:
- Cách 3 tốn $O(N)$ cho mỗi giá trị $k$ khác nhau, không quan tâm số bước nhảy: tốt khi $k$ nhỏ (vì có ít giá trị nhỏ).
- Cách 4 tốn $O(\log N)$ cho mỗi bước nhảy, mà số bước nhảy $\le N/k + 1$: tốt khi $k$ lớn.
Chọn ngưỡng $T$: đơn có $k \le T$ đi Cách 3 (có tối đa $T$ giá trị $k$ khác nhau, tổng $O(T \cdot N)$); đơn có $k > T$ đi Cách 4 (mỗi đơn tối đa $N/T + 1$ bước, tổng $O(Q \cdot \frac{N}{T} \log N)$). Cân bằng hai vế cho $T \approx \sqrt{Q \log N}$; tính thêm hằng số thực tế (hai con trỏ chạy nhanh hơn thao tác BIT), mình chọn $T = 300$. Khi đó cả hai phần đều chỉ cỡ $1{,}5 \cdot 10^7$ – $10^8$ phép tính đơn giản.
- Đọc hết đơn hàng. Đơn có $k \le T$ gom vào nhóm theo $k$; đơn có $k > T$ xếp hàng chờ ở bến $l$.
- Quét $p = 1..N$, BIT giữ $S_p = \{j : prev_j < p\}$; mỗi đơn chờ ở $p$: tăng đếm, $y$ = phần tử nhỏ thứ $p + k$, nếu $y \le r$ thì chuyển sang chờ ở $y$.
- Với mỗi $k \le T$ có đơn: hai con trỏ tính $nx$, dựng
far/numtheo khối $B \approx \sqrt N$, trả lời các đơn của nhóm.
#include <bits/stdc++.h>
using namespace std;
const int T = 300, B = 224; // nguong cua k va kich thuoc khoi
int n, q, LOG;
vector<int> a, nxtOcc, bit;
void add(int i) { for (; i <= n; i += i & -i) bit[i]++; }
// phan tu nho thu m trong tap dang luu tren BIT (n+1 neu tap co it hon m phan tu)
int kth(int m) {
int pos = 0;
for (int pw = LOG; pw > 0; pw >>= 1)
if (pos + pw <= n && bit[pos + pw] < m) { pos += pw; m -= bit[pos]; }
return pos + 1;
}
int main() {
scanf("%d %d", &n, &q);
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
nxtOcc.assign(n + 2, n + 1);
vector<int> last(n + 1, n + 1);
for (int i = n; i >= 1; i--) { nxtOcc[i] = last[a[i]]; last[a[i]] = i; }
vector<int> L(q), R(q), K(q), ans(q, 0), head(n + 2, -1), link(q, -1);
vector<vector<int>> byK(T + 1);
for (int t = 0; t < q; t++) {
scanf("%d %d %d", &L[t], &R[t], &K[t]);
if (K[t] <= T) byK[K[t]].push_back(t);
else { link[t] = head[L[t]]; head[L[t]] = t; } // cho tai ben L[t]
}
// Phan 1 (k > T): quet p tang dan, BIT luu tap S = { j : lan xuat hien truoc cua a[j] < p }
bit.assign(n + 1, 0);
LOG = 1; while (LOG * 2 <= n) LOG *= 2;
int tot = 0;
vector<char> seen(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!seen[a[i]]) { seen[a[i]] = 1; add(i); tot++; }
for (int p = 1; p <= n; p++) {
if (p > 1 && nxtOcc[p - 1] <= n) { add(nxtOcc[p - 1]); tot++; }
for (int t = head[p]; t != -1; ) {
int nt = link[t];
ans[t]++; // mot chuyen bat dau tai p
int m = p + K[t];
int y = (m <= tot) ? kth(m) : n + 1; // chuyen sau bat dau tai y
if (y <= R[t]) { link[t] = head[y]; head[y] = t; }
t = nt;
}
}
// Phan 2 (k <= T): voi moi k, hai con tro tinh nx[] roi nhay theo khoi
vector<int> nx(n + 2), far_(n + 2), num(n + 2), cnt(n + 1, 0);
for (int k = 1; k <= T; k++) {
if (byK[k].empty()) continue;
int j = 1, d = 0;
for (int i = 1; i <= n; i++) {
while (j <= n && (cnt[a[j]] > 0 || d < k)) { if (cnt[a[j]]++ == 0) d++; j++; }
nx[i] = j;
if (--cnt[a[i]] == 0) d--;
}
for (int i = n; i >= 1; i--) {
if (nx[i] > n || nx[i] / B != i / B) { far_[i] = nx[i]; num[i] = 1; }
else { far_[i] = far_[nx[i]]; num[i] = num[nx[i]] + 1; }
}
for (int t : byK[k]) {
int cur = L[t], c = 0;
while (far_[cur] <= R[t]) { c += num[cur]; cur = far_[cur]; }
while (cur <= R[t]) { c++; cur = nx[cur]; }
ans[t] = c;
}
}
string out;
for (int t = 0; t < q; t++) { out += to_string(ans[t]); out += '\n'; }
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])
T = 50; B = 224 # nguong cua k (Python: dat nho hon C++ vi vong lap hai con tro rat cham) va kich thuoc khoi
a = [0] * (n + 1)
for i in range(n):
a[i + 1] = int(data[2 + i])
nxtOcc = [n + 1] * (n + 2); last = [n + 1] * (n + 1)
for i in range(n, 0, -1):
nxtOcc[i] = last[a[i]]; last[a[i]] = i
L = [0] * q; R = [0] * q; K = [0] * q; ans = [0] * q
head = [-1] * (n + 2); link = [-1] * q
byK = [[] for _ in range(T + 1)]
pos = 2 + n
for t in range(q):
l = int(data[pos]); r = int(data[pos + 1]); k = int(data[pos + 2]); pos += 3
L[t] = l; R[t] = r; K[t] = k
if k <= T:
byK[k].append(t)
else:
link[t] = head[l]; head[l] = t # cho tai ben l
# Phan 1 (k > T): quet p tang dan, BIT luu S = { j : lan xuat hien truoc cua a[j] < p }
bit = [0] * (n + 1)
LOG = 1
while LOG * 2 <= n:
LOG *= 2
tot = 0
seen = [False] * (n + 1)
for i in range(1, n + 1):
if not seen[a[i]]:
seen[a[i]] = True; tot += 1
j = i
while j <= n:
bit[j] += 1; j += j & -j
for p in range(1, n + 1):
if p > 1 and nxtOcc[p - 1] <= n:
j = nxtOcc[p - 1]; tot += 1
while j <= n:
bit[j] += 1; j += j & -j
t = head[p]
while t != -1:
nt = link[t]
ans[t] += 1 # mot chuyen bat dau tai p
m = p + K[t]
if m <= tot: # tim phan tu nho thu m cua S
ps = 0; pw = LOG
while pw:
if ps + pw <= n and bit[ps + pw] < m:
ps += pw; m -= bit[ps]
pw >>= 1
y = ps + 1
if y <= R[t]:
link[t] = head[y]; head[y] = t
t = nt
# Phan 2 (k <= T): voi moi k, hai con tro tinh nx[] roi nhay theo khoi
nx = [0] * (n + 2); far_ = [0] * (n + 2); num = [0] * (n + 2); cnt = [0] * (n + 1)
for k in range(1, T + 1):
if not byK[k]:
continue
j = 1; d = 0
for i in range(1, n + 1):
while j <= n:
v = a[j]
if cnt[v] == 0:
if d == k:
break
d += 1
cnt[v] += 1; j += 1
nx[i] = j
v = a[i]; cnt[v] -= 1
if cnt[v] == 0:
d -= 1
for i in range(n, 0, -1):
y = nx[i]
if y > n or y // B != i // B:
far_[i] = y; num[i] = 1
else:
far_[i] = far_[y]; num[i] = num[y] + 1
for t in byK[k]:
cur = L[t]; r = R[t]; c = 0
while far_[cur] <= r:
c += num[cur]; cur = far_[cur]
while cur <= r:
c += 1; cur = nx[cur]
ans[t] = c
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()- Quên thêm
nxtOcc[p-1]vào BIT khi $p$ tăng (dùng mãi tập lần-đầu-xuất-hiện của cả dãy): sai ngay khi dãy có loại lặp lại. - Lấy phần tử nhỏ thứ $p + k - 1$ thay vì $p + k$: đó là sọt cuối cùng của chuyến chứ không phải điểm bắt đầu chuyến sau.
- Dùng dãy nhảy tham lam xuất phát từ sọt $1$ rồi đếm số điểm cắt rơi vào $[l, r]$: dãy nhảy từ $l$ nói chung khác dãy nhảy từ $1$.
Khung chạy tay dưới đây là của chính code C++ Cách 5. Vì dữ liệu nhỏ có $k \le T = 300$ nên mọi đơn đi theo nhánh "hai con trỏ + nhảy khối" (với $N$ nhỏ, cả dãy nằm trong một khối nên em sẽ thấy nhảy từng bước); nhánh quét đã được chạy tay ở Cách 4 phía trên.
Bộ test chấm "bắt" những lỗi nào?
Bộ test có 41 test: subtask 1 có 8 test (có $N = 1$), các subtask 2–5 có lần lượt 8, 8, 8, 9 test, tất cả đều $N = Q = 5\cdot 10^4$ và phần lớn đơn hàng là đoạn rất dài. Dãy $a$ đủ kiểu: hoán vị (mỗi chuyến đúng $k$ sọt – nhiều bước nhảy nhất), ngẫu nhiên với nhiều/ít loại, lặp chu kỳ có nhiễu, các khúc cùng loại, xen kẽ đoạn nhiều loại và đoạn ít loại. Subtask 2, 3 dùng $k \le 10$ là chủ yếu để Cách 4 phải nhảy hàng trăm triệu bước; subtask 4, 5 có hàng chục nghìn giá trị $k$ khác nhau để Cách 3 không gom được; subtask 5 còn có nhiều đơn $k$ sát ngưỡng $300$ ở cả hai phía.
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – mô phỏng O(N·Q) | 8/8 | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – một k: hai con trỏ + nhảy khối | 8/8 | 8/8 | TLE | TLE | TLE | 25 |
| Cách 3 – gom đơn theo k | 8/8 | 8/8 | 8/8 | TLE | TLE | 45 |
| Cách 4 – quét offline + Fenwick cho mọi đơn | 8/8 | TLE | TLE | 8/8 | TLE | 35 |
| Cách 5 – chia căn theo k (lời giải đầy đủ) | 8/8 | 8/8 | 8/8 | 8/8 | 9/9 | 100 |
| Sai: quên thêm nxtOcc[p−1] vào BIT | 8/8 | 8/8 | 8/8 | 2/8 | 2/9 | 57,92 |
| Sai: lấy phần tử thứ p + k − 1 | 7/8 | 8/8 | 8/8 | 0/8 | 0/9 | 43,75 |
| Sai: dùng dãy nhảy xuất phát từ sọt 1 | 2/8 | 1/8 | 0/8 | 8/8 | 0/9 | 29,38 |
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: lời giải chuẩn chạy tối đa 0,31 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3,5 giây (hơn 3 lần giới hạn). Lời giải chuẩn (cả bản đặt ngưỡng T = 3 để ép mọi nhánh chạy) được đối chiếu với chương trình QHĐ $O(len^2)$ không dùng nhận xét tham lam trên 1000 test nhỏ ngẫu nhiên, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test. Bản Python đặt ngưỡng $T = 50$ thay vì $300$ vì trong Python vòng lặp hai con trỏ chậm hơn nhiều so với thao tác BIT, nên điểm cân bằng dịch về phía $T$ nhỏ – ý tưởng hoàn toàn giống bản C++.
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