Bedao Mini Contest 26 - NAX

Xem dạng PDF

Gửi bài giải


Điểm: 0,01 (OI)
Giới hạn thời gian: 1.2s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~A~ có ~N~ phần tử không âm. Định nghĩa ~f(x, A)~ (với ~x~ là một số nguyên dương ~\leq |A|~) là ~AND~ lớn nhất của mọi dãy con của ~A~ có độ dài ~x~.

Dãy con của A có thể được tạo ra bằng cách xóa đi một vài (có thể là không) phần tử từ dãy ban đầu, các phần tử còn lại phải đảm bảo tính thứ tự ban đầu của nó. Ví dụ, với dãy ~[5, 1, 3, 4]~ thì các dãy con có thể là ~[3], [5, 4], [5, 1, 4]~, nhưng dãy ~[3, 1]~ thì không.

Có ~M~ truy vấn trên dãy ~A~, mỗi truy vấn thuộc 1 trong 3 loại:

  • ~1 \space v:~ Chèn giá trị ~v~ vào cuối dãy ~A~.

  • ~2 \space v:~ Xóa một phần tử mang giá trị ~v~ ra khỏi ~A~, dữ liệu đảm bảo luôn tồn tại ~v~ trong dãy trước khi xóa.

  • ~3 \space x~: Tính ~f(x, A)~.

Input

  • Dòng đầu gồm 3 số nguyên ~N, M, k~ ~(1 \leq N, M \leq 75000, 1 \leq k \leq 18)~.

  • Dòng tiếp theo gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(0 \leq a_i < 2^k \space)~ là các phần tử ban đầu của dãy ~A~.

  • Mỗi dòng trong ~M~ dòng tiếp theo chứa 1 trong 3 truy vấn ~1 \space v~, ~2 \space v~, hoặc ~3 \space x~ ~(0 \leq v < 2 ^ k, 1 \leq x \leq |A|~).

Output

  • Với mỗi truy vấn loại ~3~, in ra một số nguyên duy nhất là kết quả của ~f(x, A)~ trên một dòng.

Scoring

Subtask Điểm Giới hạn
1 ~10~ ~1 \leq |A| \leq 12~ tại mọi thời điểm
2 ~30~ Không có truy vấn loại ~1~ và ~2~
3 ~60~ Không có ràng buộc gì thêm

Sample Input 1

4 7 3
6 7 5 2
3 2
3 3
1 7
3 3
2 7
2 6
3 2

Sample Output 1

6
4
6
5

Notes

Những dãy con mang lại kết quả tối ưu là ~(6, 7); (6, 7, 5); (6, 7, 7); (7, 5)~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.