#1477. XQUERY - Truy vấn

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Alice là một kĩ sư đang làm việc trên một loại vi xử lí mới. Bộ vi xử lí làm việc trên tập số nguyên không âm 𝑆 (các số có thể được xuất hiện nhiều lần) để mô phỏng sự sống trong Matrix. Ban đầu tập 𝑆 là rỗng, bộ vi xử lí có các loại truy vấn sau:

  • Truy vấn dạng: 0\ 𝑥 , truy vấn này thêm một số nguyên 𝑥 vào 𝑆\ (0 ≤ 𝑥 ≤ 10^5) . Nếu giá trị 𝑥 đã có trong 𝑆 thì truy vấn này vẫn được thực hiện;
  • Truy vấn dạng: 1\ 𝑥 , truy vấn này xóa một số 𝑥 khỏi 𝑆\ (0 ≤ 𝑥 ≤ 10^5) . Nếu giá trị 𝑥 không thuộc 𝑆 thì truy vấn này không cần làm gì. Nếu giá trị 𝑥 xuất hiện nhiều lần trong 𝑆 thì truy vấn này chỉ xóa đi một lần;
  • Truy vấn dạng: 2\ 𝑎 , truy vấn này thay đổi cả phần tử của 𝑆 với sự ảnh hưởng của 𝑎\ (0 ≤𝑎 ≤ 10^5) . Cụ thể, với 𝑥 thuộc 𝑆 được thay bằng 𝑥\ {XOR}\ 𝑎 . Phép toán XOR (trong các ngôn ngữ lập trình thường được kí hiệu là ^) được định nghĩa như sau: Kết quả của phép toán XOR giữa hai số nguyên không âm 𝑥 𝑦 là một số nguyên không âm 𝑧 trong đó bit thứ 𝑖 trong biểu diễn nhị phân của 𝑧 sẽ là 0 khi bit thứ 𝑖 trong biểu diễn nhị phân của 𝑥 𝑦 bằng nhau (đồng thời bằng 0 hoặc 1 ), ngược lại bit thứ 𝑖 trong biểu diễn nhị phân của 𝑧 sẽ là 1 ;
  • Truy vấn dạng: 3\ 𝑘 , truy vấn này tính tổng 𝑘 phần tử nhỏ nhất trong 𝑆\ (0 ≤ 𝑘 ≤ |𝑆|) .

Để kiểm tra trước khi đưa vào sử dụng, Alice muốn bạn lập trình xử lí các kiểm tra lại các truy vấn.

Dữ liệu vào:

  • Dòng thứ nhất chứa số nguyên dương 𝑄 ;
  • Dòng thứ 𝑖\ (1 ≤ 𝑖 ≤ 𝑄) trong 𝑄 dòng tiếp theo chứa hai số nguyên mô tả loại truy vấn.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra:

  • Với mỗi truy vấn loại 3 , hãy in ra tổng của 𝑘 phần tử nhỏ nhất trong 𝑆 trên một dòng.

Ví dụ:

Dữ liệu vào:

6
0 1
2 2
0 3
3 2
2 2
3 1

Dữ liệu ra:

6
1

Giới hạn:

  • 25\% số điểm của bài thỏa mãn: 𝑄 ≤ 1000 ;
  • 25\% số điểm khác của bài thỏa mãn: 𝑄 ≤ 10^5 và không có truy vấn loại 2 ;
  • 25\% số điểm khác của bài thỏa mãn: 𝑄 ≤ 10^5 𝑘 ≤ 10 ;
  • 25\% số điểm còn lại của bài thỏa mãn: 𝑄 ≤ 10^5 .