Lý thuyết: 896C CF

Cho dãy số nguyên không âm ~a_1,a_2,\ldots,a_n~ và ~q~ truy vấn. Mỗi truy vấn gồm bốn số nguyên ~l,r,k,\mathrm{val}~. Thực hiện lần lượt hai thao tác sau:

1. In ra số lượng chỉ số ~i~ thỏa mãn ~l\le i\le r~ và ~a_i\le k~.
2. Với mọi chỉ số ~i~ thuộc đoạn ~[l,r]~, cập nhật ~a_i\leftarrow\max(a_i,\mathrm{val})~.

Gọi ~a_i^{(0)}~ là giá trị ban đầu của phần tử thứ ~i~, và ~\mathrm{val}_j~ là giá trị cập nhật của truy vấn thứ ~j~. Dữ liệu bảo đảm:

~\max\limits_{1\le i\le n}a_i^{(0)}\le\mathrm{val}_1\le\mathrm{val}_2\le\cdots\le\mathrm{val}_q~.

Ngưỡng đếm ~k~ có thể thay đổi tùy ý giữa các truy vấn, độc lập với giá trị cập nhật ~\mathrm{val}~. Các giá trị cập nhật liên tiếp được phép bằng nhau.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n,q~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,\ldots,a_n~ là các giá trị ban đầu của dãy.
• Mỗi dòng trong ~q~ dòng tiếp theo chứa bốn số nguyên ~l,r,k,\mathrm{val}~ mô tả một truy vấn.

Các truy vấn được xử lý theo đúng thứ tự trong dữ liệu vào. Mỗi tệp dữ liệu chứa một bộ dữ liệu duy nhất.

Dữ liệu ra

In ra ~q~ dòng. Dòng thứ ~j~ chứa số lượng phần tử thỏa mãn điều kiện đếm của truy vấn thứ ~j~, tính trước khi thực hiện cập nhật của truy vấn đó.

Giới hạn

• ~1\le n,q\le 10^5~.
• ~0\le a_i^{(0)}\le 10^9~ với mọi ~1\le i\le n~.
• ~1\le l\le r\le n~ trong mỗi truy vấn.
• ~0\le k,\mathrm{val}\le 10^9~ trong mỗi truy vấn.
• ~\max\limits_{1\le i\le n}a_i^{(0)}\le\mathrm{val}_1\le\mathrm{val}_2\le\cdots\le\mathrm{val}_q~.

Ví dụ

Dữ liệu vào

5 4
1 2 3 4 5
1 5 3 5
2 4 5 7
1 5 5 8
1 5 7 9

Dữ liệu ra

3
3
2
0

Giải thích

• Truy vấn thứ nhất: trong đoạn ~[1,5]~ có ba phần tử không vượt quá ~3~. Sau cập nhật, dãy trở thành ~[5,5,5,5,5]~.
• Truy vấn thứ hai: cả ba phần tử trong đoạn ~[2,4]~ đều không vượt quá ~5~. Sau cập nhật, dãy trở thành ~[5,7,7,7,5]~.
• Truy vấn thứ ba: trong đoạn ~[1,5]~ có hai phần tử không vượt quá ~5~. Sau cập nhật, dãy trở thành ~[8,8,8,8,8]~.
• Truy vấn thứ tư: mọi phần tử trong đoạn ~[1,5]~ đều lớn hơn ~7~, nên đáp án là ~0~. Sau cập nhật, dãy trở thành ~[9,9,9,9,9]~.