Truy vấn khoảng giá trị (Range Interval Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $x_1,x_2,\ldots,x_n$. Mỗi truy vấn cho bốn số $a,b,c,d$. Hãy đếm số chỉ số $i$ thỏa đồng thời $a\le i\le b$ và $c\le x_i\le d$.

Dữ liệu vào

Dòng đầu chứa $n,q$. Dòng thứ hai chứa $n$ số $x_i$. Mỗi trong $q$ dòng sau chứa $a,b,c,d$.

Kết quả

In kết quả của từng truy vấn trên một dòng.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le 2\cdot10^5$
• $1\le x_i\le10^9$
• $1\le a\le b\le n$
• $1\le c\le d\le10^9$

Ví dụ

Input

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

Output

2
0
8
1

Giải thích

Truy vấn đầu xét các vị trí $2..4$, nhận được [2,4,5]. Chỉ 2 và 4 nằm trong khoảng giá trị $[2,4]$, nên đáp án là $2$.