Bedao Mini Contest 09 - SOR

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.