Bình luận

• 
  

  1

  

  minhkochamhoc  đã bình luận lúc 2, Tháng 1, 2026, 15:10

  solve

  ý tưởng

  • đầu tiên khi đọc bài tập này ta có thể nghĩ ngay tới phương án dp do nó là thuộc dạng dãy con tăng dài nhất
  • mà do bài này bị phụ thuộc vào việc để nối 1 phần tử vào 1 dãy con tăng nào đó thì chênh lệch giữa phần tử trước đó và phần tử ta nối vào ko được vượt quá k cho nên người thông minh như bạn nghĩ ra cách gọi dp[x] là dộ dài dãy con tăng dài nhất có kết thúc là phần tử mang giá trị x
  • do đó ta có cách tính mảng dp này là với mỗi giá trị val[i] hiện tại đang xét ta tìm trên mảng dp xem trước đó dãy con nào kết thúc trong khoảng [val[i] - k , val[i] - 1] có độ dài lớn nhất từ đó ta sẽ có phương án tốt nhất tạo nên dãy con kết thúc tại val[i]
  • vậy nên công thức truy hồi là dp[val[i]] = max(dp[val[i]] , dp[val[i] - j] + 1) (với 1 <= j <= k && val[i] - j >= 1)
  • ở đây mỗi lần tính dp[val[i]] ta lại phải xét k lần để tìm đoạn con tốt nhất trước đó nối đuôi vào vì vậy độ phức tạp bài toán là O(n * k) , dễ thấy với cách làm này bài toán đúng bản chất nhưng chưa tối ưu do số lượng phần tử của mảng và giá trị k khá lớn nên chưa thể ac được
  • do đó người thông minh như bạn lại nghĩ ra cách ném bài này lên các cấu trúc dữ liệu cây như segment tree và fenwick tree để giảm độ phức tạp do các cấu trúc này giúp chúng ta có khả năng tìm kiếm giá trị tốt nhất trên khoảng do tính chất nút cha sẽ được tạo nên từ kết quả tốt nhất của các nút con cho nên thay vì phải so sánh tất cả những phần tử thì ta chỉ cần so sánh 1 vài phần tử nút cha với nhau là được từ đó việc tính toán cx giảm bớt
  • giả sử với cấu trúc segment tree ta sẽ triển khai như sau :
  • tạo cây segment tree là lưu giá trị lớn nhất trên đoạn , mỗi phần tử lá là độ dài dãy con tăng dài nhất có giá trị kết thúc là val[i] , đoạn mà nút đó kiểm soát là [l , r] chính là độ dài dãy con tăng dài nhất có giá trị kết thúc nằm trong khoảng [l,r]
  • hàm GetPre(int node , int l , int r , int u , int v) là trả về độ dài dãy con tăng dài nhất có giá trị kết thúc nằm trong khoảng [u , v] mà khoảng này chính là khoảng [val[i] - k , val[i] - 1] mà ta sẽ dùng để tính mảng dp khi nãy
  • hàm update(int node , int l , int r , int pos , int lenght) là cập nhật vị trí dãy con tăng dài nhất có giá trị kết thúc là pos có độ dài length mà ta tìm được bằng cách lấy độ dài đoạn trước bằng GetPre + 1 do ghép đoạn tốt nhất đằng trước với phần tử hiện tại
  • sau cùng kết quả chính là nút lá có độ dài tốt nhất trên cây
  • độ phức tạp O(nlog(n))

  code và lời khuyên

  • code của tớ : Segment Tree
  • lưu ý 1: với những bạn nào chưa học segment tree hay fenwick tree thì mình nghĩ các bạn vẫn nên làm thử bài này với thuật O(n * k) do nó cx ko tốn mấy thời gian mà còn tăng kĩ năng các bạn lên hoặc các bạn có thể học nó trên vnoi wiki trước rồi sau đó giải bài này sau
  • lưu ý 2: bài này mình nghĩ mọi người nên code segment tree cho dễ code hơn với đỡ sai hơn do việc tìm max trên 1 đoạn [l, r] trên fenwick tree là phức tạp hơn và dễ sai hơn (mình đã thử code và bị wa chắc là do mình gà) còn segment tree thì lấy max trên đoạn [l , r] là bài toán quen thuộc và ko quá xa lạ rồi