Range Xor Queries

Xem PDF
Tác giả:
hhoangcpascal
Dạng bài
Đ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


  • 0
    vinhntndu    10:02 p.m. 2 Tháng 9, 2020

    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

      đr a kiểu : vd 1 2 3 4 5 6 7 8 mà q(4,6) = prefix[6]^prefix[3] = kq


      • 0
        hhoangcpascal    10:27 p.m. 2 Tháng 9, 2020

        Dạ anh :V


        • 0
          vinhntndu    10:30 p.m. 2 Tháng 9, 2020

          thế thì chỉ cần tag implementation thôi chứ nhỉ


          • 0
            hhoangcpascal    10:33 p.m. 2 Tháng 9, 2020

            Là sao anh?


            • 0
              SPyofgame    8:58 a.m. 3 Tháng 9, 2020 ← đã chỉnh sửa

              \(xorsum[1, r] ⊕ xorsum[1, l - 1] = xorsum[l, r]\) mà đúng không anh nhỉ :v


            • 1
              vinhntndu    6:00 a.m. 3 Tháng 9, 2020

              dạng bài ấy, cần gì BIT


              • 1
                hhoangcpascal    9:37 a.m. 3 Tháng 9, 2020

                :V luyện tập bằng bit cũng được :V

        4 bình luận nữa