Công Ty (HSG12 Hà Nội 2023 Vòng 1 – Bài 4)
Đề bài
Câu IV. CÔNG TY (3 điểm)
Một công ty gồm $N$ người được đánh số từ $1$ tới $N$. Tổng giám đốc của công ty được đánh số là $1$, mỗi người từ $2$ tới $N$ có đúng một cấp trên trực tiếp của mình.
Nếu $i$ là cấp trên trực tiếp của $j$, ta gọi $i$ là quản lý của $j$. Nếu $i$ là quản lý của $j$ thì $i$ cũng là quản lý của những người mà $j$ quản lý. Không có trường hợp $i$ là quản lý của $j$ đồng thời $j$ là quản lý của $i$.
Công ty có chế độ lương thưởng rất đặc biệt, người thứ $i$ có lương là $a_i$, người cấp dưới có thể có lương cao hơn người quản lý.
Công ty muốn tổ chức một sự kiện cho toàn bộ công ty. Nhưng nếu hai người $u$ và $v$ tham gia, trong đó, $u$ là quản lý của $v$ mà lương của $u$ không cao hơn lương của $v$ $(a_u \le a_v)$ thì sẽ gây ra bất hòa. Công ty muốn chọn ra được nhiều người nhất tham gia sự kiện mà không có sự bất hòa nào.
Phòng tổ chức sự kiện đã lên $Q$ giả định như sau: Xét người $u$ $(1 \le u \le N)$, chọn ra một số người mà $u$ là quản lý (có thể chọn hoặc không chọn $u$) để tham gia sự kiện sao cho:
- Tổng số người được chọn là lớn nhất;
- Không có sự bất hoà nào giữa những người được chọn.
Yêu cầu: Với mỗi giả định, in ra số người nhiều nhất có thể chọn để tham gia sự kiện.
Dữ liệu vào từ file văn bản CONGTY.INP:
- Dòng đầu tiên chứa hai số nguyên dương $N$ và $Q$ $(1 \le N, Q \le 2 \times 10^5)$;
- Dòng thứ hai gồm $N$ số nguyên dương, số thứ $i$ là $a_i$ mô tả mức lương của người thứ $i$ $(1 \le a_i \le 10^9)$;
- Dòng thứ ba gồm $N - 1$ số nguyên dương, số thứ $i$ là $p_i$ mô tả $p_i$ là cấp trên trực tiếp của $i + 1$ $(1 \le p_i \le N)$;
- $Q$ dòng sau, dòng thứ $i$ gồm một số nguyên dương $u_i$ $(1 \le u_i \le N)$, mô tả giả định thứ $i$.
Kết quả ghi ra file văn bản CONGTY.OUT: Với mỗi giả định, in ra kết quả tương ứng.
Ràng buộc:
- Có $15\%$ số test ứng với $15\%$ số điểm của bài thỏa mãn: $N \le 15$; $Q = 1$;
- $20\%$ số test khác ứng với $20\%$ số điểm của bài thỏa mãn: nếu $u$ là quản lý của $v$ thì $a_u \gt a_v$;
- $15\%$ số test khác ứng với $15\%$ số điểm của bài thỏa mãn: $i$ là cấp trên trực tiếp của $i + 1$ $(1 \le i \lt N)$;
- $15\%$ số test khác ứng với $15\%$ số điểm của bài thỏa mãn: $N \le 1000$; $a_i \le 100$;
- $20\%$ số test khác ứng với $20\%$ số điểm của bài thỏa mãn: $N \le 10^5$; $a_i \le 100$;
- $15\%$ số test còn lại ứng với $15\%$ số điểm của bài không có ràng buộc gì thêm.
Lưu ý: đề thi gốc đọc/ghi file CONGTY.INP / CONGTY.OUT; nộp trên web (HNOJ) thì đọc từ bàn phím và in ra màn hình. Code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng.
6 3
8 4 2 7 1 3
1 1 3 2 3
1
3
45
2
16 2
7 5 6 4 3 1
1 1 3 3 5
3
14
6Giải thích (theo đề): Hình vẽ minh hoạ ví dụ 1 như Hình 3 ở trên.
- Ví dụ 1 – với giả định thứ nhất, chọn các nhân viên: $1, 2, 5, 4, 6$;
- Ví dụ 1 – với giả định thứ hai, chọn các nhân viên: $4, 6$;
- Ví dụ 1 – với giả định thứ ba, chọn nhân viên: $4$.
- Ví dụ 2 – với giả định thứ nhất, chọn các nhân viên: $3, 4, 5, 6$;
- Ví dụ 2 – với giả định thứ hai, chọn các nhân viên: $1, 2, 3, 4, 5, 6$.
Lời mở đầu
Đây là bài 4 – bài khó nhất – trong đề thi học sinh giỏi Tin học lớp 12 thành phố Hà Nội năm 2023 (vòng 1). Đề có tới 6 subtask, mỗi subtask là một "bậc thang" kiến thức: vét cạn bitmask → đếm cây con → dãy con tăng dài nhất → QHĐ trên cây → tối ưu QHĐ → gộp set (hoặc HLD). Mình sẽ đi lần lượt từng subtask để các bạn thấy rõ ý tưởng nào dẫn tới ý tưởng nào nha. Bài khá dài, các bạn cứ từ từ đọc 😇.
Mình giải thích kỹ thêm ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Công ty chính là một cây có gốc là $1$, "$u$ là quản lý của $v$" nghĩa là $u$ là tổ tiên của $v$. Điều kiện không bất hoà nói rằng: trong những người được chọn, nếu $u$ là tổ tiên của $v$ thì phải có $a_u \gt a_v$ – tức là đi từ trên xuống dưới, lương phải giảm ngặt. Còn hai người không có quan hệ tổ tiên – con cháu (ví dụ hai nhánh khác nhau) thì lương thế nào cũng được. Mỗi giả định $u$ hỏi: chỉ được chọn trong cây con gốc $u$, chọn được nhiều nhất bao nhiêu người.
- Ví dụ 1, giả định $u = 1$: chọn $\{1, 2, 5, 4, 6\}$. Kiểm tra: $1 (8) \to 2 (4) \to 5 (1)$ giảm dần ✔; $1 (8) \to 4 (7)$ ✔; $1 (8) \to 6 (3)$ ✔; $4$ và $6$ là anh em nên không sao. Không thể chọn thêm $3$ (lương $2$) vì $3$ là quản lý của $4$ mà $2 \le 7$.
- Giả định $u = 3$: cây con gồm $\{3, 4, 6\}$; chọn $3$ thì không chọn được $4, 6$ (lương $2$ quá thấp), nên tốt nhất là chọn $\{4, 6\}$: $2$ người.
- Giả định $u = 4$: cây con chỉ có mình $4$ → $1$ người.
- Ví dụ 2: mọi quản lý đều có lương cao hơn cấp dưới, nên chọn được hết cả cây con: $u = 3$ có $4$ người, $u = 1$ có $6$ người.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Duyệt mọi cách chọn bằng bitmask – O(Q · 2^N · N)
Ở subtask này, $N \le 15$ và $Q = 1$, nên đối với mỗi truy vấn, ta duyệt trâu hết những lựa chọn có thể và kiểm tra xem có thoả mãn điều kiện của đề bài không. Mỗi cách chọn là một tập con của $N$ người, biểu diễn bằng một số $j$ từ $0$ đến $2^N - 1$: bit thứ $k - 1$ của $j$ bật nghĩa là người $k$ được chọn (hàm testBit).
Với mỗi cách chọn, ta gọi dfs(1) trên toàn cây để tính 2 thứ cho mỗi đỉnh $u$:
sub[u]: số người được chọn trong cây con gốc $u$. Cách chọn hợp lệ cho giả định $w$ thì mọi người được chọn phải nằm trong cây con của $w$, tức làsub[w] == sl(vớisllà tổng số người được chọn).ded[u]: lương cao nhất của những người được chọn trong cây con gốc $u$ (chưa chọn ai thì là $-10^9$). Nếu $u$ được chọn màa[u] <= ded[u](tính trước khi gộp chính $u$) thì có một cấp dưới của $u$ được chọn với lương không thấp hơn $u$ → bất hoà, đặtok = 0.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], p[200005], w[200005];
vector<int> ad[200005];
bool testBit(int x, int k){
return x & (1 << k); // check bit k có bật không
}
bool vis[200005];
int sub[200005], ded[200005];
bool ok = 0;
void dfs(int u, int need){
sub[u] = vis[u];
ded[u] = -1e9;
for (auto j : ad[u]){
dfs(j, need);
sub[u] += sub[j];
ded[u] = max(ded[u], ded[j]);
}
if (vis[u] && a[u] <= ded[u]) ok = 0;
if (vis[u]) ded[u] = max(ded[u], a[u]);
}
signed main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
ad[p[i]].push_back(i);
}
for (int i = 1; i <= q; i ++){
cin >> w[i];
int mx = 0;
for (int j = 0; j < (1 << n); j ++){
int sl = 0;
ok = 1;
for (int k = 1; k <= n; k ++){
vis[k] = testBit(j, k - 1);
sl += vis[k];
}
dfs(1, w[i]);
if (sub[w[i]] == sl && ok) mx = max(mx, sl);
}
cout << mx << endl;
}
}import sys
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
a = [0] + [int(x) for x in d[2:2 + n]]
p = [0, 0] + [int(x) for x in d[2 + n:1 + 2 * n]]
ad = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
ad[p[i]].append(i)
# thứ tự duyệt: cha trước con, đảo ngược lại để tính con trước cha
order = [1]
for u in order:
order.extend(ad[u])
order.reverse()
out = []
for w in d[1 + 2 * n:1 + 2 * n + q]:
w = int(w)
mx = 0
for mask in range(1 << n):
vis = [False] + [(mask >> (k - 1)) & 1 == 1 for k in range(1, n + 1)]
sl = sum(vis)
ok = True
sub = [0] * (n + 1)
ded = [-10**9] * (n + 1) # lương lớn nhất của người được chọn ở dưới u
for u in order:
sub[u] += vis[u]
if vis[u] and a[u] <= ded[u]:
ok = False
if vis[u]:
ded[u] = max(ded[u], a[u])
if u != 1:
sub[p[u]] += sub[u]
ded[p[u]] = max(ded[p[u]], ded[u])
if sub[w] == sl and ok:
mx = max(mx, sl)
out.append(mx)
print('\n'.join(map(str, out)))
main()Trong khung chạy tay, mỗi cách chọn $j$ mình gom vòng for k (gán vis) và lời gọi dfs lại thành 1 bước, có giải thích vì sao hợp lệ / không hợp lệ. Hình cây: xanh = được chọn và nằm trong cây con của $w$, xám = được chọn nhưng nằm ngoài cây con của $w$, đỏ = người bị bất hoà với cấp dưới:
Đánh giá độ phức tạp của cách làm này:
- Không gian: các mảng cỡ $N$: $O(N)$.
- Thời gian: mỗi truy vấn có $2^N$ cách chọn, mỗi cách chọn tốn $O(N)$ để gán
visvà chạydfs: $O(Q \cdot 2^N \cdot N)$. Với $N = 15$, $Q = 1$ thì chỉ khoảng $5 \cdot 10^5$ phép tính.
Subtask 2Quản lý luôn lương cao hơn: đếm cây con – O(N + Q)
Nếu $a_u \gt a_v$ với mọi $v$ mà $u$ quản lý thì không bao giờ có bất hoà, ta nhận xét cách chọn tối ưu tại đỉnh $u$ sẽ là lấy hết những đỉnh trong cây con gốc $u$. Khi này, kết quả sẽ là số lượng đỉnh trong cây con gốc $u$. Đến đây, chúng ta chỉ cần dfs sẵn để tính trước số lượng đỉnh sub[u] của các cây con gốc $u$:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], p[200005], w[200005];
vector<int> ad[200005];
int sub[200005];
void dfs(int u){
sub[u] ++;
for (auto j : ad[u]){
dfs(j);
sub[u] += sub[j];
}
}
signed main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
ad[p[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= q; i ++){
cin >> w[i];
cout << sub[w[i]] << endl;
}
}import sys
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
p = [0, 0] + [int(x) for x in d[2 + n:1 + 2 * n]]
ad = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
ad[p[i]].append(i)
order = [1]
for u in order:
order.extend(ad[u])
sub = [1] * (n + 1)
for u in reversed(order): # con được tính xong trước cha
if u != 1:
sub[p[u]] += sub[u]
ws = d[1 + 2 * n:1 + 2 * n + q]
print('\n'.join(str(sub[int(w)]) for w in ws))
main()Bản Python không dùng đệ quy (cây có thể là đường thẳng dài $2 \cdot 10^5$, đệ quy sâu như vậy Python sẽ lỗi): mình lấy thứ tự BFS từ gốc (cha luôn đứng trước con) rồi duyệt ngược lại để cộng sub của con vào cha. Khung chạy tay bản C++ (vòng tròn vàng = đỉnh đang ở trong dfs, số dưới mỗi đỉnh = sub):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian:
dfsđi qua mỗi đỉnh một lần $O(N)$, mỗi truy vấn $O(1)$: tổng $O(N + Q)$.
dfs đệ quy sâu $2 \cdot 10^5$ tầng. Các hệ thống chấm thi thường cho bộ nhớ ngăn xếp (stack) lớn nên chạy được, nhưng trên máy cá nhân (giới hạn stack mặc định 8 MB của Linux) thì chương trình có thể bị lỗi segmentation fault – mình thử thì đúng là như vậy, phải chạy lệnh ulimit -s unlimited trước mới chạy được. Các code đệ quy ở các subtask sau cũng vậy nha.Subtask 3Cây là đường thẳng: dãy con tăng dài nhất – O(N log N + Q)
Đề bài cho chúng ta rằng $i$ là sếp trực tiếp của $i + 1$. Điều này khiến cây trở thành một dạng đường thẳng $1 \to 2 \to \cdots \to N$ và chúng ta có thể quy sang dãy. Với giả định $w$, ta được chọn trong các người $w, w + 1, \ldots, N$, và vì ai đứng trước cũng là quản lý của người đứng sau, nên dãy lương của những người được chọn (theo thứ tự chỉ số) phải giảm ngặt. Đảo ngược mảng $a$ lại thì thành tìm dãy con tăng ngặt dài nhất trong $N - w + 1$ phần tử đầu của mảng đã đảo.
Đến đây, bài toán chuyển về thành bài toán tìm dãy con tăng dần dài nhất, có thể được giải bằng chặt nhị phân và tính trước các mảng kết quả cho từng tiền tố. Đến khi truy vấn ta chỉ cần truy xuất kết quả của đỉnh đó.
- Gọi $g_x$ (trong code là
dp_[x]) là phần tử có giá trị nhỏ nhất sao cho nó là điểm kết thúc của một dãy con tăng độ dài $x$ nào đó (chưa có thì $g_x = +\infty$, quy ước $g_0 = -\infty$). Mảng $g$ luôn tăng dần. - Xét phần tử $a_i$: chặt nhị phân trên $g$ để tìm ra độ dài $y$ lớn nhất sao cho $g_y \lt a_i$. Khi này, dãy con tăng dài nhất kết thúc tại $i$ có độ dài $len = y + 1$. Ta cập nhật lại $g_{y+1} = \min(g_{y+1}, a_i)$.
- $dp_i = \max(dp_{i-1}, len)$ là độ dài dãy con tăng dài nhất trong $i$ phần tử đầu. Giả định $w$ có đáp án $dp_{N - w + 1}$.
Các bạn nhập dãy lương $a_1, a_2, \ldots, a_N$ (từ giám đốc xuống nhân viên cuối) vào khung minh hoạ để xem mảng $g$ thay đổi thế nào nhé:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], w[200005], dp_[200005], dp[200005], p[200005];
signed main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
}
for (int i = 0; i <= n; i ++) dp_[i] = 1e9;
dp_[0] = -1e9;
reverse(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++){
int l = 0, r = i, mid;
int len = 0;
while (l <= r){
mid = (l + r) / 2;
if (dp_[mid] < a[i]){
l = mid + 1;
len = max(len, mid);
}
else{
r = mid - 1;
}
}
len += 1;
dp[i] = max(dp[i - 1], len);
dp_[len] = min(dp_[len], a[i]);
}
for (int i = 1; i <= q; i ++){
cin >> w[i];
cout << dp[n - w[i] + 1] << endl;
}
}import sys
from bisect import bisect_left
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
a = [int(x) for x in d[2:2 + n]]
a.reverse() # đi từ nhân viên n ngược lên 1
g = [] # g[x - 1]: giá trị cuối nhỏ nhất của dãy tăng dài x
dp = [0] * (n + 1)
for i in range(1, n + 1):
k = bisect_left(g, a[i - 1])
if k == len(g):
g.append(a[i - 1])
else:
g[k] = a[i - 1]
dp[i] = max(dp[i - 1], k + 1)
ws = d[1 + 2 * n:1 + 2 * n + q]
print('\n'.join(str(dp[n - int(w) + 1]) for w in ws))
main()Code C++ tự viết chặt nhị phân trên dp_ (tìm mid lớn nhất có dp_[mid] < a[i]), còn bản Python dùng bisect_left cho gọn – hai cách tương đương nhau. Mảng p vẫn được đọc nhưng không dùng tới vì cây đã chắc chắn là đường thẳng.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: mỗi phần tử chặt nhị phân $O(\log N)$: tổng $O(N \log N + Q)$.
Subtask 4QHĐ trên cây theo mức lương – O(N · mxval²)
Từ subtask này trở đi, cây có hình dạng bất kỳ. Ở subtask 4 và 5, lương $a_i \le 100$ rất nhỏ nên ta có thể đưa luôn mức lương vào trạng thái quy hoạch động.
Ta có $v$ là nút con của $u$, ta sẽ có các trường hợp sau:
- $val \ne a_u$: khi này ta không chọn $u$ (nếu chọn $u$ thì lương lớn nhất là $a_u$, rơi vào trường hợp dưới). Với mỗi con $v$, số lượng tối đa đỉnh của cây con gốc $v$ có thể đóng góp cho lựa chọn của $dp[u][val]$ chính là $\max\limits_{y \le val} dp[v][y]$. Vì $u$ không được chọn và các cây con của những đứa con khác nhau không có quan hệ quản lý với nhau, nên không có trường hợp không thoả mãn điều kiện nào phát sinh: $dp[u][val] = \sum_{v} \max_{y \le val} dp[v][y]$ Độ phức tạp xử lý mỗi ô: $O(mxval)$ cho mỗi con.
- $val = a_u$:
- Trường hợp 1: không chọn đỉnh $u$ vào trong lựa chọn tối ưu, khi này ta xử lý như trường hợp $val \ne a_u$ (biến
sustrong code): $sus = \sum_v \max_{y \le a_u} dp[v][y]$. - Trường hợp 2: chọn đỉnh $u$, tương tự trường hợp $val \ne a_u$ chỉ khác là phải có $y \lt val$ mới thoả mãn điều kiện (cấp dưới phải có lương thấp hơn hẳn $u$): $1 + \sum_v \max_{y \lt a_u} dp[v][y]$.
- Trường hợp 1: không chọn đỉnh $u$ vào trong lựa chọn tối ưu, khi này ta xử lý như trường hợp $val \ne a_u$ (biến
Ta cần duyệt qua $N$ đỉnh, mỗi con $v$ duyệt $mxval$ giá trị $val$, mỗi giá trị lại duyệt $O(mxval)$ để lấy max, nên độ phức tạp sẽ là $O(N \cdot mxval^2)$. Ví dụ với ví dụ 1 của đề: lá $5$ (lương $1$) có $dp[5][1] = 1$; đỉnh $2$ (lương $4$) có $dp[2][4] = \max(1 + \max_{y \lt 4} dp[5][y], \ldots) = 2$ (chọn cả $2$ và $5$).
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], w[200005], dp[1005][105], p[200005];
vector<int> ad[1005];
void dfs(int u){
dp[u][a[u]] ++;
int sus = 0;
for (auto v : ad[u]){
dfs(v);
for (int j = 0; j <= 100; j ++){
if (j == a[u]){
int mx = 0;
for (int k = 1; k <= j; k ++){
mx = max(mx, dp[v][k]);
}
sus += mx;
mx = 0;
for (int k = 1; k < j; k ++){
mx = max(mx, dp[v][k]);
}
dp[u][a[u]] += mx;
continue;
}
int mx = 0;
for (int k = 1; k <= j; k ++){
mx = max(mx, dp[v][k]);
}
dp[u][j] += mx;
}
}
dp[u][a[u]] = max(dp[u][a[u]], sus);
}
signed main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
ad[p[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= q; i ++){
cin >> w[i];
int res = 0;
for (int j = 1; j <= 100; j ++){
res = max(res, dp[w[i]][j]);
}
cout << res << endl;
}
}import sys
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
a = [0] + [int(x) for x in d[2:2 + n]]
p = [0, 0] + [int(x) for x in d[2 + n:1 + 2 * n]]
ad = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
ad[p[i]].append(i)
order = [1]
for u in order:
order.extend(ad[u])
dp = [[0] * 101 for _ in range(n + 1)]
for u in reversed(order): # duyệt con trước cha (thay cho dfs đệ quy)
dp[u][a[u]] += 1
sus = 0
for v in ad[u]:
for j in range(101):
if j == a[u]:
sus += max(dp[v][1:j + 1], default=0)
dp[u][a[u]] += max(dp[v][1:j], default=0)
continue
dp[u][j] += max(dp[v][1:j + 1], default=0)
dp[u][a[u]] = max(dp[u][a[u]], sus)
ws = d[1 + 2 * n:1 + 2 * n + q]
print('\n'.join(str(max(dp[int(w)][1:])) for w in ws))
main()Vòng for j chạy đủ $101$ giá trị nên trong khung chạy tay mình gom các giá trị $j \ne a_u$ lại, chỉ tách riêng $j = a_u$. Để bảng dễ nhìn, em nhập lương $a_i \le 9$ nhé (cột "≥10" đại diện cho mọi $j$ từ $10$ tới $100$ vì chúng bằng nhau):
Đánh giá độ phức tạp của cách làm này:
- Không gian: bảng $dp$ cỡ $N \times 101$: $O(N \cdot mxval)$.
- Thời gian: $O(N \cdot mxval^2)$ – với $N = 1000$, $mxval = 100$ là cỡ $10^7$ phép tính.
dp[1005][105] và ad[1005] đúng theo giới hạn $N \le 1000$, nên nộp cho test lớn hơn sẽ bị tràn mảng. Sang subtask 5 mình phải tăng lên dp[200005][105].Subtask 5Tối ưu QHĐ bằng max cộng dồn – O(N · mxval)
Tương tự với subtask 4, nhưng ta sẽ tối ưu hơn việc xử lý $val \ne a_u$. Điểm lãng phí ở subtask 4 là với mỗi $val$ ta lại duyệt lại từ đầu để tính $\max_{y \le val} dp[v][y]$. Ta nhận thấy rằng, ta có thể duyệt cập nhật $dp[u][val]$ đối với mỗi $v$ theo $val$ tăng dần. Khi đó, ta có thể cập nhật $\max(dp[v][y])$ sau mỗi lần tăng $val$:
mx $= \max_{y \le j} dp[v][y]$. Khi $j$ tăng lên $1$ chỉ cần mx = max(mx, dp[v][j]) – $O(1)$ thay vì $O(mxval)$. Riêng tại $j = a_u$ cần thêm $\max_{y \lt a_u} dp[v][y]$, ta tính bằng một vòng lặp riêng (biến mx_), nhưng vòng này chỉ chạy một lần cho mỗi con nên không ảnh hưởng độ phức tạp.Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], w[200005], dp[200005][105], p[200005];
vector<int> ad[200005];
void dfs(int u){
dp[u][a[u]] ++;
int sus = 0;
for (auto v : ad[u]){
dfs(v);
int mx = 0;
for (int j = 0; j <= 100; j ++){
if (j == a[u]){
mx = max(mx, dp[v][j]);
sus += mx;
int mx_ = 0;
for (int k = 1; k < j; k ++){
mx_ = max(mx_, dp[v][k]);
}
dp[u][a[u]] += mx_;
continue;
}
mx = max(mx, dp[v][j]);
dp[u][j] += mx;
}
}
dp[u][a[u]] = max(dp[u][a[u]], sus);
}
signed main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i ++){
cin >> a[i];
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
ad[p[i]].push_back(i);
}
dfs(1);
for (int i = 1; i <= q; i ++){
cin >> w[i];
int res = 0;
for (int j = 1; j <= 100; j ++){
res = max(res, dp[w[i]][j]);
}
cout << res << endl;
}
}import sys
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
a = [0] + [int(x) for x in d[2:2 + n]]
p = [0, 0] + [int(x) for x in d[2 + n:1 + 2 * n]]
ad = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
ad[p[i]].append(i)
order = [1]
for u in order:
order.extend(ad[u])
dp = [None] * (n + 1)
res = [0] * (n + 1)
for u in reversed(order): # duyệt con trước cha (thay cho dfs đệ quy)
cur = [0] * 101
au = a[u]
cur[au] += 1
sus = 0
for v in ad[u]:
dv = dp[v]
mx = 0
for j in range(101):
if dv[j] > mx:
mx = dv[j]
if j == au:
sus += mx
cur[au] += max(dv[1:j], default=0)
continue
cur[j] += mx
dp[v] = None # dp của con không cần nữa, giải phóng bộ nhớ
cur[au] = max(cur[au], sus)
dp[u] = cur
res[u] = max(cur[1:])
ws = d[1 + 2 * n:1 + 2 * n + q]
print('\n'.join(str(res[int(w)]) for w in ws))
main()Bản Python duyệt cây không đệ quy (thứ tự BFS đảo ngược) và giải phóng dp của con sau khi dùng xong cho đỡ tốn bộ nhớ. Khung chạy tay bản C++ (vẫn gom các giá trị $j \ne a_u$):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N \cdot mxval)$ – mảng
dp[200005][105]kiểuintkhoảng 84 MB. - Thời gian: mỗi cạnh cha – con tốn $O(mxval)$: tổng $O(N \cdot mxval)$, với $N = 10^5$ là khoảng $10^7$ phép tính.
Subtask 6Mang "dãy con tăng dài nhất" lên cây + gộp set – O(N log² N)
Bài này có thể giải bằng hai lời giải: gộp set (phần này) và HLD (phần sau). Mình trình bày cách gộp set trước vì code ngắn và đẹp hơn nhiều.
Ôn lại bài toán dãy con tăng dài nhất
Chúng ta thấy, nếu xét cây có dạng đường thẳng thì bài toán của chúng ta gần như giống bài toán LIS (dãy con tăng dài nhất) như subtask 3. Ta ôn lại 1 cách giải của bài toán này:
Bài toán: Cho 1 dãy các số $a_1, a_2, a_3, \ldots, a_n$. Với mỗi $i$ thoả mãn $1 \le i \le n$, ta cần tìm độ dài dãy con tăng dài nhất trong $i$ phần tử đầu của dãy $a$.
Lời giải: Gọi $dp[i]$ là độ dài dãy con tăng dài nhất mà kết thúc tại phần tử $i$. Dễ thấy $dp[i] = \max(dp[j] + 1)$ với $j \lt i$ và $a_j \lt a_i$. Từ đây ta có thể giải được trong $O(n^2)$. Để tối ưu, khi xét đến phần tử $i$, gọi $startOf[x]$ là giá trị cuối cùng nhỏ nhất của một dãy con tăng có độ dài $x$ (nếu không có dãy có độ dài $x$ thì quy ước $startOf[x] = +\infty$). Ta có thể thấy rằng, mảng $startOf$ luôn là mảng không giảm, vì với một dãy con tăng độ dài $x$, khi bỏ phần tử cuối ta luôn có một dãy con tăng có độ dài $x - 1$ và phần tử cuối nhỏ hơn. Do vậy nên ta có thể tìm kiếm nhị phân giá trị $y$ lớn nhất thoả mãn $startOf[y] \lt a_i$, và đặt $dp[i] = y + 1$, sau đó cập nhật $startOf[y + 1]$. Độ phức tạp là $O(n \log n)$.
Đưa lên cây
Quay trở lại với bài toán ban đầu, ta sẽ có một hướng đi gần như tương tự. Với mỗi cách chọn các đỉnh, gọi giá trị của cách chọn đó là lương lớn nhất trong các đỉnh được chọn. Gọi $dp[u]$ là số đỉnh lớn nhất có thể được chọn trong cây con gốc $u$ mà vẫn thoả mãn điều kiện đề bài, và $startOf_u[k]$ là giá trị nhỏ nhất của 1 cách chọn $k$ đỉnh thoả mãn trong cây con gốc $u$, có thể bao gồm cả $u$ (quy ước $startOf_u[k] = +\infty$ nếu không tồn tại cách chọn thoả mãn). Tương tự như trên, ta cũng có thể chứng minh được $startOf_u$ là mảng không giảm, và $dp[u]$ chính là số phần tử khác $+\infty$ của nó. Bài toán còn lại là làm sao để duy trì mảng $startOf_u$, hoặc ít nhất là duy trì các thông tin cần thiết để có thể tính toán được lại $dp[u]$.
May mắn thay, chúng ta có một cách: Gọi $S_u$ là dãy các giá trị trong $startOf_u$ mà khác $+\infty$, được sắp xếp theo giá trị không giảm (một multiset). Khi này, ta có một nhận xét rất đẹp sau: Với một đỉnh $u$ bất kì, giả sử $a_u = -\infty$ (tức là $u$ không thể được chọn), gọi các con trực tiếp của $u$ lần lượt là $v_1, v_2, \ldots, v_k$, khi này ta có:
Vì sao? Các cây con của những đứa con khác nhau không có quan hệ quản lý với nhau, nên chọn $k_1$ đỉnh ở cây con $v_1$, $k_2$ đỉnh ở cây con $v_2$,… ghép lại luôn hợp lệ, và giá trị của cách ghép là $\max_i startOf_{v_i}[k_i]$. Muốn chọn tổng cộng $k$ đỉnh với giá trị nhỏ nhất thì ta lấy $k$ phần tử nhỏ nhất của hợp các $S_{v_i}$ – mà vì mỗi $S_{v_i}$ đã sắp xếp tăng dần nên $k$ phần tử nhỏ nhất luôn gồm một đoạn đầu của mỗi $S_{v_i}$, đúng là một cách chọn hợp lệ. Vậy $startOf_u[k]$ chính là phần tử nhỏ thứ $k$ của hợp.
Giờ thêm chính đỉnh $u$ với lương thật $a_u$ vào: chọn $u$ thì mọi đỉnh được chọn bên dưới phải có lương $\lt a_u$, tức là ghép $u$ với một cách chọn $y$ đỉnh có giá trị $startOf_u[y] \lt a_u$, được cách chọn $y + 1$ đỉnh với giá trị $a_u$. Y hệt bài LIS: tìm $y$ lớn nhất có $startOf_u[y] \lt a_u$ rồi cập nhật $startOf_u[y + 1] = \min(startOf_u[y + 1], a_u)$. Trên multiset, việc này đơn giản là:
lower_bound(a[u])). Nếu có thì xoá nó và chèn $a_u$ vào; nếu không có (mọi phần tử đều $\lt a_u$) thì chèn thêm $a_u$ – lúc này $dp[u]$ tăng thêm $1$. Đáp án $dp[u] = |S_u|$.Như vậy, bằng việc tính $S_{v_1} \cup S_{v_2} \cup \ldots \cup S_{v_k}$ theo thứ tự không giảm, sau đó tìm kiếm nhị phân để chèn $a_u$, ta tính được $S_u$ và $dp[u]$. Ta có nhận xét $|S_u| \le sz_u$, trong đó $sz_u$ là số đỉnh trong cây con gốc $u$. Vậy nên việc duy trì $S_u$ có thể được thực hiện bằng std::multiset và kĩ thuật gộp set (luôn đổ set nhỏ vào set lớn – small to large): mỗi phần tử mỗi lần bị "đổ" sang set khác thì set chứa nó lớn gấp đôi trở lên, nên mỗi phần tử bị đổ tối đa $\log N$ lần, mỗi lần chèn tốn $O(\log N)$.
Các bạn xem khung minh hoạ dưới đây (số cam = lương, dòng chữ dưới mỗi đỉnh = multiset $S$ đang giữ):
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
multiset<int> st[200005];
vector<int> ad[200005];
int a[200005], ans[200005];
void unite(int u, int v){
if (st[u].size() < st[v].size()) st[u].swap(st[v]);
for (int x : st[v]) st[u].insert(x);
}
void dfs(int u){
for (int v : ad[u]){
dfs(v); unite(u, v);
}
st[u].insert(0);
multiset<int>::iterator it = st[u].lower_bound(a[u]);
if (it != st[u].end()){
int x = *it;
st[u].erase(st[u].lower_bound(x));
}
st[u].insert(a[u]); st[u].erase(0);
ans[u] = st[u].size();
}
int main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++){
int u; cin >> u;
ad[u].push_back(i);
}
dfs(1);
for (int i = 1; i <= q; i++){
int x; cin >> x;
cout << ans[x] << '\n';
}
}import sys
from bisect import bisect_left, insort
def main():
d = sys.stdin.buffer.read().split()
n, q = int(d[0]), int(d[1])
a = [0] + [int(x) for x in d[2:2 + n]]
p = [0, 0] + [int(x) for x in d[2 + n:1 + 2 * n]]
ad = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
ad[p[i]].append(i)
order = [1]
for u in order:
order.extend(ad[u])
st = [None] * (n + 1) # st[u]: list đã sắp xếp, đóng vai trò multiset
ans = [0] * (n + 1)
for u in reversed(order): # con được xử lý xong trước cha
cur = []
for v in ad[u]: # gộp set: luôn đổ set nhỏ vào set lớn
sv = st[v]; st[v] = None
if len(cur) < len(sv):
cur, sv = sv, cur
for x in sv:
insort(cur, x)
k = bisect_left(cur, a[u]) # phần tử nhỏ nhất >= a[u]
if k < len(cur):
cur[k] = a[u] # xoá nó rồi chèn a[u]: vị trí vẫn giữ đúng thứ tự
else:
cur.append(a[u])
st[u] = cur
ans[u] = len(cur)
ws = d[1 + 2 * n:1 + 2 * n + q]
print('\n'.join(str(ans[int(w)]) for w in ws))
main()Giải thích 1 số chỗ trong code ở trên:
- Hàm
unite(u, v): nếust[u]nhỏ hơnst[v]thìswaphai set (thao tác $O(1)$, chỉ đổi "ruột" chứ không chép phần tử), rồi đổ từng phần tử của set nhỏ sang set lớn – đó chính là kĩ thuật gộp set nhỏ vào lớn. st[u].lower_bound(a[u])trả về phần tử nhỏ nhất $\ge a_u$. Phải xoá bằng iterator (erase(lower_bound(x))) để chỉ xoá một bản sao, vìmultiset::erase(x)sẽ xoá tất cả các phần tử bằng $x$.- Cặp lệnh
st[u].insert(0)vàst[u].erase(0)thực ra không ảnh hưởng kết quả (vì $a_i \ge 1$ nênlower_bound(a[u])không bao giờ trỏ vào số $0$), mình giữ nguyên như code gốc. - Bản Python không có multiset nên dùng
listđã sắp xếp +bisect: thay "xoá phần tử nhỏ nhất $\ge a_u$ rồi chèn $a_u$" bằng gán thẳngcur[k] = a[u](vị trí đó vẫn giữ đúng thứ tự). Mỗi lầninsortphải dời phần tử trong list nên chậm hơn C++.
Đánh giá độ phức tạp của cách làm này:
- Không gian: tổng số phần tử trong các set không vượt quá $N$: $O(N)$.
- Thời gian: gộp set nhỏ vào lớn: mỗi phần tử bị chuyển tối đa $O(\log N)$ lần, mỗi lần chèn $O(\log N)$; mỗi đỉnh thêm một lần
lower_bound/xoá/chèn $O(\log N)$. Tổng $O(N \log^2 N)$.
Subtask 6 – cách 2Thêm đỉnh theo lương tăng dần + HLD – O(N log³ N)
Lời giải thứ hai khó cài đặt hơn nhiều, mình để đây cho bạn nào muốn luyện thêm kĩ thuật HLD (Heavy Light Decomposition). Ý tưởng: thay vì xử lý theo thứ tự trên cây, ta sắp xếp lại các đỉnh theo lương tăng dần và lần lượt "bật" từng đỉnh lên (cho phép nó được chọn), đồng thời cập nhật đáp án cho mọi đỉnh.
Với mỗi đỉnh $u$, xét tại thời điểm hiện tại (chỉ những đỉnh đã bật mới được chọn):
- $cur_u$: số đỉnh chọn được tối đa trong cây con của $u$ không tính $u$ (trong code lưu bằng cây Fenwick
sum, đọc bằngre(pos[u])). Khi đỉnh $u$ được bật, mọi đỉnh đã bật trước đều có lương nhỏ hơn nên đều đặt được dưới $u$: số đỉnh chọn được tối đa bắt buộc chứa $u$ là $dp_u = cur_u + 1$, và giá trị này được "chốt" luôn (các đỉnh bật sau có lương lớn hơn, không thể đặt dưới $u$ nếu đã chọn $u$). - $dis_u$: hiệu của số đỉnh có thể chọn tối đa với đỉnh $u$ trong đó lựa chọn không bắt buộc chứa $u$ và bắt buộc chứa $u$ – tức là $cur_u - dp_u$ (lưu trên cây phân đoạn
max_dp, thực chất là cây min). Lúc vừa bật $u$ thì $dis_u = -1$; đỉnh chưa bật thì coi $dis_u = 0$.
Sắp xếp lại các đỉnh theo giá trị và cố gắng vừa đẩy từng đỉnh vào vừa cập nhật mảng $cur$. Ví dụ ta đang đẩy đến đỉnh $i$:
- Ta nhận thấy rằng, khi đẩy $i$ vào, những đỉnh bị thay đổi kết quả sẽ là các tổ tiên của $i$, tương đương với việc sự thay đổi sẽ diễn ra trên đường đi đơn từ $1$ đến $i$. Sự thay đổi này chỉ có thể tăng nhiều nhất $1$, vì ta chỉ thêm mỗi đỉnh $i$ vào. Nhận xét thêm, các đỉnh được tăng thêm $1$ sẽ là một đoạn tổ tiên liên tiếp ngay trên $i$. Giờ ta chỉ cần biết tổ tiên gần $i$ nhất mà ta không thể cập nhật tiếp nữa là đỉnh $c$ nào. Nhận thấy rằng đỉnh này chỉ có khi $dis_c \lt 0$: lúc đó $c$ đang "chọn $c$" tốt hơn hẳn "không chọn $c$", $cur_c$ tăng $1$ thì $dis_c$ tăng lên $0$ nhưng đáp án tốt nhất của $c$ không đổi, nên các tổ tiên phía trên $c$ cũng không đổi.
- Giá trị $cur_i + 1$ ngay lúc đẩy $i$ chính là kết quả lựa chọn tối đa bắt buộc chứa $i$, ta lưu vào mảng $dp_i$. Các đỉnh đẩy vào sau có lương lớn hơn hẳn $a_i$, khi cập nhật có thể làm thay đổi $cur_i$ nhưng không làm thay đổi được $dp_i$. Cuối cùng đáp án của $i$ là $\max(dp_i, cur_i) = dp_i + \max(0, dis_i)$.
- Các đỉnh có lương bằng nhau được tính $dp$ cho cả nhóm trước rồi mới đẩy vào (chúng không được đặt dưới nhau), và trong nhóm thì đỉnh nông hơn (gần gốc hơn) đẩy trước – đó là lý do hàm
cmpso sánh thêm độ sâudeg.
Tới đây, bài toán đã quy về một bài toán HLD căn bản: chia cây thành các chuỗi nặng, đường đi từ $i$ lên gốc đi qua tối đa $O(\log N)$ chuỗi, mỗi chuỗi là một đoạn liên tiếp trên mảng pos (mình đánh số mỗi chuỗi từ dưới lên trên). Trên mỗi chuỗi ta cần: cộng $1$ cho một đoạn (Fenwick cho $cur$, cây phân đoạn cho $dis$) và tìm vị trí đầu tiên có $dis = -1$. Ở việc tìm đỉnh gần nhất có $dis_c \lt 0$, chúng ta có thể sử dụng walk on segment tree $O(N \log^2 N)$ hoặc chặt nhị phân + cây phân đoạn $O(N \log^3 N)$ – code dưới đây dùng cách chặt nhị phân.
Source code để các bạn tham khảo nếu làm theo hướng này (cách này mình chỉ để bản C++):
#include<bits/stdc++.h>
using namespace std;
int n, q, u;
pair<int, int> a[200005];
int p[200005];
int dp[200005];
vector<int> child[200005];
int sub[200005];
vector<int> chain[200005];
vector<int> k[200005];
int lt[200005], num[200005];
int deg[200005];
int nw = 1;
int lz2[800005], lz[800005], sum[800005], max_dp[800005];
int pos[200005];
int st[200005], ed[200005];
int b[200005];
void dfs(int u){
sub[u] ++;
deg[u] = deg[p[u]] + 1;
for (auto v : child[u]){
dfs(v);
sub[u] += sub[v];
}
return;
}
void hld(int u, int tt){
chain[tt].push_back(u);
if (child[u].size() == 0){
lt[u] = tt;
return;
}
lt[u] = tt;
num[u] = chain[tt].size();
int mx = 0, idx = 0;
for (auto v : child[u]){
mx = max(mx, sub[v]);
if (mx == sub[v]) idx = v;
}
for (auto v : child[u]){
if (v == idx) hld(v, tt);
else{
hld(v, ++nw);
}
}
}
void up(int x, int chg){
int idx = x;
while (idx <= n){
sum[idx] += chg;
idx += idx & (-idx);
}
return;
}
int re(int x){
int idx = x;
int res = 0;
while (idx > 0){
res += sum[idx];
idx -= idx & (-idx);
}
return res;
}
int h;
void apply(int p, int val){
max_dp[p] += val;
if (p < n + 1) lz2[p] += val;
}
void path(int p){
while (p > 1){
p >>= 1;
max_dp[p] = min(max_dp[p << 1], max_dp[p << 1 ^ 1]) + lz2[p];
}
}
void down(int p){
for (int s = h; s > 0; --s){
int i = p >> s;
apply(i << 1, lz2[i]);
apply(i << 1 | 1, lz2[i]);
lz2[i] = 0;
}
}
void up2(int l, int r, int val){
l += n + 1, r += n + 1;
int l0 = l, r0 = r;
for (; l < r; l >>= 1, r >>= 1){
if (l & 1) apply(l++, val);
if (r & 1) apply(--r, val);
}
path(l0);
path(r0 - 1);
}
int re2(int l, int r){
l += n + 1, r += n + 1;
down(l);
down(r - 1);
int res = 1e9;
for (; l < r; l >>= 1, r >>= 1){
if (l & 1){
res = min(res, max_dp[l++]);
}
if (r & 1){
res = min(max_dp[--r], res);
}
}
return res;
}
int sus;
void cal(int val, int u){
u = p[u];
while (u){
int posSt = pos[u];
int posEd = pos[chain[lt[u]][chain[lt[u]].size() - 1]];
sus = 1e9;
int l = posSt, r = posEd, mid;
while (l <= r){
mid = (l + r) / 2;
if (re2(posSt, mid + 1) == -1){
r = mid - 1;
sus = min(sus, mid);
}
else l = mid + 1;
}
if (sus != 1e9 && sus <= posEd){
up(posSt, 1);
up(sus, -1);
up2(posSt, sus + 1, 1);
break;
}
up(posSt, 1);
up(posEd + 1, -1);
up2(posSt, posEd + 1, 1);
u = p[b[posEd]];
}
}
bool cmp(pair<int, int> a, pair<int, int> b){
if (a.first != b.first) return a.first < b.first;
return deg[a.second] < deg[b.second];
}
int main(){
if(fopen("CONGTY.INP", "r")){
freopen("CONGTY.INP", "r", stdin);
freopen("CONGTY.OUT", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
h = sizeof(int) * 8 - __builtin_clz(n + 1);
for (int i = 1; i <= n; i ++){
cin >> a[i].first;
a[i].second = i;
}
for (int i = 2; i <= n; i ++){
cin >> p[i];
child[p[i]].push_back(i);
}
dfs(1);
hld(1, 1);
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= nw; i ++) reverse(chain[i].begin(), chain[i].end());
int stt = 0;
for (int i = 1; i <= nw; i ++){
st[i] = stt + 1;
for (auto j : chain[i]){
pos[j] = ++ stt;
b[stt] = j;
}
ed[i] = stt;
}
vector<pair<int,int>> aft;
for (int i = 1; i <= n; i ++){
dp[a[i].second] = re(pos[a[i].second]) + 1;
aft.push_back(a[i]);
if (a[i].first != a[i + 1].first){
for (auto j : aft){
cal(dp[j.second], j.second);
up2(pos[j.second], pos[j.second] + 1, - (re2(pos[j.second], pos[j.second] + 1) - (-1)));
}
aft.clear();
}
}
for (int i = 1; i <= n; i ++){
dp[i] = max(dp[i], dp[i] + re2(pos[i], pos[i] + 1));
}
while (q --){
cin >> u;
cout << dp[u] << '\n';
}
}Code dài gần 200 dòng nên trong khung chạy tay mình gom các hàm dựng cây (dfs, hld) và vòng chặt nhị phân lại, còn hàm cal (đi từ đỉnh vừa bật lên gốc) thì chạy từng dòng. Bảng bên dưới cho biết với mỗi đỉnh: vị trí pos, chuỗi chứa nó, $cur$ (đọc từ Fenwick), $dis$ (đọc từ cây phân đoạn) và $dp$:
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$.
- Thời gian: sắp xếp $O(N \log N)$; mỗi đỉnh khi bật đi qua $O(\log N)$ chuỗi, trên mỗi chuỗi chặt nhị phân $O(\log N)$ lần, mỗi lần truy vấn cây phân đoạn $O(\log N)$: tổng $O(N \log^3 N)$ (nếu dùng walk on segment tree thì còn $O(N \log^2 N)$).
ulimit -s unlimited). Code gốc của mình dùng freopen trực tiếp, ở đây mình bọc thêm if(fopen(...)) để nộp trên web không bị lỗi.- 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