trang chủ / bài tập / divpairq

Cặp ước trong đoạn

Cho dãy $p = p_{1}, p_{2}, \dots, p_{n}$ gồm $n$ số nguyên đôi một phân biệt, với $1 \leq p_{i} \leq n$ .

Bạn cần trả lời $m$ truy vấn. Truy vấn thứ $i$ là một cặp số nguyên $l_{i}, r_{i}$ : hãy đếm số cặp chỉ số $(q, w)$ với $l_{i} \leq q \leq r_{i}$ và $l_{i} \leq w \leq r_{i}$ sao cho $p_{q}$ là ước của $p_{w}$ .

Cặp $(q, w)$ và cặp $(w, q)$ được xem là khác nhau, và trường hợp $q = w$ cũng được tính vì mọi số đều là ước của chính nó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa $n$ số nguyên phân biệt $p_{1}, p_{2}, \dots, p_{n}$ .
$m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_{i}$ và $r_{i}$ .

Dữ liệu ra

In ra $m$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$ , theo đúng thứ tự trong dữ liệu vào.

Ràng buộc

$1 \leq n, m \leq 2 \cdot 10^{5}$
$1 \leq p_{i} \leq n$ , các $p_{i}$ đôi một phân biệt
$1 \leq l_{i} \leq r_{i} \leq n$

Ví dụ

Input	Output	Giải thích
1 1 1 1 1	1	Chỉ có cặp $(1, 1)$ vì $p_{1} = 1$ là ước của chính nó.
10 9 1 2 3 4 5 6 7 8 9 10 1 10 2 9 3 8 4 7 5 6 2 2 9 10 5 10 4 10	27 14 8 4 2 1 2 7 9	Với truy vấn $1 10$ , ta đếm mọi cặp $(u, v)$ với $u$ là ước của $v$ và cả hai đều thuộc ${1, \dots, 10}$ : có $10$ cặp $u = v$ cùng $17$ cặp $u < v$ , tổng cộng $27$ . Với truy vấn $5 6$ chỉ còn hai giá trị $5$ và $6$ , không giá trị nào là ước của giá trị kia nên đáp án là $2$ .
4 4 4 2 3 1 3 4 1 4 1 2 4 4	3 8 3 1	Truy vấn $3 4$ lấy hai giá trị $3$ và $1$ : ngoài hai cặp $q = w$ còn có cặp $(4, 3)$ vì $p_{4} = 1$ là ước của $p_{3} = 3$ . Truy vấn $1 4$ lấy cả bốn giá trị $4, 2, 3, 1$ : bốn cặp $q = w$ , ba cặp bắt đầu từ giá trị $1$ , và cặp $(2, 1)$ vì $2$ là ước của $4$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 8,00một phần

Giới hạn thời gian 2.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig