Khung tre (Đề tự luyện HSG Tin quốc gia – Bài 4)
Đề bài
Khung tre. Có $N$ cây tre xếp hàng, cây $i$ dài $a_i$. Đoạn liên tiếp $[l, r]$ gọi là vây được nếu dùng tất cả các cây trong đoạn ghép được một đa giác có diện tích dương, tức là có ít nhất 3 cây và cây dài nhất ngắn hơn tổng các cây còn lại. Trả lời $Q$ câu hỏi $(L, R)$: có bao nhiêu đoạn vây được $[l, r]$ với $L \le l \le r \le R$?
Dữ liệu vào: dòng 1 gồm $N, Q$ $(1 \le N, Q \le 10^5)$; dòng 2 gồm $a_1..a_N$ $(1 \le a_i \le 10^9)$; $Q$ dòng sau mỗi dòng gồm $L, R$ $(1 \le L \le R \le N)$.
Kết quả: $Q$ dòng, mỗi dòng là đáp án của câu hỏi tương ứng.
- Subtask 1 (10%): $N, Q \le 300$.
- Subtask 2 (15%): $N \le 3000$.
- Subtask 3 (20%): $a_1 \le a_2 \le \ldots \le a_N$.
- Subtask 4 (25%): $Q = 1$.
- 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.
6 3
5 8 12 11 2 1
1 6
3 6
3 59
2
1Các đoạn vây được: $[1,3], [1,4], [1,5], [1,6], [2,4], [2,5], [2,6], [3,5], [3,6]$. Ví dụ $[3,5] = (12, 11, 2)$: $12 < 13$; còn $[4,6] = (11, 2, 1)$ thì không vì $11 \ge 3$.
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 Khung treLời mở đầu
Đây là bài cuối, bài "phân loại" của đề. Đề rất ngắn nhưng có tới ba lớp khó chồng lên nhau: điều kiện "vây được" không đơn điệu, số đoạn vây được có thể lên tới $\approx 5 \cdot 10^9$ (không thể liệt kê từng đoạn), và mỗi câu hỏi lại hỏi trên một khúc $[L, R]$ khác nhau. Mình sẽ đi qua 5 cách, mỗi cách gỡ thêm một lớp.
Nhận xét 1: viết lại điều kiện bằng tổng và max
Gọi $S = a_l + \ldots + a_r$ và $M = \max(a_l..a_r)$. "Cây dài nhất ngắn hơn tổng các cây còn lại" chính là $M < S - M$, tức là $$2M < S.$$ Điều kiện "ít nhất 3 cây" tự động thỏa: với 1 cây thì $S = M$, với 2 cây thì $S \le 2M$. Chú ý dấu nhỏ hơn hẳn: $2M = S$ là đa giác dẹt, không tính.
Nhận xét 2: "vây được" không đơn điệu
Thêm một cây vào đoạn có thể làm hỏng đoạn: $(3, 3, 3)$ vây được ($6 < 9$), nhưng $(3, 3, 3, 10)$ thì không ($20 \ge 19$); thêm tiếp vài cây nữa thì lại vây được. Vì vậy các kỹ thuật "hai con trỏ" quen thuộc không dùng được. Mỗi câu hỏi $(L, R)$ là đếm các ô "tốt" trong một góc của bảng $(l, r)$:
Hình 1. Bảng các đoạn $(l, r)$ của ví dụ đề. Câu hỏi $(L, R)$ đếm các ô tốt có $l \ge L$ và $r \le R$.
Cách 1Duyệt mọi đoạn – O(Q·N²) · 10%
Với mỗi câu hỏi, cố định $l$ rồi cho $r$ chạy từ $l$ tới $R$, cập nhật dần tổng và max, đếm các lần $2M < S$. Mỗi câu hỏi $O(N^2)$, với $N, Q \le 300$ là khoảng $1{,}4 \cdot 10^7$ phép tính.
#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);
long long cnt = 0;
for (int l = L; l <= R; l++) {
long long mx = 0, s = 0; // max va tong cua doan [l, r]
for (int r = l; r <= R; r++) {
mx = max(mx, a[r]); s += a[r];
if (2 * mx < s) cnt++; // cay dai nhat < tong cac cay con lai
}
}
printf("%lld\n", cnt);
}
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
cnt = 0
for l in range(L, R + 1):
mx = 0; s = 0 # max va tong cua doan [l, r]
for r in range(l, R + 1):
x = a[r]
if x > mx:
mx = x
s += x
if 2 * mx < s: # cay dai nhat < tong cac cay con lai
cnt += 1
out.append(cnt)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 2Gom câu hỏi theo L – O(N² + Q) · 25%
Gọi $col_L[r]$ là số $l \ge L$ sao cho $[l, r]$ vây được. Khi đó đáp án câu hỏi $(L, R)$ là $col_L[L] + col_L[L+1] + \ldots + col_L[R]$. Ta cho $L$ chạy giảm dần từ $N$ về 1: mỗi khi giảm $L$, chỉ cần duyệt các đoạn $[L, r]$ (một vòng $O(N)$) và cộng 1 vào $col[r]$ với mỗi đoạn tốt. Câu hỏi nào có đúng $L$ đó thì trả lời bằng tổng tiền tố của $col$ (tính lại $O(N)$, chỉ khi có câu hỏi). Tổng cộng $O(N^2 + Q)$: đủ cho $N \le 3000$ dù $Q = 10^5$.
#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]);
vector<vector<pair<int, int>>> qs(n + 1); // gom cau hoi theo L
vector<long long> ans(q);
for (int t = 0; t < q; t++) { int L, R; scanf("%d %d", &L, &R); qs[L].push_back({R, t}); }
vector<long long> col(n + 1, 0); // col[r] = so l >= L de [l, r] tot
for (int L = n; L >= 1; L--) {
long long mx = 0, s = 0;
for (int r = L; r <= n; r++) {
mx = max(mx, a[r]); s += a[r];
if (2 * mx < s) col[r]++;
}
if (qs[L].empty()) continue;
vector<long long> pre(n + 1, 0); // pre[R] = col[L] + ... + col[R]
for (int r = L; r <= n; r++) pre[r] = (r > L ? pre[r - 1] : 0) + col[r];
for (auto& [R, t] : qs[L]) ans[t] = pre[R];
}
for (int t = 0; t < q; t++) printf("%lld\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]]
qs = [[] for _ in range(n + 1)] # gom cau hoi theo L
p = 2 + n
for t in range(q):
L = int(data[p]); R = int(data[p + 1]); p += 2
qs[L].append((R, t))
ans = [0] * q
col = [0] * (n + 1) # col[r] = so l >= L de [l, r] tot
for L in range(n, 0, -1):
mx = 0; s = 0
for r in range(L, n + 1):
x = a[r]
if x > mx:
mx = x
s += x
if 2 * mx < s:
col[r] += 1
if qs[L]:
pre = [0] * (n + 1); acc = 0
for r in range(L, n + 1):
acc += col[r]; pre[r] = acc
for R, t in qs[L]:
ans[t] = pre[R]
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()long long cho bộ đếm.Cách 3Dãy không giảm: một chặt nhị phân + Fenwick – O((N + Q) log N) · 45%
Nếu $a$ không giảm thì cây dài nhất của $[l, r]$ luôn là $a_r$. Dùng tổng tiền tố $P$ ($P_0 = 0$, $P_i = a_1 + \ldots + a_i$), điều kiện thành $$P_r - P_{l-1} > 2a_r \iff P_{l-1} < P_r - 2a_r.$$ Vì $a_i \ge 1$ nên $P$ tăng hẳn, các $l$ thỏa mãn là một đoạn đầu $l = 1..t_r$, với $t_r$ = số chỉ số $j < r$ có $P_j < P_r - 2a_r$ (chặt nhị phân). Đáp án câu hỏi $(L, R)$ là $$\sum_{r \le R,\ t_r \ge L} (t_r - L + 1).$$ Lại cho $L$ giảm dần: khi $L$ chạm $t_r$ thì "kích hoạt" $r$ — cộng 1 vào Fenwick đếm và cộng $t_r$ vào Fenwick tổng tại vị trí $r$. Câu hỏi $(L, R)$ = (tổng $t_r$ đã kích hoạt với $r \le R$) $- (L - 1) \times$ (số $r$ đã kích hoạt với $r \le R$).
Code dưới đây kiểm tra dãy có không giảm không; nếu không thì quay về Cách 2, nên Cách 3 ăn được subtask 1, 2, 3.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
vector<ll> fc, fs; // Fenwick: so luong va tong t_r
void add(int i, ll t) { for (; i <= n; i += i & -i) { fc[i]++; fs[i] += t; } }
int main() {
scanf("%d %d", &n, &q);
vector<ll> a(n + 1), P(n + 1, 0);
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); P[i] = P[i - 1] + a[i]; }
vector<int> QL(q), QR(q);
for (int t = 0; t < q; t++) scanf("%d %d", &QL[t], &QR[t]);
vector<ll> ans(q);
bool sorted_ = true;
for (int i = 1; i < n; i++) if (a[i] > a[i + 1]) sorted_ = false;
if (sorted_) {
// day khong giam: max cua [l, r] la a[r]; [l, r] tot <=> P[l-1] < P[r] - 2a[r] <=> l <= t[r]
vector<vector<int>> byT(n + 1);
for (int r = 1; r <= n; r++) {
int t = lower_bound(P.begin(), P.begin() + r, P[r] - 2 * a[r]) - P.begin(); // so j < r co P[j] < P[r] - 2a[r]
if (t >= 1) byT[t].push_back(r);
}
vector<vector<int>> qs(n + 1);
for (int t = 0; t < q; t++) qs[QL[t]].push_back(t);
fc.assign(n + 1, 0); fs.assign(n + 1, 0);
for (int L = n; L >= 1; L--) {
for (int r : byT[L]) add(r, L); // cac r co t[r] = L bat dau dong gop khi L giam toi day
for (int t : qs[L]) {
ll c = 0, s = 0;
for (int i = QR[t]; i > 0; i -= i & -i) { c += fc[i]; s += fs[i]; }
ans[t] = s - (ll)(L - 1) * c; // tong (t[r] - L + 1) voi r <= R, t[r] >= L
}
}
} else {
// quay ve Cach 2: O(N^2)
vector<vector<pair<int, int>>> qs(n + 1);
for (int t = 0; t < q; t++) qs[QL[t]].push_back({QR[t], t});
vector<ll> col(n + 1, 0), pre(n + 1, 0);
for (int L = n; L >= 1; L--) {
ll mx = 0, s = 0;
for (int r = L; r <= n; r++) { mx = max(mx, a[r]); s += a[r]; if (2 * mx < s) col[r]++; }
if (qs[L].empty()) continue;
for (int r = L; r <= n; r++) pre[r] = (r > L ? pre[r - 1] : 0) + col[r];
for (auto& [R, t] : qs[L]) ans[t] = pre[R];
}
}
for (int t = 0; t < q; t++) printf("%lld\n", ans[t]);
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [0] * (n + 1); P = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[1 + i]); P[i] = P[i - 1] + a[i]
QL = [0] * q; QR = [0] * q
p = 2 + n
for t in range(q):
QL[t] = int(data[p]); QR[t] = int(data[p + 1]); p += 2
ans = [0] * q
if all(a[i] <= a[i + 1] for i in range(1, n)):
# day khong giam: [l, r] tot <=> l <= t[r] = so j < r co P[j] < P[r] - 2a[r]
byT = [[] for _ in range(n + 1)]
for r in range(1, n + 1):
t = bisect_left(P, P[r] - 2 * a[r], 0, r)
if t >= 1:
byT[t].append(r)
qs = [[] for _ in range(n + 1)]
for t in range(q):
qs[QL[t]].append(t)
fc = [0] * (n + 1); fs = [0] * (n + 1)
for L in range(n, 0, -1):
for r in byT[L]:
i = r
while i <= n:
fc[i] += 1; fs[i] += L; i += i & -i
for t in qs[L]:
i = QR[t]; c = 0; s = 0
while i:
c += fc[i]; s += fs[i]; i &= i - 1
ans[t] = s - (L - 1) * c
else:
# quay ve Cach 2: O(N^2)
qs = [[] for _ in range(n + 1)]
for t in range(q):
qs[QL[t]].append((QR[t], t))
col = [0] * (n + 1)
for L in range(n, 0, -1):
mx = 0; s = 0
for r in range(L, n + 1):
x = a[r]
if x > mx:
mx = x
s += x
if 2 * mx < s:
col[r] += 1
if qs[L]:
pre = [0] * (n + 1); acc = 0
for r in range(L, n + 1):
acc += col[r]; pre[r] = acc
for R, t in qs[L]:
ans[t] = pre[R]
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()Cách 4Q = 1: chia để trị theo cây dài nhất + duyệt nửa nhỏ – O(N log² N) · 35%
Bây giờ dãy bất kỳ, nhưng chỉ có một câu hỏi (có thể coi là đếm trên cả dãy). Ý tưởng then chốt: gom các đoạn theo vị trí cây dài nhất.
Bước 1: mỗi đoạn có đúng một "trụ"
Với đoạn $[l, r]$, gọi trụ $m$ là vị trí cây dài nhất, nếu có nhiều cây cùng dài nhất thì lấy cây trái nhất. Đặt $Lm$ = vị trí gần nhất bên trái $m$ có $a \ge a_m$ (0 nếu không có), $Rm$ = vị trí gần nhất bên phải $m$ có $a > a_m$ ($N+1$ nếu không có). Khi đó $m$ là trụ của $[l, r]$ khi và chỉ khi $$Lm < l \le m \le r < Rm.$$ Hai mảng $Lm, Rm$ tính bằng ngăn xếp đơn điệu trong $O(N)$. Chú ý một bên dùng $\ge$, một bên dùng $>$: nếu cả hai bên cùng dùng $>$ thì đoạn có hai cây dài nhất bằng nhau sẽ bị đếm hai lần.
Bước 2: với trụ cố định, điều kiện trở nên đơn điệu
Khi trụ $m$ đã cố định thì $M = a_m$ là hằng số, điều kiện là $P_r - P_{l-1} > 2a_m$. Cố định $l$: vế trái tăng theo $r$, nên các $r$ tốt là một đoạn cuối $[r_0, Rm - 1]$, tìm $r_0$ bằng chặt nhị phân trên $P$. Tương tự, cố định $r$ thì các $l$ tốt là một đoạn đầu $[Lm + 1, l_0]$.
Hình 2. Ví dụ đề, trụ $m = 3$ (cây 12). Các đoạn nhận cây 3 làm trụ tạo thành một hình chữ nhật $l \in [1,3]$, $r \in [3,6]$; ô tốt ở mỗi hàng là một đoạn liền về bên phải. Cả 9 đoạn vây được của ví dụ đều có trụ là cây 3.
Bước 3: chỉ duyệt bên ít lựa chọn hơn
Nếu luôn duyệt mọi $l \in (Lm, m]$ thì với dãy tăng dần, $Lm = 0$ với mọi $m$: tổng chi phí $N^2/2$. Mẹo: so sánh $m - Lm$ (số lựa chọn của $l$) và $Rm - m$ (số lựa chọn của $r$), duyệt bên ít hơn và chặt nhị phân bên kia.
Em thử mô phỏng: mỗi bước là một trụ, khung bên dưới là bảng $(l, r)$ — vùng tô nhạt là các đoạn nhận trụ này, ô xanh là các đoạn tốt đã tìm được, ô vàng là mảnh vừa thêm.
Code Cách 4 trả lời từng câu hỏi bằng cách chạy lại toàn bộ thuật toán trên khúc $[L, R]$: đúng với mọi test, nhưng chỉ kịp khi $Q$ nhỏ.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Dem so doan tot trong b[1..k] bang chia de tri theo phan tu lon nhat + duyet nua nho
ll countGood(const vector<ll>& b, int k) {
vector<ll> P(k + 1, 0);
for (int i = 1; i <= k; i++) P[i] = P[i - 1] + b[i];
vector<int> lm(k + 1), rm(k + 1), st;
for (int i = 1; i <= k; i++) {
while (!st.empty() && b[st.back()] < b[i]) st.pop_back();
lm[i] = st.empty() ? 0 : st.back(); st.push_back(i);
}
st.clear();
for (int i = k; i >= 1; i--) {
while (!st.empty() && b[st.back()] <= b[i]) st.pop_back();
rm[i] = st.empty() ? k + 1 : st.back(); st.push_back(i);
}
ll cnt = 0;
for (int m = 1; m <= k; m++) {
int Lm = lm[m], Rm = rm[m];
ll lim = 2 * b[m];
if (m - Lm <= Rm - m) {
for (int l = Lm + 1; l <= m; l++) {
int r0 = upper_bound(P.begin() + m, P.begin() + Rm, P[l - 1] + lim) - P.begin();
cnt += Rm - r0; // r thuoc [r0, Rm-1]
}
} else {
for (int r = m; r < Rm; r++) {
int j = lower_bound(P.begin() + Lm, P.begin() + m, P[r] - lim) - P.begin() - 1;
cnt += j - Lm + 1; // l thuoc [Lm+1, j+1]
}
}
}
return cnt;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<ll> 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<ll> b(R - L + 2);
for (int i = L; i <= R; i++) b[i - L + 1] = a[i];
printf("%lld\n", countGood(b, R - L + 1));
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
def count_good(b, k):
# dem so doan tot trong b[1..k]: chia de tri theo phan tu lon nhat + duyet nua nho
P = [0] * (k + 1)
for i in range(1, k + 1):
P[i] = P[i - 1] + b[i]
lm = [0] * (k + 1); rm = [k + 1] * (k + 1)
st = []
for i in range(1, k + 1):
while st and b[st[-1]] < b[i]:
st.pop()
lm[i] = st[-1] if st else 0
st.append(i)
st = []
for i in range(k, 0, -1):
while st and b[st[-1]] <= b[i]:
st.pop()
rm[i] = st[-1] if st else k + 1
st.append(i)
cnt = 0
for m in range(1, k + 1):
Lm = lm[m]; Rm = rm[m]; lim = 2 * b[m]
if m - Lm <= Rm - m:
for l in range(Lm + 1, m + 1):
cnt += Rm - bisect_right(P, P[l - 1] + lim, m, Rm)
else:
for r in range(m, Rm):
cnt += bisect_left(P, P[r] - lim, Lm, m) - Lm
return cnt
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
out.append(count_good([0] + a[L:R + 1], R - L + 1))
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()Cách 5Ghép hai nửa: mảnh ngang, mảnh dọc và quét offline – O(N log² N + Q log N) · 100%
Nhìn lại Cách 4: nó không chỉ đếm mà còn chia tập các đoạn tốt thành $O(N \log N)$ mảnh rời nhau, mỗi mảnh có dạng rất đẹp trên bảng $(l, r)$:
- Mảnh ngang (khi duyệt bên trái): $l$ cố định, $r \in [x, y]$ (với $x = r_0$, $y = Rm - 1$).
- Mảnh dọc (khi duyệt bên phải): $r$ cố định, $l \in [x, y]$ (với $x = Lm + 1$, $y = l_0$).
Đây đúng là "dạng đẹp" mà Cách 3 cần! Câu hỏi $(L, R)$ = tổng đóng góp của mọi mảnh vào góc $l \ge L$, $r \le R$. Ta lại quét $L$ từ $N$ về 1 và dùng Fenwick theo chỉ số $r$:
Mảnh ngang $(l;\ x..y)$ chỉ có mặt khi $L \le l$ (kích hoạt lúc quét tới $L = l$). Nó đóng góp số $r \in [x, \min(y, R)]$, tức là $$\max(0, R - x + 1) - \max(0, R - y).$$ Mỗi số hạng có dạng "dốc" tại điểm $c$: $[c \le R] \cdot (R + 1 - c) = (R+1)\cdot[c \le R] - c\cdot[c \le R]$. Vậy ta giữ hai Fenwick: $A$ (cộng $\pm 1$ tại $c$) và $B$ (cộng $\pm c$ tại $c$), đóng góp = $(R+1)\cdot A(R) - B(R)$. Mảnh ngang = dốc $+1$ tại $c = x$ và dốc $-1$ tại $c = y + 1$.
Mảnh dọc $(r;\ x..y)$ đóng góp $[r \le R] \cdot \#\{l \in [x, y] : l \ge L\}$. Theo $L$: bằng 0 khi $L > y$; bằng $(y + 1) - L$ khi $x \le L \le y$; bằng $y - x + 1$ khi $L < x$. Đó là hàm bậc nhất từng khúc theo $L$: giữ hai Fenwick $C$ (hệ số tự do) và $D$ (hệ số của $L$) tại vị trí $r$. Lúc quét tới $L = y$: $C[r] \mathrel{+}= y + 1$, $D[r] \mathrel{+}= -1$. Lúc quét tới $L = x - 1$: $C[r] \mathrel{+}= -x$, $D[r] \mathrel{+}= +1$ (biến $(y + 1) - L$ thành hằng $y - x + 1$). Đóng góp = $C(R) + L \cdot D(R)$.
Mô phỏng dưới đây chạy lượt quét: bảng $(l, r)$ tô xanh các đoạn tốt đã "kích hoạt" ($l \ge L$), khung vàng là vùng của câu hỏi đang trả lời; các hàng $A, B, C, D$ là giá trị tại từng điểm (Fenwick chỉ giúp lấy tổng tiền tố nhanh).
Code đầy đủ. Mảng sự kiện ev[L] lưu: loại 0 = dốc $(c, \pm 1)$ vào $A, B$; loại 1 = $(r, x, y)$ cộng vào $C, D$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
vector<ll> A_, B_, C_, D_; // 4 cay Fenwick theo chi so r
void addAB(int c, ll s) { for (int i = c; i <= n; i += i & -i) { A_[i] += s; B_[i] += s * c; } }
void addCD(int r, ll x, ll y) { for (int i = r; i <= n; i += i & -i) { C_[i] += x; D_[i] += y; } }
int main() {
scanf("%d %d", &n, &q);
vector<ll> a(n + 2), P(n + 1, 0);
for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); P[i] = P[i - 1] + a[i]; }
// lm[m]: vi tri gan nhat ben trai co a >= a[m]; rm[m]: gan nhat ben phai co a > a[m]
vector<int> lm(n + 1), rm(n + 1), st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.back()] < a[i]) st.pop_back();
lm[i] = st.empty() ? 0 : st.back(); st.push_back(i);
}
st.clear();
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
rm[i] = st.empty() ? n + 1 : st.back(); st.push_back(i);
}
// su kien gan voi thoi diem quet L: loai 0 = (c, s) vao A,B; loai 1 = (r, x, y) vao C,D
vector<vector<array<ll, 4>>> ev(n + 1);
for (int m = 1; m <= n; m++) {
int Lm = lm[m], Rm = rm[m]; // a[m] lon nhat (trai nhat) cua [l, r] <=> Lm < l <= m <= r < Rm
ll lim = 2 * a[m];
if (m - Lm <= Rm - m) { // duyet ben trai (nua nho)
for (int l = Lm + 1; l <= m; l++) {
int r0 = upper_bound(P.begin() + m, P.begin() + Rm, P[l - 1] + lim) - P.begin();
if (r0 < Rm) { // r thuoc [r0, Rm-1] deu tot
ev[l].push_back({0, r0, 1, 0});
if (Rm <= n) ev[l].push_back({0, Rm, -1, 0});
}
}
} else { // duyet ben phai (nua nho)
for (int r = m; r < Rm; r++) {
int j = lower_bound(P.begin() + Lm, P.begin() + m, P[r] - lim) - P.begin() - 1;
if (j >= Lm) { // l thuoc [Lm+1, j+1] deu tot
int l1 = Lm + 1, l2 = j + 1;
ev[l2].push_back({1, r, l2 + 1, -1});
if (l1 >= 2) ev[l1 - 1].push_back({1, r, -l1, 1});
}
}
}
}
vector<vector<pair<int, int>>> qs(n + 1);
vector<ll> ans(q);
for (int t = 0; t < q; t++) { int L, R; scanf("%d %d", &L, &R); qs[L].push_back({R, t}); }
A_.assign(n + 1, 0); B_.assign(n + 1, 0); C_.assign(n + 1, 0); D_.assign(n + 1, 0);
for (int L = n; L >= 1; L--) {
for (auto& e : ev[L]) {
if (e[0] == 0) addAB((int)e[1], e[2]);
else addCD((int)e[1], e[2], e[3]);
}
for (auto& [R, t] : qs[L]) {
ll sa = 0, sb = 0, sc = 0, sd = 0;
for (int i = R; i > 0; i -= i & -i) { sa += A_[i]; sb += B_[i]; sc += C_[i]; sd += D_[i]; }
ans[t] = (ll)(R + 1) * sa - sb + sc + (ll)L * sd;
}
}
for (int t = 0; t < q; t++) printf("%lld\n", ans[t]);
return 0;
}import sys
from bisect import bisect_left, bisect_right
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [0] * (n + 2)
P = [0] * (n + 1)
s = 0
for i in range(1, n + 1):
v = int(data[1 + i]); a[i] = v; s += v; P[i] = s
# lm[m]: gan nhat ben trai co a >= a[m]; rm[m]: gan nhat ben phai co a > a[m]
lm = [0] * (n + 1); rm = [n + 1] * (n + 1)
st = []
for i in range(1, n + 1):
ai = a[i]
while st and a[st[-1]] < ai:
st.pop()
lm[i] = st[-1] if st else 0
st.append(i)
st = []
for i in range(n, 0, -1):
ai = a[i]
while st and a[st[-1]] <= ai:
st.pop()
rm[i] = st[-1] if st else n + 1
st.append(i)
# su kien theo thoi diem quet L (danh sach lien ket tren mang phang)
h0 = [-1] * (n + 1); n0 = []; c0 = []; s0 = [] # loai 0: (c, s) vao A, B
h1 = [-1] * (n + 1); n1 = []; r1 = []; x1 = []; y1 = [] # loai 1: (r, x, y) vao C, D
for m in range(1, n + 1):
Lm = lm[m]; Rm = rm[m]; lim = 2 * a[m]
if m - Lm <= Rm - m: # duyet ben trai (nua nho)
for l in range(Lm + 1, m + 1):
r0 = bisect_right(P, P[l - 1] + lim, m, Rm)
if r0 < Rm: # r thuoc [r0, Rm-1] deu tot
n0.append(h0[l]); h0[l] = len(c0); c0.append(r0); s0.append(1)
if Rm <= n:
n0.append(h0[l]); h0[l] = len(c0); c0.append(Rm); s0.append(-1)
else: # duyet ben phai (nua nho)
l1 = Lm + 1
for r in range(m, Rm):
j = bisect_left(P, P[r] - lim, Lm, m) - 1
if j >= Lm: # l thuoc [Lm+1, j+1] deu tot
l2 = j + 1
n1.append(h1[l2]); h1[l2] = len(r1); r1.append(r); x1.append(l2 + 1); y1.append(-1)
if Lm >= 1:
n1.append(h1[Lm]); h1[Lm] = len(r1); r1.append(r); x1.append(-l1); y1.append(1)
qh = [-1] * (n + 1); qn = [0] * q; qr = [0] * q
p = 2 + n
for t in range(q):
L = int(data[p]); R = int(data[p + 1]); p += 2
qn[t] = qh[L]; qh[L] = t; qr[t] = R
A = [0] * (n + 1); B = [0] * (n + 1); C = [0] * (n + 1); D = [0] * (n + 1)
ans = [0] * q
for L in range(n, 0, -1):
e = h0[L]
while e >= 0:
c = c0[e]; sg = s0[e]; sc = sg * c; i = c
while i <= n:
A[i] += sg; B[i] += sc; i += i & -i
e = n0[e]
e = h1[L]
while e >= 0:
i = r1[e]; x = x1[e]; y = y1[e]
while i <= n:
C[i] += x; D[i] += y; i += i & -i
e = n1[e]
t = qh[L]
while t >= 0:
R = qr[t]; i = R; sa = sb = sc = sd = 0
while i:
sa += A[i]; sb += B[i]; sc += C[i]; sd += D[i]; i &= i - 1
ans[t] = (R + 1) * sa - sb + sc + L * sd
t = qn[t]
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()- Cây bằng nhau: trụ phải được chọn duy nhất (cây dài nhất trái nhất: bên trái dùng $\ge$, bên phải dùng $>$). Dùng $>$ cả hai bên sẽ đếm trùng.
- Dấu bằng: $2M = S$ là đa giác dẹt, KHÔNG tính. Bộ test có rất nhiều đoạn kiểu $(1, 1, 2)$, $(x, x, 2x)$.
- Tràn số: tổng tiền tố tới $10^{14}$, đáp án tới $5 \cdot 10^9$, Fenwick $B$ tới $\approx 10^{11}$: tất cả phải là
long long. - Phải duyệt nửa nhỏ: nếu luôn duyệt bên trái, một dãy tăng dài sẽ làm thuật toán thành $O(N^2 \log N)$.
Chạy tay từng dòng của code C++ trên (để dễ theo dõi: $N \le 10$, $Q \le 6$):
Bộ test chấm "bắt" những lỗi nào?
Bộ test có 40 test, mỗi subtask 8 test. Các test lớn có đủ kiểu: cây gần bằng nhau (đáp án tới $5 \cdot 10^9$), nhiều cây bằng nhau, rất nhiều đoạn có $2M = S$, "gai" dài phá hỏng đoạn tốt, dãy tăng dài 40000–50000 phần tử, cây Cartesian cân bằng.
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – duyệt mọi đoạn | 8/8 | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – O(N²) gom theo L | 8/8 | 8/8 | TLE | TLE | TLE | 25 |
| Cách 3 – dãy không giảm + Fenwick | 8/8 | 8/8 | 8/8 | TLE | TLE | 45 |
| Cách 4 – chia để trị theo max cho từng câu hỏi | 8/8 | TLE | TLE | 8/8 | TLE | 35 |
| Cách 5 – mảnh ngang/dọc + quét offline (lời giải đầy đủ) | 8/8 | 8/8 | 8/8 | 8/8 | 8/8 | 100 |
| Sai: hai phía cùng dùng ">" (đếm trùng cây dài nhất bằng nhau) | 3/8 | 3/8 | 0/8 | 1/8 | 2/8 | 20 |
| Sai: chấp nhận 2·max = tổng | 3/8 | 3/8 | 0/8 | 1/8 | 2/8 | 20 |
| Sai: Fenwick và đáp án kiểu int | 8/8 | 8/8 | 0/8 | 0/8 | 0/8 | 25 |
| Sai: luôn duyệt bên trái (không chọn nửa nhỏ) | 8/8 | 8/8 | 5/8 | 1/8 | TLE | 40,62 |
| Sai: tin "đoạn tốt mở rộng vẫn tốt" (hai con trỏ) | 4/8 | 2/8 | 6/8 | 2/8 | 1/8 | 33,75 |
Để ý: ví dụ trong đề được chọn sao cho cả năm lời giải sai ở trên đều in đúng 9 2 1 — trong ví dụ, mọi đoạn tốt đều chứa cây 12 và mở rộng đoạn tốt thì vẫn tốt, không có hai cây dài nhất bằng nhau, không có đoạn nào $2M = S$. Qua ví dụ chưa nói lên điều gì cả!
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,28 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3,5 giây. Lời giải chuẩn được đối chiếu với chương trình vét cạn (sắp xếp các cạnh rồi kiểm tra trực tiếp) trên 1300 test nhỏ ngẫu nhiên có rất nhiều giá trị bằng nhau, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và chạy tối đa khoảng 2,6 giây ngay cả trên CPython.
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