Hướng dẫn cho Liên Minh Dễ Dàng

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuom1999

Đầu tiên, chúng ta thử giải bài toán với trường hợp không có cập nhật. Với một dãy \(a_1, a_2, ..., a_n\), ta dựng 2 dãy sau:

  • \(s_i = a_1 + a_2 + ... + a_i\)
  • \(b_i = a_i - s_{i - 1}\)

Khi đó đáp số là \(max(b_1, b_2, ..., b_n)\). Chứng minh này khá đơn giản, xin nhường lại các bạn.

Với một truy vấn \((l, r)\) thì chúng ta làm thế nào? Đáp số sẽ là \(max(b_l, b_{l+1}, ..., b_r) - s_{l - 1}\).

Do vậy để làm subtask \(2\), các bạn có thể dùng RMQ để trả lời các truy vấn max cho một đoạn.

Subtask 3:

Để giải subtask cuối, chúng ta cần quan tâm thao tác cập nhật \(a_x = y\). Điều cần quan tâm là thao tác này sẽ làm biến đổi dãy \(b\) và \(s\) như thế nào?

  • Dãy \(s\) có thể dễ dàng cập nhật bằng BIT / Fenwick Tree
  • \(b_x\) tăng lên \(y - a_x\) đơn vị
  • \(b_i\) tăng lên \(a_x - y\) đơn vị \(\forall i > x\)

Như vậy chúng ta cần thao tác tăng các số trong một đoạn lên \(k\) đơn vị và lấy max của một đoạn. Đây chính là ứng dụng cơ bản của Segment Tree + Lazy Propagation (Cây IT + Cập nhật Lazy).

Độ phức tạp: \(O((n + q) \log n)\)


Bình luận


  • 0
    Toilaaibanbietko7A4    10:13 a.m. 16 Tháng 8, 2020 ← chỉnh sửa 2

    Thank anh cuom1999 đã viết Editorial cho ý tưởng của em nha!


    • -5
      THOANGLQDT    8:52 p.m. 30 Tháng 10, 2020

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


      • 4
        HH_Hoang    8:37 p.m. 18 Tháng 12, 2020

        cÓ LÀM MỚI CÓ ĂN NHÁ!tỰ LÀM ĐI BRO:))