Truy vấn XOR trên đoạn

General
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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ại 1 gầ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 v hoặc 2 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$
Draft saved