VO 16 Bài 2 - XOR dãy số

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
VNOI Online 2016
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Cho dãy ~A~ gồm ~N~ số nguyên không âm. Ta lần lượt thực hiện ~Q~ thao tác trên tập hợp này:

  • XOR ~x~: Với mọi ~i~, ~A_i = A_i~ xor ~x~
  • FIND ~k~: Tìm số lớn thứ ~k~ trong dãy ~A~.

Yêu cầu: Thực hiện các truy vấn trên.

Input

  • Dòng đầu tiên ghi ~2~ số ~N~ và ~Q~.
  • Dòng thứ hai ghi ~N~ số là giá trị ban đầu của dãy ~A~.
  • Tiếp theo là ~Q~ dòng, mỗi dòng ghi ~1~ trong ~2~ loại truy vấn.

Output

Với mỗi truy vấn loại FIND, in ra kết quả tìm được.

Giới hạn

Subtask ~1~ ~(25\%)~

  • ~N~, ~Q \leq 5000~
  • ~0 \leq A_i \leq 10^{9}~
  • ~0 \leq x \leq 10^{9}~.

Các subtask ~2~, ~3~ và ~4~ tiếp theo đều có

  • ~N \leq 10^{5}~
  • ~Q \leq 10^{5}~
  • ~0 \leq A_i \leq 10^{9}~

Subtask ~2~ ~(40\%)~

  • ~0 \leq x \leq 100~

Subtask ~3~ ~(10\%)~:

  • ~0 \leq x \leq 10^{9}~
  • ~x~ luôn có dạng ~2 \times k~

Subtask ~4~ ~(25\%)~:

  • ~0 \leq x \leq 10^{9}~

Sample Input

4 9
1 2 3 4
FIND 1
FIND 2
FIND 3
FIND 4
XOR 6
FIND 1
FIND 2
FIND 3
FIND 4

Sample Output

4
3
2
1
7
5
4
2

Note

Giải thích

Trước truy vấn XOR 6, dãy số là 1 2 3 4.

Sau truy vấn XOR 6, dãy số là 7 4 5 2.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.