TLE-oj Cup Round 11 - Bộ ba tăng dần

Điểm: 1800 (thành phần)

Thời gian: 1.5s

Bộ nhớ: 512M

Input: TRILIS.inp

Output: TRILIS.out

Tác giả:

huyhau6a2

Dạng bài

Bạn được cho một dãy số $a$ gồm $n$ phần tử. Bạn phải thực hiện $q$ truy vấn, mỗi truy vấn gồm 2 số $l,r$ . Nhiệm vụ của bạn là với mỗi truy vấn, bạn cần phải đếm số bộ ba số $i,j,k$ thỏa mãn

$l\le i<j<k\le r$
$a_i<a_j<a_k$

Input, Output và Subtasks

Input: (TRILIS.inp)

Dòng đầu tiên gồm hai số nguyên dương $n \le 5000$ và $q \le 10^6$ .
Dòng tiếp theo gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$ ( $a_i\le 10^9$ ).
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $l, r$ mô tả mỗi truy vấn. ( $1\le l\le r\le n$ )

Output: (TRILIS.out)

Gồm $q$ dòng, dòng thứ $i$ là kết quả truy vấn thứ $i$ .

Subtasks

Subtask 1 $(10\%)$ : $n,q\le 100$ .
Subtask 2 $(10\%)$ : $n\le 100$ .
Subtask 3 $(10\%)$ : $n,q\le 500$ .
Subtask 4 $(15\%)$ : $n\le 500$ .
Subtask 5 $(15\%)$ : $n,q\le 2000$ .
Subtask 6 $(15\%)$ : $n\le 2000$ .
Subtask 7 $(25\%)$ : Không có giới hạn gì thêm.

Sample

Input (TRILIS.inp)

7 2
1 2 3 4 3 2 1
1 7
2 6

Output (TRILIS.out)

5
1

Note

Truy vấn 1: Các bộ ba thỏa mãn: $(1,2,3), (1,2,4), (1,2,5), (1,3,4), (2,3,4)$

Bình luận

Không có bình luận nào.