Truy vấn XOR trên đoạn
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho đồ thị $N$ đỉnh ban đầu không có cạnh nào. Thực hiện $Q$ thao tác thuộc các loại sau:
1 u v: Lưu trạng thái hiện tại vào lịch sử, sau đó thêm cạnh nối $u$ và $v$ (nếu $u, v$ đã liên thông thì không có thay đổi nhưng vẫn tính là một thao tác lưu trạng thái).2: Hoàn tác thao tác loại1gần nhất chưa bị hoàn tác (đảm bảo luôn có thao tác loạiĐề bài
Cho mảng $A$ gồm $N$ số nguyên không âm đánh số từ $1$ đến $N$. Bạn cần thực hiện $Q$ truy vấn thuộc một trong hai loại sau:
1 p v: Gán giá trị $A[p] = v$.2 l r: Tính tổng XOR ($A[l] \oplus A[l+1] \oplus \dots \oplus A[r]$) của đoạn từ $l$ đến $r$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
- Dòng thứ hai chứa $N$ số nguyên $A[1], A[2], \dots, A[N]$.
- $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn dạng
1 p vhoặc2 l r.
Dữ liệu ra
Với mỗi truy vấn loại
21để hoàn tác).3 u v: Kiểm tra $u$ và $v$ có liên thông hay không (YES/NO).4: In ra số thành phần liên thông hiện tại.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- $Q$ dòng tiếp theo mô tả các truy vấn.
Dữ liệu ra
- In ra kết quả cho mỗi truy vấn loại
3 và 4.
Ví dụ
, in ra kết quả trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 4 1 2 3 4 5 2 1 3 1 2 6 2 1 3 2 2 5 |
0 4 4 |
| Input | Output |
| 4 7 1 1 2 1 2 3 3 1 3 4 2 3 1 3 4 |
YES 2 NO 3 |
Giới hạn
- $1 \le N, Q \le 10^5$
- $0 \le A[i], v \le 10^9$
- $1 \le p \le N$, $1 \le l \le r \le N$
Community Discussion