NKBRACKET-spoj

NKBRACKE-spoj
- Tóm tắt :có 2 loại truy vấn 0 và 1, với truy vấn 0 thì ta update vị trí i thành kí tự ch , truy vấn 1 ta kiểm tra xem từ l đến r có phải dãy ngoặc đúng hay k.
- Cách trâu : nói sao làm vậy :v độ phức tạp O(n^2);
- Cách 2 :
+ mã hóa : '(' là 1 vả ')' là -1.
+ điều kiện để là ngoặc đúng : tiền tố nhỏ nhất phải >=0 vả tổng từ l đến r=0.
+ giải : sử dụng 1 chút mẹo của bài gss, sử dụng nút ảo không là nút kết quả , với mỗi nút thuộc đoạn [l,r] ta cập nhật với nút 0, lưu ý cập nhật tiền tố trước không sẽ bị sai lệch
+ Cập nhật : tiền tố [i]=min(tiền tố nút trái , sum nút trái + tiền tố nút phải )
CODE