Comments

• 
  

  1

  

  vrski39  commented on May 31, 2024, 12:01 p.m.

  Mình xin chia sẻ một lời giải mình đọc được của bài này

  Spoiler lồng để tránh ai chưa muốn đọc nhưng lỡ bấm nhầm

  Sub 90 điểm

  Xét một đoạn D = [L, R], số xu trong túi A, B đều nằm trong đoạn này, lấy $$ M = \left\lfloor \frac{L+R}{2} \right\rfloor $$

  Xét số xu ở A

  Nếu A = L, dễ thấy A < B

  Nếu A = R, dễ thấy A > B

  Còn lại, ta chia 2 đoạn: D1 = [L+1, M] và D2 = [M+1, R-1]

  Dễ thấy các trường hợp

  A, B ở khác D1, D2, dễ thấy túi nào ít xu hơn

  A, B ở cùng D1 hoặc D2, ta sẽ xét tiếp ở khoảng nhỏ hơn

  Tới đây các bạn có thể thử sức giải

  Chi tiết 1:

  Ta có thể dựng một segment tree

  Xét túi A, B đều có xu trong đoạn [L, R]

  Giả sử có nút a quản lý xu ở nút A trong đoạn [L, R]

  Nút bl và br quản lý xu ở nút B trong đoạn [L, R]

  Tại a[L]: A < B, tại a[R]: A > B

  Nếu số xu trong túi A nằm trong đoạn [L+1, M], ta sẽ xét nút bl

  Dễ thấy bl[i] cho B > A với mọi i trong [M, R], còn bl[L+1] cho B < A

  Với các giá trị còn lại [L+2, M-1], ta biết A cũng chỉ trong khoảng [L+1, M], tức là ta có thể xét lại y hệt như trên với vai trò B, A hoán đổi

  Segment tree sẽ có dạng như thế này

           a         (xu túi A trong đoạn [L  , R  ])
         /   \
        /     \
       /       \
      bl       br    (xu túi B trong đoạn [L  , R  ])
      /\       /\
     /  \     /  \
    /    \  arl  arr (xu túi A trong đoạn [M+1, R-1]) 
  all   alr          (xu túi A trong đoạn [L+1, M  ])
  

  Ta đến được nút all từ bl chỉ khi xu B nằm trong [L+2, M-1], nên có thể bắt đầu xét tương tự như a

  Đến đây chắc bạn nào tinh ý thì thấy cách giải rồi

  Gợi ý:

  Nhìn cặp 2 nút all/arl và cặp 2 nút alr/arr

  Chi tiết 2:

  Mình đã nổ não khi lần đầu đọc trick này :v

  Vấn đề hiện tại đó là chúng ta sử dụng quá nhiều nút

  Tuy nhiên, nếu tinh ý, có thể thấy all và arl hoạt động y hệt nhau, chỉ khác nhau ở đoạn mà chúng quản lý

  Do đó, ta có thể gộp chúng chung vào một siêu-nút để quản lý (tương tự với cặp nút alr/arr)

  Tổng quát hơn: Trong cùng một độ sâu, có thể để một nút quản lý mọi con trái, và một nút quản lý mọi con phải

  Có 5000 phần tử, mỗi bước ta trừ 2 và chia đôi phần tử, dễ thấy có thể áp vào 11 lần

  Và có thể tối ưu thêm để bỏ bớt nút thứ 22 nếu ta cẩn thận cắt một số trường hợp đi, lúc này ta được 90 điểm