Xor Cả Đoạn Tính Tổng

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

Cho dãy N số nguyên không âm nhỏ hơn 2^30. Thao tác XOR mọi phần tử trong một đoạn với cùng một số x, và hỏi tổng (số học thông thường) các phần tử trong một đoạn.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một thao tác:

  • 1 l r x: thay a_i bằng a_i XOR x với mọi i ∈ [l, r].
  • 2 l r: hỏi tổng a_l + ... + a_r.
Dữ liệu ra

Với mỗi thao tác loại 2, in ra tổng đoạn.

Ví dụ
Input Output
5 4\n3 9 2 3 5\n2 2 2\n1 2 5 3\n2 1 1\n2 2 5 9\n3\n17
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 0 ≤ a_i, x < 2^30
Draft saved