bh thao tác đổi L -> R và ngược lại như sau: Đật vị trí của kí tự cần đổi là k
TH1: k thuộc set 1 (k là cuối của 1 đoạn L/R liên tiếp)
Nếu k bằng kích thước xâu (kí tự ở cuối xâu):
Giả sử xâu là ...RL Khi đó set 1 = {..., k-1, k} Xâu sau khi đổi là ...RR Khi đó set 1 = {..., k} (các ptu ở trước ko thay đổi) => thực hiện thao tác XÓA ptu k-1
Ngược lại giả sử xâu là ...RR Khi đó set 1 = {..., k} (các ptu ở trước ko thay đổi) Xâu sau khi đổi là ...RL Khi đó set 1 = {..., k-1, k} (các ptu ở trước ko thay đổi) => thực hiện thao tác THÊM ptu k-1
Nếu k KHÁC kích thước xâu:
Giả sử xâu là ...LRLRRRRRRRRRRRRRRRRRRRRRL... (kí tự vị trí k-1 != kí tự vị trí k-2) ^ kí tự cần đổi ^ vị trí p nào đó (p >= k+1) Khi đó set 1 = {..., k-1, k, p, ...} Xâu sau khi đổi là ...LRRRRRRRRRRRRRRRRRRL... ^ vị trí p nào đó (p >= k+1) Khi đó set 1 = {..., p, ...} => thực hiện thao tác XÓA ptu k và k-1
Ngược lại giả sử xâu là ...LLLLLLRRRRRRRRRRRRRRRRRRRRRL... vị trí q nào đó ^ ^ kí tự cần đổi ^ vị trí p nào đó (p >= k+1) Khi đó set 1 = {..., q, k, p, ...} Xâu sau khi đổi là ...LRRRRRRRRRRRRRRRRRRL... vị trí q nào đó ^ ^ vị trí p nào đó (p >= k+1) Khi đó set 1 = {..., q, k - 1, p, ...} => thực hiện thao tác XÓA ptu k và thêm ptu k-1
TH2: k KHÔNG thuộc set 1 (k là đầu/giữa 1 đoạn L/R liên tiếp)
=> sẽ luôn THÊM ptu k (vì giờ k sẽ là cuối của 1 đoạn L/R liên tiếp)
Nếu k là đầu 1 đoạn => có ptu k-1 trong set 1 => XÓA ptu k-1 và THÊM ptu k (vì khi đó ptu k-1 ko còn là ptu cuối của 1 đoạn nữa)
Nếu k giữa 1 đoạn => ko có ptu k-1 trong set 1 => THÊM ptu k-1 và k (vì khi đó ptu k-1 và k là cuối của 2 đoạn nó đó)
(xong r lmao)
SAU KHI XỬ LÝ => in ra ptu cuối của set 2 (aka max của set 2) = đáp án sau 1 query