Bedao Mini Contest 09 - SOR

Xem dạng PDF

Gửi bài giải


Điểm: 0,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
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

Dế Mèn mới được học về toán tử OR, anh đang muốn luyện tập bằng một bài liên quan tới toán tử OR trên trang web VNOJ. Nhưng bài toán này quá khó nên Dế Mèn muốn nhờ các bạn giúp :

Xét dãy ~a~ gồm ~n~ phần tử. Thực hiện ~q~ truy vấn sau trên dãy ~a~.

  • ~u \ \ \, v~ : ~a_u = v~

Sau mỗi truy vấn, in ra độ dài của dãy con liên tiếp dài nhất của dãy ~a~ thỏa mãn biểu thức :

  • ~a_l + a_{l+1} + ... + a_r = a_l \ | \ a_{l+1} \ | \ ... \ | \ a_r~. Trong đó "~|~" là toán tử OR.

Input

  • Dòng đầu tiên nhập vào hai số nguyên dương ~n~ và ~q~ là độ dài của dãy ~a~ và số truy vấn cần trả lời ~(1 \le n,\ q \le 10^5)~.
  • Dòng thứ hai nhập vào ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. ~(1 \le a_i \le 10^9)~
  • ~q~ dòng tiếp theo, mỗi dòng nhập hai số nguyên dương ~u~ và ~v~ tương ứng với truy vấn gán ~a_u = v~. ~(1 \le u \le n, 1 \le v \le 10^9)~

Output

  • In ra ~q~ dòng, dòng thứ ~i~ trả lời câu hỏi sau truy vấn thứ ~i~.

Sample Input

5 4
1 2 3 4 5
1 3
1 1
3 8
4 6

Sample Output

2
2
4
3

Note

  • Sau truy vấn ~2~, dãy con dài nhất thỏa điều kiện là dãy từ ~1~ đến ~2~.
  • Sau truy vấn ~3~, dãy con dài nhất thỏa điều kiện là dãy từ ~1~ đến ~4~.

Subtask

  • ~25\%~ số test có ~n,\ q \le 10^2~
  • ~25\%~ số test tiếp theo có ~n,\ q \le 10^3~
  • ~50\%~ số test còn lại không có điều kiện gì thêm

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.