Sau khi đạt thành tựu "Completionist++" trong Balatro, bậc thầy Balatro Clonoth muốn kiểm tra hiểu biết của bạn về trò chơi thẻ bài.

Có một bộ bài gồm \(n\) lá. Mỗi mặt của mỗi lá ghi một số nguyên trong \([1,m]\). Bạn có thể chọn một số lá và lật chúng.

Với \(1\le l\le r\le m\), đoạn \([l,r]\) được gọi là có thể phủ nếu tồn tại một cách lật sao cho mỗi số nguyên trong \([l,r]\) xuất hiện trên mặt ngửa của ít nhất một lá.

Nói chính xác hơn, gọi hai số trên hai mặt của lá thứ \(i\) là \(a_{i,0},a_{i,1}\). Đoạn \([l,r]\) có thể phủ khi và chỉ khi tồn tại một xâu nhị phân \(s\) độ dài \(n\) sao cho với mọi \(l\le x\le r\), tồn tại \(1\le j\le n\) thỏa mãn \(a_{j,s_j}=x\).

Ban đầu bộ bài rỗng, tức \(n=0\). Sau đó có \(q\) thao tác thuộc một trong ba loại:

1. Thêm lá: cho \(x,y\) (\(1\le x,y\le m\)). Tăng \(n\) lên \(1\), rồi thêm lá số \(n\) có mặt trước ghi \(x\) và mặt sau ghi \(y\).
2. Loại lá: cho \(p\) (\(1\le p\le n\)), bảo đảm lá số \(p\) hiện vẫn còn trong bộ bài. Loại lá đó khỏi bộ bài.
3. Truy vấn: cho \(s,t,u,v\) (\(1\le s\le t\le m\), \(1\le u\le v\le m\)). Đếm số đoạn \([l,r]\) thỏa mãn \(s\le l\le t\), \(u\le r\le v\) và \([l,r]\) có thể phủ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(m,q\).
• Mỗi dòng trong \(q\) dòng tiếp theo bắt đầu bằng số nguyên \(o\), là loại thao tác:
• Nếu \(o=1\), dòng chứa 1 x y.
• Nếu \(o=2\), dòng chứa 2 p.
• Nếu \(o=3\), dòng chứa 3 s t u v.

Dữ liệu ra

Với mỗi truy vấn loại \(3\), in một số nguyên không âm trên một dòng: số đoạn thỏa mãn.

Ràng buộc

Mọi tham số của thao tác đều thỏa mãn các giới hạn nêu trong phần mô tả.

Chấm điểm

• Tính chất A: mọi thao tác thêm và loại lá đều xuất hiện trước mọi truy vấn.
• Tính chất B: không có thao tác loại lá.
• Tính chất C: mọi truy vấn thỏa mãn \(s=t\) và \(u=v\).

Ví dụ

8 10
1 6 5
3 2 3 8 8
1 3 3
1 4 5
3 2 6 6 8
1 1 2
2 4
1 2 5
3 1 3 2 7
3 2 3 2 3

0
2
8
3

9 17
1 6 6
3 1 1 3 3
1 5 1
1 3 4
2 2
1 9 9
1 2 2
1 7 9
2 4
1 2 3
3 1 7 3 3
1 8 6
1 7 5
3 6 9 9 9
1 4 5
2 3
3 3 5 2 9

0
2
4
16

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.