Bình luận

• 
  

  2

  

  Groot  đã bình luận lúc 2, Tháng 12, 2024, 1:54 ← sửa 2 →

  Edit: Mình định rep comment của bạn dưới nhưng lỡ đăng thành 1 comment riêng :V

  ---

  CTDL

  • Dùng Segment Tree
  • Mỗi nút trong Segment Tree lưu:
    • Tổng đoạn (sum).
    • Giá trị nhỏ nhất (min_val).
    • Vị trí nhỏ nhất (min_pos).
  • Thay vì thực sự xoay mảng (truy vấn loại 1), sử dụng 1 biến offset để điều chỉnh chỉ số l , r.

  ---

  Xử lý các truy vấn

  Loại 1:

  Cộng thêm d vào offset và lấy mod để giữ chỉ số trong khoảng [0, n-1].

  Loại 2, 3:

  Về phần cài đặt

  Mình thấy thì bài này cài đặt như Segment Tree cổ điển thôi, tuy cài có chút phức tạp hơn nhưng ý tưởng cơ bản thì không có gì mới lắm....

  ---

  Mấu chốt thuật toán:

  Ở mỗi truy vấn, ta cần phải tính chỉ số thật sự của s và t

  Công thức:

  int real_s = (s - offset - 1 + n * n) % n + 1;
  int real_t = (t - offset - 1 + n * n) % n + 1;
  

  Bên cạnh đó, phải lưu ý rằng sẽ có 2 trường hợp xảy ra:

  TH 1. s <= t : truy vấn từ s -> t như bình thường

  TH 2. s > t : truy vấn từ s -> n và 1 -> t

  ở TH 2, cần lưu ý khi truy vấn loại 2...?

  ---

  Code mẫu:

  https://ideone.com/1XU1IC

• 
  

  0

  

  Rykrax  đã bình luận lúc 14, Tháng 5, 2024, 3:02

  xin ý tưởng bài này với ae