Đếm giá trị trong khoảng trên đường đi

Buổi 30 — Persistent Segment Tree
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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.
Draft saved