Range Xor Queries
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1,A_2,...,A_N\). Nhiệm vụ của bạn là thực hiện \(Q\) truy vấn sau: Tổng \(XOR\) của các giá trị trong phạm vi \([x,y]\) là bao nhiêu?
Input
- Dòng đầu tiên gồm hai số nguyên dương \(N, Q\) là số lượng giá trị và số truy vấn.
- Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,...,A_N (A_i≤10^9)\).
- \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn, gồm hai số nguyên \(x,y\) \((1≤x≤y≤N)\).
Output
- In ra \(Q\) dòng, mỗi dòng là kết quả của một truy vấn.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
- Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).
Example
Test 1
Input
8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3 Output
3
0
6
4
Bình luận
bài này dùng mảng XOR dồn đúng k nhỉ
-
1
minhtuanitk20
10:33 p.m. 18 Tháng 1, 2022
-
0
hhoangcpascal
10:27 p.m. 2 Tháng 9, 2020
-
0
vinhntndu
10:30 p.m. 2 Tháng 9, 2020
-
0
hhoangcpascal
10:33 p.m. 2 Tháng 9, 2020
-
0
SPyofgame
8:58 a.m. 3 Tháng 9, 2020
←
đã chỉnh sửa
→
-
0
BichSonNhat
9:25 a.m. 3 Tháng 9, 2020
-
1
vinhntndu
6:00 a.m. 3 Tháng 9, 2020
-
1
hhoangcpascal
9:37 a.m. 3 Tháng 9, 2020
4 bình luận nữađr a kiểu : vd 1 2 3 4 5 6 7 8 mà q(4,6) = prefix[6]^prefix[3] = kq
Dạ anh :V
thế thì chỉ cần tag implementation thôi chứ nhỉ
Là sao anh?
\(xorsum[1, r] ⊕ xorsum[1, l - 1] = xorsum[l, r]\) mà đúng không anh nhỉ :v
SPyofgame Đúng gùi ông
dạng bài ấy, cần gì BIT
:V luyện tập bằng bit cũng được :V