Đếm giá trị trong khoảng trên đường đi
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho cây gốc $1$ gồm $n$ đỉnh, đỉnh $i$ có giá trị $a_i$. Mỗi truy vấn $(u,v,A,B)$: đếm số đỉnh $w$ trên đường đi từ $u$ đến $v$ sao cho $A\le a_w\le B$.
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $p_1,\dots,p_n$ ($p_1=0$, $p_i<i$). Dòng ba: $n$ số $a_i$. Sau đó $q$ dòng: $u,v,A,B$ với $A\le B$.
Dữ liệu ra
Với mỗi truy vấn in số đỉnh thỏa mãn.
Ví dụ
Input
5 5
0 1 1 3 4
8 -9 0 -10 -1
3 5 -12 -4
1 2 -8 -6
4 2 -9 -7
4 1 -4 8
3 2 -1 12
Output
1
0
1
2
2
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|,|A|,|B|\le 10^9$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion