Đảo bit và nghịch thế (Lazy Segment Tree)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Duy trì mảng nhị phân với thao tác đảo bit cả đoạn và truy vấn số nghịch thế trên đoạn.

Input

Dòng đầu chứa $N,Q$, dòng kế chứa $A_1,\ldots,A_N$. Mỗi truy vấn T L R:

• 1 L R: thay $A_j$ bằng $1-A_j$ với mọi $L\le j\le R$.
• 2 L R: đếm cặp $i<j$ trong đoạn sao cho $A_i>A_j$.

Output

In số nghịch thế cho mỗi truy vấn loại 2.

Subtask

• 20 điểm: $N,Q\le50$.
• 30 điểm: $N,Q\le5000$.
• 50 điểm: $N,Q\le2\cdot10^5$, mỗi $A_i$ là 0 hoặc 1.

Ví dụ

Input

5 5
0 1 0 0 1
2 1 5
1 3 4
2 2 5
1 1 3
2 1 2

Output

2
0
1

Giải thích

Ban đầu có hai nghịch thế. Đảo vị trí 3 và 4 làm đoạn $[2,5]$ thành toàn 1 nên có 0 nghịch thế. Sau thao tác đảo tiếp, hai phần tử đầu là 1 0, tạo đúng một nghịch thế.