Nộp bài
Điểm:
1800 (thành phần)
Thời gian:
1.5s
Bộ nhớ:
512M
Input:
TRILIS.inp
Output:
TRILIS.out
Tác giả:
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