Mạch kiến thức (Đề tự luyện HSG Tin 12 – Bài 5) – Thuật toán Mo chỉ thêm (rollback Mo), nén giá trị chèn ô trống và nối mạch bằng hai đầu mút
Đề bài
Mạch kiến thức. Cho dãy mã số video $a_1, a_2, \dots, a_N$ (nhật ký $N$ lượt xem) và $Q$ câu hỏi $[l, r]$. Với mỗi câu hỏi, xét tập các video được mở trong các lượt $l..r$; tìm dãy mã số liên tiếp $x, x+1, \dots, x+k-1$ dài nhất mà video nào cũng có trong tập (gọi là mạch kiến thức). In $k$ và $x$; nếu nhiều mạch cùng dài nhất thì in mạch có $x$ nhỏ nhất.
Dữ liệu vào: dòng đầu $N, Q$ ($1 \le N, Q \le 10^5$); dòng hai là $a_1..a_N$ ($1 \le a_i \le 10^9$); $Q$ dòng sau mỗi dòng $l\ r$ ($1 \le l \le r \le N$).
Kết quả: $Q$ dòng, mỗi dòng hai số $k$ và $x$.
- Subtask 1 (10%): $N, Q \le 2000$.
- Subtask 2 (15%): $a_i \le 20$.
- Subtask 3 (20%): $l = 1$ với mọi câu hỏi.
- Subtask 4 (25%): $N, Q \le 2 \cdot 10^4$.
- Subtask 5 (30%): không có ràng buộc gì thêm.
12 5
26 25 27 28 18 21 20 23 24 22 19 23
1 12
3 7
3 5
5 9
7 1111 18
2 20
2 27
2 20
3 22Câu 1: đủ các video $18..28$. Câu 2 (lượt $3..7$: $27, 28, 18, 21, 20$): hai mạch $20, 21$ và $27, 28$ cùng dài $2$, chọn $x = 20$. Câu 3: mạch $27, 28$. Câu 4 (lượt $5..9$: $18, 21, 20, 23, 24$): chọn $20, 21$. Câu 5 (lượt $7..11$: $20, 23, 24, 22, 19$): mạch $22, 23, 24$.
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 Mạch kiến thứcLời mở đầu
Đây là bài phân loại cuối đề. Đọc kỹ, ta thấy mấy điều quan trọng:
- Chỉ tập giá trị là quan trọng. Một video mở 1 lần hay 10 lần trong đoạn đều như nhau. Câu hỏi thực chất là: trong tập các số $a_l, \dots, a_r$, tìm đoạn số nguyên liên tiếp dài nhất nằm trọn trong tập.
- Thêm một số thì dễ. Ta quản lý các "mạch" hiện có (các đoạn số liên tiếp có mặt). Khi thêm số $x$ chưa có: nếu $x - 1$ có mặt thì $x$ nối vào cuối mạch bên trái; nếu $x + 1$ có mặt thì $x$ nối vào đầu mạch bên phải; có khi nối cả hai thành một mạch dài. Chỉ cần biết hai đầu mút của mỗi mạch: lưu
dau[s] = evàdau[e] = scho mạch $s..e$. Khi thêm $x$, số $x - 1$ (nếu có mặt) chắc chắn là đầu phải của mạch chứa nó (vì $x$ chưa có), nêndau[x-1]cho ngay đầu trái; tương tựdau[x+1]cho ngay đầu phải. Mỗi lần thêm là $O(1)$, và mạch tốt nhất chỉ có thể tốt lên. - Xóa một số thì khó. Xóa $x$ khỏi giữa một mạch sẽ bẻ nó làm đôi, và mạch tốt nhất có thể tụt xuống – ta không biết mạch tốt nhì là mạch nào nếu không có cấu trúc dữ liệu mạnh.
- Mã số tới $10^9$. Cần nén giá trị, nhưng phải cẩn thận: sau khi nén, hai mã kề nhau chưa chắc là hai số liền nhau (ví dụ 20 và 22 khi không ai xem video 21).
Thêm video 6: bên trái có mạch $3..5$ (đọc dau[5] = 3), bên phải có mạch $7..8$ (đọc dau[7] = 8), nối thành mạch $3..8$ chỉ bằng hai phép gán dau[3] = 8, dau[8] = 3.
Từ đó, lộ trình là: làm thô (Cách 1), khai thác giá trị nhỏ (Cách 2), khai thác "chỉ thêm" khi $l = 1$ (Cách 3), thuật toán Mo có cả thêm và xóa nhờ cây phân đoạn (Cách 4), và cuối cùng là thuật toán Mo chỉ thêm – tận dụng triệt để nhận xét 2 và né nhận xét 3 (Cách 5).
Cách 1Sắp xếp các mã số của từng câu hỏi – $O(Q \cdot N \log N)$ · 10%
Với mỗi câu hỏi, chép $a_l..a_r$ ra mảng b, sắp xếp và bỏ trùng. Duyệt b: nếu b[i-1] + 1 == b[i] thì mạch hiện tại dài thêm 1, ngược lại bắt đầu mạch mới tại b[i]. Vì duyệt tăng dần và chỉ cập nhật khi dài hơn hẳn, khi hòa ta tự động giữ mạch có $x$ nhỏ hơn.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
vector<long long> b(a.begin() + l, a.begin() + r + 1);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
int bestLen = 0, len = 0;
long long bestX = 0, x = 0;
for (int i = 0; i < (int)b.size(); i++) {
if (i > 0 && b[i - 1] + 1 == b[i]) len++;
else { len = 1; x = b[i]; } // bắt đầu mạch mới
if (len > bestLen) { bestLen = len; bestX = x; }
}
printf("%d %lld\n", bestLen, bestX);
}
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]]
out = []
p = 2 + n
for _ in range(q):
l = int(data[p]); r = int(data[p + 1]); p += 2
b = sorted(set(a[l:r + 1]))
bestLen = 0; bestX = 0; ln = 0; x = 0
for i in range(len(b)):
if i > 0 and b[i - 1] + 1 == b[i]:
ln += 1
else: # bắt đầu mạch mới
ln = 1; x = b[i]
if ln > bestLen:
bestLen = ln; bestX = x
out.append("%d %d" % (bestLen, bestX))
print("\n".join(out))
main()Cách 2Mã số không quá 20: đếm tiền tố – $O(20 \cdot (N + Q))$ · 15%
Khi $a_i \le 20$, chỉ có 20 video. Lập dem[v][i] = số lần video $v$ được mở trong $i$ lượt đầu. Video $v$ có mặt trong đoạn $[l, r]$ khi và chỉ khi dem[v][r] - dem[v][l-1] > 0. Mỗi câu hỏi chỉ cần duyệt $v = 1..20$ để tìm mạch dài nhất.
#include <bits/stdc++.h>
using namespace std;
const int V = 20;
int main() {
int n, q;
scanf("%d %d", &n, &q);
// dem[v][i] = số lượt xem video v trong i lượt đầu
vector<vector<int>> dem(V + 2, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
long long x;
scanf("%lld", &x);
for (int v = 1; v <= V; v++) dem[v][i] = dem[v][i - 1];
if (x <= V) dem[x][i]++;
}
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
int bestLen = 0, bestX = 0, len = 0;
for (int v = 1; v <= V; v++) {
if (dem[v][r] - dem[v][l - 1] > 0) {
len++;
if (len > bestLen) { bestLen = len; bestX = v - len + 1; }
} else len = 0;
}
printf("%d %d\n", bestLen, bestX);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
V = 20
# dem[v][i] = số lượt xem video v trong i lượt đầu
dem = [[0] * (n + 1) for _ in range(V + 1)]
for i in range(1, n + 1):
x = int(data[1 + i])
for v in range(1, V + 1):
dem[v][i] = dem[v][i - 1]
if x <= V:
dem[x][i] += 1
out = []
p = 2 + n
for _ in range(q):
l = int(data[p]); r = int(data[p + 1]); p += 2
bestLen = 0; bestX = 0; ln = 0
for v in range(1, V + 1):
if dem[v][r] - dem[v][l - 1] > 0:
ln += 1
if ln > bestLen:
bestLen = ln; bestX = v - ln + 1
else:
ln = 0
out.append("%d %d" % (bestLen, bestX))
print("\n".join(out))
main()Cách 3Khi $l = 1$: chỉ thêm, nối mạch bằng hai đầu mút – $O(N + Q)$ · 20%
Khi mọi câu hỏi có $l = 1$, đáp án của câu $[1, r]$ chỉ phụ thuộc $r$. Ta thêm lần lượt $a_1, a_2, \dots, a_N$ vào tập theo nhận xét 2 và ghi lại đáp án sau mỗi bước. Mã số tới $10^9$ nên dùng unordered_map (C++) / dict (Python) làm mảng dau: khóa nào có trong map nghĩa là video đó đã được xem.
Chú ý khi so sánh với mạch tốt nhất: dài hơn hẳn thì lấy; bằng độ dài mà $x$ nhỏ hơn thì cũng lấy – vì mạch mới có thể nằm bên trái mạch cũ. Bấm "Tiếp" để xem từng bước thêm:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
// Mọi truy vấn có l = 1: thêm dần a[1], a[2], ... và ghi lại đáp án của từng tiền tố
unordered_map<long long, long long> dau; // video v là đầu mạch -> đầu kia của mạch
dau.reserve(2 * n + 7);
vector<int> ansLen(n + 1);
vector<long long> ansX(n + 1);
int bestLen = 0;
long long bestX = 0;
for (int i = 1; i <= n; i++) {
long long x = a[i];
if (!dau.count(x)) {
long long s = dau.count(x - 1) ? dau[x - 1] : x;
long long e = dau.count(x + 1) ? dau[x + 1] : x;
dau[x] = x;
dau[s] = e;
dau[e] = s;
int len = e - s + 1;
if (len > bestLen || (len == bestLen && s < bestX)) { bestLen = len; bestX = s; }
}
ansLen[i] = bestLen;
ansX[i] = bestX;
}
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d %lld\n", ansLen[r], ansX[r]);
}
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]]
# Mọi truy vấn có l = 1: thêm dần a[1], a[2], ... và ghi lại đáp án của từng tiền tố
dau = {} # video v là đầu mạch -> đầu kia của mạch
ansLen = [0] * (n + 1); ansX = [0] * (n + 1)
bestLen = 0; bestX = 0
for i in range(1, n + 1):
x = a[i]
if x not in dau:
s = dau.get(x - 1, x)
e = dau.get(x + 1, x)
dau[x] = x
dau[s] = e
dau[e] = s
ln = e - s + 1
if ln > bestLen or (ln == bestLen and s < bestX):
bestLen = ln; bestX = s
ansLen[i] = bestLen; ansX[i] = bestX
out = []
p = 2 + n
for _ in range(q):
r = int(data[p + 1]); p += 2
out.append("%d %d" % (ansLen[r], ansX[r]))
print("\n".join(out))
main()Cách 4Thuật toán Mo + cây phân đoạn trên giá trị – $O((N + Q)\sqrt{N} \log N)$ · 70%
Thuật toán Mo trả lời các câu hỏi đoạn offline: chia các vị trí thành khối độ dài $B \approx N / \sqrt{Q}$, sắp các câu hỏi theo (khối của $l$, rồi $r$), rồi dịch hai con trỏ cl, cr từ câu này sang câu kia, mỗi bước thêm hoặc bớt một phần tử. Trong một khối, $r$ tăng dần nên cr đi tổng cộng $O(N)$; cl mỗi câu chỉ lắc trong một khối, $O(B)$. Tổng số bước cỡ $O(N \sqrt{Q})$. (Mẹo nhỏ: khối lẻ thì sắp $r$ giảm dần để cr khỏi chạy ngược về đầu.)
Mo cần cả thêm lẫn bớt. Ta giữ dem[x] = số lần mã $x$ xuất hiện trong đoạn hiện tại; khi dem[x] đổi giữa 0 và 1, ta bật/tắt lá $x$ của một cây phân đoạn trên các giá trị đã nén. Mỗi nút lưu: tien = độ dài mạch bắt đầu ở mép trái nút, hau = độ dài mạch kết thúc ở mép phải, và mạch tốt nhất (len, xs). Ghép hai con chỉ "nối" được khi giá trị cuối nửa trái và giá trị đầu nửa phải liền số (mảng ke) – đây chính là chỗ xử lý nhận xét 4. Gốc cây cho ngay đáp án.
#include <bits/stdc++.h>
using namespace std;
int D, P;
vector<long long> V;
vector<int> dem, dai, giua; // dai[o]: số giá trị nút o quản lý; giua[o]: giá trị nén cuối của nửa trái
vector<int> tien, hau, len, xs; // mạch đầu nút, mạch cuối nút, mạch tốt nhất (độ dài, giá trị nén đầu mạch)
vector<char> ke; // ke[x] = 1 nếu V[x] + 1 == V[x + 1]
void gop(int o) {
int A = 2 * o, C = 2 * o + 1, m = giua[o];
bool noi = m < D - 1 && ke[m];
tien[o] = (tien[A] == dai[A] && noi) ? dai[A] + tien[C] : tien[A];
hau[o] = (hau[C] == dai[C] && noi) ? dai[C] + hau[A] : hau[C];
len[o] = len[A]; xs[o] = xs[A];
if (len[C] > len[o]) { len[o] = len[C]; xs[o] = xs[C]; }
if (noi && hau[A] > 0 && tien[C] > 0) {
int l = hau[A] + tien[C], x = m - hau[A] + 1;
if (l > len[o] || (l == len[o] && x < xs[o])) { len[o] = l; xs[o] = x; }
}
}
void datLa(int x, int v) { // v = 1: video x đang được xem trong đoạn; v = 0: không
int o = P + x;
tien[o] = hau[o] = len[o] = v;
xs[o] = x;
for (o /= 2; o >= 1; o /= 2) gop(o);
}
void them(int x) { if (++dem[x] == 1) datLa(x, 1); }
void bot(int x) { if (--dem[x] == 0) datLa(x, 0); }
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<long long> a(n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
V = a;
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
D = V.size();
vector<int> id(n);
for (int i = 0; i < n; i++) id[i] = lower_bound(V.begin(), V.end(), a[i]) - V.begin();
ke.assign(D, 0);
for (int x = 0; x + 1 < D; x++) ke[x] = (V[x] + 1 == V[x + 1]);
P = 1;
while (P < D) P *= 2;
dai.assign(2 * P, 1); giua.assign(2 * P, 0);
tien.assign(2 * P, 0); hau.assign(2 * P, 0); len.assign(2 * P, 0); xs.assign(2 * P, 0);
for (int x = 0; x < P; x++) xs[P + x] = x;
for (int o = P - 1; o >= 1; o--) {
dai[o] = dai[2 * o] + dai[2 * o + 1];
int c = 2 * o;
while (c < P) c = 2 * c + 1; // lá phải nhất của con trái
giua[o] = c - P;
gop(o);
}
dem.assign(D, 0);
vector<int> L(q), R(q);
for (int i = 0; i < q; i++) {
scanf("%d %d", &L[i], &R[i]);
L[i]--; R[i]--;
}
int B = max(1, (int)(n / sqrt((double)q)));
vector<int> ord(q);
for (int i = 0; i < q; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int x, int y) {
if (L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return (L[x] / B % 2) ? R[x] > R[y] : R[x] < R[y];
});
vector<int> ansLen(q);
vector<long long> ansX(q);
int cl = 0, cr = -1;
for (int t = 0; t < q; t++) {
int i = ord[t];
while (cr < R[i]) them(id[++cr]);
while (cl > L[i]) them(id[--cl]);
while (cr > R[i]) bot(id[cr--]);
while (cl < L[i]) bot(id[cl++]);
ansLen[i] = len[1];
ansX[i] = V[xs[1]];
}
for (int i = 0; i < q; i++) printf("%d %lld\n", ansLen[i], ansX[i]);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [int(x) for x in data[2:2 + n]]
V = sorted(set(a))
D = len(V)
pos = {V[k]: k for k in range(D)}
idx = [pos[x] for x in a]
ke = [1 if V[x] + 1 == V[x + 1] else 0 for x in range(D - 1)] + [0]
P = 1
while P < D:
P *= 2
dai = [1] * (2 * P); giua = [0] * (2 * P)
tien = [0] * (2 * P); hau = [0] * (2 * P); ln = [0] * (2 * P); xs = [0] * (2 * P)
for x in range(P):
xs[P + x] = x
for o in range(P - 1, 0, -1):
dai[o] = dai[2 * o] + dai[2 * o + 1]
c = 2 * o
while c < P:
c = 2 * c + 1 # lá phải nhất của con trái
giua[o] = c - P
def gop(o):
A = 2 * o; C = A + 1; m = giua[o]
noi = m < D - 1 and ke[m]
tien[o] = dai[A] + tien[C] if (tien[A] == dai[A] and noi) else tien[A]
hau[o] = dai[C] + hau[A] if (hau[C] == dai[C] and noi) else hau[C]
bl = ln[A]; bx = xs[A]
if ln[C] > bl:
bl = ln[C]; bx = xs[C]
if noi and hau[A] > 0 and tien[C] > 0:
l = hau[A] + tien[C]; x = m - hau[A] + 1
if l > bl or (l == bl and x < bx):
bl = l; bx = x
ln[o] = bl; xs[o] = bx
def datLa(x, v): # v = 1: video x đang được xem trong đoạn; v = 0: không
o = P + x
tien[o] = hau[o] = ln[o] = v
o //= 2
while o >= 1:
gop(o)
o //= 2
dem = [0] * D
L = [0] * q; R = [0] * q
p = 2 + n
for i in range(q):
L[i] = int(data[p]) - 1; R[i] = int(data[p + 1]) - 1; p += 2
B = max(1, int(n / q ** 0.5))
def khoa(i):
b = L[i] // B
return b * (n + 1) + (n - R[i] if b % 2 else R[i])
ord_ = sorted(range(q), key=khoa)
ansLen = [0] * q; ansX = [0] * q
cl = 0; cr = -1
for i in ord_:
while cr < R[i]:
cr += 1; x = idx[cr]; dem[x] += 1
if dem[x] == 1: datLa(x, 1)
while cl > L[i]:
cl -= 1; x = idx[cl]; dem[x] += 1
if dem[x] == 1: datLa(x, 1)
while cr > R[i]:
x = idx[cr]; cr -= 1; dem[x] -= 1
if dem[x] == 0: datLa(x, 0)
while cl < L[i]:
x = idx[cl]; cl += 1; dem[x] -= 1
if dem[x] == 0: datLa(x, 0)
ansLen[i] = ln[1]; ansX[i] = V[xs[1]]
sys.stdout.write("\n".join(str(ansLen[i]) + " " + str(ansX[i]) for i in range(q)) + "\n")
main()Với $N = Q = 2 \cdot 10^4$ cách này chạy khoảng 0,5 giây; nhưng với $N = Q = 10^5$, khi các mã số gần như khác nhau đôi một (mỗi bước Mo đều bật/tắt một lá), có cỡ $6 \cdot 10^7$ lần cập nhật cây, mỗi lần 17 tầng – mất 4–8 giây. Khi $a_i \le 20$ hoặc $l = 1$ thì cây gần như không phải cập nhật / Mo chỉ đi một chiều, nên cách này vẫn qua subtask 2 và 3: tổng cộng 70%.
Cách 5Thuật toán Mo chỉ thêm (rollback Mo) – $O(N \sqrt{Q})$ · 100%
Nút thắt của Cách 4 là thao tác bớt. Ý tưởng của "Mo chỉ thêm": sắp xếp lại công việc sao cho ta không bao giờ phải bớt – chỉ thêm, và khi cần "lùi" thì hoàn tác những gì vừa thêm (giống nút Undo).
- Chia vị trí thành khối độ dài $B$; sắp các câu hỏi theo (khối của $l$, rồi $r$ tăng dần).
- Xét lần lượt từng khối. Gọi $E$ là vị trí cuối khối. Khi sang khối mới: xóa sạch cấu trúc, đặt con trỏ phải $r = E$ (đoạn "vĩnh viễn" đang rỗng).
- Câu hỏi có $R > E$: đoạn của nó gồm hai phần – phần bên phải $E+1..R$ và phần trong khối $L..E$.
- Phần bên phải: vì $R$ tăng dần trong khối, ta chỉ việc thêm vĩnh viễn $a_{r+1}, \dots, a_R$ – không bao giờ phải bớt.
- Phần trong khối: thêm tạm $a_L, \dots, a_E$ (tối đa $B$ phần tử), mỗi lần sửa mảng
dauđều ghi vào nhật ký (vị trí, giá trị cũ). Đọc đáp án. Rồi hoàn tác theo nhật ký từ cuối về đầu và khôi phục mạch tốt nhất đã lưu – cấu trúc trở về đúng trạng thái "chỉ có phần vĩnh viễn".
- Câu hỏi có $R \le E$ (nằm gọn trong khối, dài không quá $B$): thêm tạm cả $a_L..a_R$, đọc đáp án, hoàn tác. Những câu này đứng đầu khối (vì $R$ nhỏ nhất) nên lúc đó phần vĩnh viễn còn rỗng.
Chi phí: phần vĩnh viễn mỗi khối đi tối đa $N$ bước, có $N / B$ khối; phần tạm mỗi câu tối đa $B$ bước. Tổng $O(N^2 / B + Q \cdot B)$, chọn $B = N / \sqrt{Q}$ được $O(N \sqrt{Q})$ – và mỗi bước chỉ là vài phép gán mảng, không có $\log$.
Sắp các mã số khác nhau tăng dần và đánh mã nén $1, 2, 3, \dots$; nhưng mỗi khi hai mã số kề nhau không liền số (như 20 và 22), ta chèn thêm một mã trống ở giữa. Mã trống không bao giờ được xem nên dau của nó luôn là $-1$, tự động "chặn" không cho hai mạch nối qua. Nhờ vậy hàm them không cần biết giá trị thật, độ dài mạch là e - s + 1 trên mã nén, và mã nén tăng cùng chiều giá trị thật nên so sánh $x$ nhỏ nhất cũng làm trên mã nén. Thêm mã trống ở hai đầu (mã $0$ và $M + 1$) để khỏi lo tràn chỉ số.
Mô phỏng dưới đây chạy Mo chỉ thêm trên ví dụ của đề (khối dài $B = \lfloor 12 / \sqrt{5} \rfloor = 5$). Ô xanh là phần vĩnh viễn, ô cam là phần thêm tạm:
Code hoàn chỉnh. Bản Python giữ đúng các bước, nhưng viết thẳng phần thêm vào vòng lặp (gọi hàm trong Python khá chậm) và nhật ký là một danh sách phẳng (vị trí, giá trị cũ):
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
// Nén giá trị: hai video liền số (v, v + 1) nhận hai mã liền nhau;
// giữa hai video KHÔNG liền số chèn thêm một mã "trống" (không bao giờ được xem).
int ma[MAXN], gtri[2 * MAXN + 5];
int dau[2 * MAXN + 5]; // dau[x] = -1: chưa xem; x là đầu mạch -> dau[x] = đầu kia của mạch
int bestLen, bestX; // mạch tốt nhất: độ dài, mã của video đầu mạch
int logPos[3 * MAXN], logOld[3 * MAXN], logSz = 0;
bool ghi = false; // có ghi nhật ký để hoàn tác hay không
void gan(int x, int v) {
if (ghi) { logPos[logSz] = x; logOld[logSz] = dau[x]; logSz++; }
dau[x] = v;
}
void them(int x) { // thêm video có mã x
if (dau[x] >= 0) return;
int s = dau[x - 1] >= 0 ? dau[x - 1] : x;
int e = dau[x + 1] >= 0 ? dau[x + 1] : x;
gan(x, x);
gan(s, e);
gan(e, s);
int len = e - s + 1;
if (len > bestLen || (len == bestLen && s < bestX)) { bestLen = len; bestX = s; }
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<long long> a(n);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
vector<long long> v = a;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int M = 0; // mã 0 là ô trống bên trái
vector<int> maOf(v.size());
for (int k = 0; k < (int)v.size(); k++) {
if (k > 0 && v[k - 1] + 1 != v[k]) M++; // chèn ô trống
maOf[k] = ++M;
gtri[M] = (int)v[k];
}
for (int i = 0; i < n; i++) ma[i] = maOf[lower_bound(v.begin(), v.end(), a[i]) - v.begin()];
vector<int> L(q), R(q);
for (int i = 0; i < q; i++) {
scanf("%d %d", &L[i], &R[i]);
L[i]--; R[i]--;
}
int B = max(1, (int)(n / sqrt((double)q)));
vector<int> ord(q);
for (int i = 0; i < q; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int x, int y) {
if (L[x] / B != L[y] / B) return L[x] / B < L[y] / B;
return R[x] < R[y];
});
vector<int> ansLen(q), ansX(q);
int khoi = -1, r = -1;
for (int t = 0; t < q; t++) {
int i = ord[t], b = L[i] / B, E = min(n - 1, (b + 1) * B - 1);
if (b != khoi) { // sang khối mới: xóa sạch
for (int x = 0; x <= M + 1; x++) dau[x] = -1;
bestLen = 0; bestX = 0;
khoi = b; r = E;
}
int luuLen = bestLen, luuX = bestX;
if (R[i] <= E) { // truy vấn nằm gọn trong khối
ghi = true;
for (int j = L[i]; j <= R[i]; j++) them(ma[j]);
} else {
ghi = false; // phần bên phải khối: thêm vĩnh viễn
while (r < R[i]) { r++; them(ma[r]); }
luuLen = bestLen; luuX = bestX;
ghi = true; // phần trong khối: thêm tạm
for (int j = L[i]; j <= E; j++) them(ma[j]);
}
ansLen[i] = bestLen;
ansX[i] = gtri[bestX];
while (logSz > 0) { logSz--; dau[logPos[logSz]] = logOld[logSz]; } // hoàn tác
bestLen = luuLen; bestX = luuX;
ghi = false;
}
for (int i = 0; i < q; i++) printf("%d %d\n", ansLen[i], ansX[i]);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [int(x) for x in data[2:2 + n]]
# Nén giá trị: video liền số nhận mã liền nhau, giữa hai video không liền số chèn một mã "trống"
v = sorted(set(a))
gtri = [0] * (2 * len(v) + 3)
maOf = {}
M = 0
for k in range(len(v)):
if k > 0 and v[k - 1] + 1 != v[k]:
M += 1
M += 1
maOf[v[k]] = M
gtri[M] = v[k]
ma = [maOf[x] for x in a]
L = [0] * q; R = [0] * q
p = 2 + n
for i in range(q):
L[i] = int(data[p]) - 1; R[i] = int(data[p + 1]) - 1; p += 2
B = max(1, int(n / q ** 0.5))
ord_ = sorted(range(q), key=lambda i: (L[i] // B) * (n + 1) + R[i])
lmax = {}
for i in range(q):
b = L[i] // B
if lmax.get(b, -1) < L[i]:
lmax[b] = L[i]
ansLen = [0] * q; ansX = [0] * q
khoi = -1; r = -1; bl = 0; bx = 0
dau = [-1] * (M + 2)
tch = []
for i in ord_:
b = L[i] // B
E = lmax[b] - 1 # phần cố định bắt đầu từ L lớn nhất của khối
if b != khoi: # sang khối mới: xóa sạch
for x in tch: # chỉ xóa các ô đã dùng
dau[x] = -1
tch = []
bl = 0; bx = 0; khoi = b; r = E
if R[i] <= E: # truy vấn nằm gọn trong khối
lo = L[i]; hi = R[i]
else:
Ri = R[i] # phần bên phải khối: thêm vĩnh viễn
while r < Ri:
r += 1
x = ma[r]
if dau[x] < 0:
s = dau[x - 1]
if s < 0: s = x
e = dau[x + 1]
if e < 0: e = x
dau[x] = x; dau[s] = e; dau[e] = s
tch.append(x)
ln = e - s + 1
if ln > bl or (ln == bl and s < bx):
bl = ln; bx = s
lo = L[i]; hi = E
luuL = bl; luuX = bx
nk = [] # nhật ký: (vị trí, giá trị cũ) để hoàn tác
ap = nk.append
for j in range(lo, hi + 1): # phần trong khối: thêm tạm
x = ma[j]
if dau[x] < 0:
s = dau[x - 1]
if s < 0: s = x
e = dau[x + 1]
if e < 0: e = x
ap(x); ap(-1)
if s != x:
ap(s); ap(dau[s])
if e != x:
ap(e); ap(dau[e])
dau[x] = x; dau[s] = e; dau[e] = s
ln = e - s + 1
if ln > bl or (ln == bl and s < bx):
bl = ln; bx = s
ansLen[i] = bl; ansX[i] = gtri[bx]
for k in range(len(nk) - 2, -1, -2): # hoàn tác
dau[nk[k]] = nk[k + 1]
bl = luuL; bx = luuX
sys.stdout.write("\n".join(str(ansLen[i]) + " " + str(ansX[i]) for i in range(q)) + "\n")
main()(1) Nén giá trị mà quên ô trống: 20 và 22 bị coi là liền số. (2) Hòa độ dài nhưng không so $x$: trong Mo, thứ tự thêm lộn xộn nên mạch bên phải có thể được tạo trước. (3) Hoàn tác mảng dau mà quên khôi phục bestLen, bestX – đáp án câu trước "rò" sang câu sau. (4) Không xử lý riêng câu hỏi nằm gọn trong một khối: thêm $a_L..a_E$ là thêm thừa các lượt sau $R$. Cả bốn lỗi đều vẫn ra đúng ví dụ của đề, nhưng bộ test bắt được hết (xem bảng cuối bài).
Em có thể chạy tay từng dòng code C++ ở trên với dữ liệu nhỏ ($N \le 12$, $Q \le 6$):
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 – sắp xếp từng câu | Đúng | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – đếm tiền tố 20 giá trị | WA | Đúng | WA | WA | WA | 15 |
| Cách 3 – chỉ đúng khi l = 1 | WA | WA | Đúng | WA | WA | 20 |
| Cách 4 – Mo + cây phân đoạn | Đúng | Đúng | Đúng | Đúng | TLE | 70 |
| Cách 5 – Mo chỉ thêm | Đúng | Đúng | Đúng | Đúng | Đúng | 100 |
| Nén giá trị quên ô trống | 3/8 | 5/6 | 2/6 | 2/8 | 2/9 | 35.83 |
| Quên khôi phục mạch tốt nhất khi hoàn tác | 1/8 | WA | Đúng | WA | WA | 21.25 |
| Không xử lý riêng câu nằm gọn trong khối | 1/8 | WA | WA | 3/8 | WA | 10.63 |
| Hòa độ dài không so x | 1/8 | WA | WA | WA | WA | 1.25 |
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 (8 + 6 + 6 + 8 + 9), giới hạn 1 giây. Cách 5 chạy tối đa khoảng 0,3 giây; Cách 4 (Mo + cây phân đoạn) mất 4–8 giây ở mỗi test subtask 5 vì gần như mỗi bước Mo đều phải cập nhật cây. Lỗi "nén quên ô trống" vẫn sống sót ở những test mà các mã số phủ kín một khoảng (như ví dụ của đề) – vì vậy mình cố ý chọn ví dụ như vậy để các em không thể "dò" lỗi qua ví dụ 😉.
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