Lật bit đoạn trên phiên bản

Buổi 30 — Persistent Segment Tree
Points
52
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy nhị phân $a_1,\dots,a_n$ (phiên bản $0$). Các thao tác (mỗi thao tác loại $1$ tạo phiên bản mới có số hiệu tiếp theo):

  • 1 v l r: tạo phiên bản mới từ $v$ bằng cách lật mọi bit $a_i$ ($0\leftrightarrow 1$) với $l\le i\le r$.
  • 2 v l r: in số bit $1$ trong đoạn $[l,r]$ của phiên bản $v$.
Dữ liệu vào

Dòng đầu: $n,q$. Dòng hai: $n$ số $0/1$. Sau đó $q$ dòng thao tác, mỗi dòng gồm $4$ số: loại, $v$, $l$, $r$.

Dữ liệu ra

Với mỗi thao tác loại $2$ in đáp án.

Ví dụ

Input

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

Output

2
Giới hạn
  • $1\le n\le 10^5$; $1\le q\le 5\cdot 10^4$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved