Vượt Qua Ngưỡng · canuc80k5903 · Thuật toán Canuc80k

Cho một mảng tĩnh gồm $n$ số nguyên. Mỗi truy vấn có dạng $l$ $r$ $k$ và yêu cầu đếm số vị trí $i$ thỏa mãn đồng thời

$l \leq i \leq r$ và $a_{i} > k$ .

Dấu so sánh là nghiêm ngặt: phần tử có giá trị đúng bằng $k$ không được đếm.

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên của mảng.
Dòng thứ ba chứa số nguyên $q$ , là số truy vấn.
Mỗi dòng trong $q$ dòng tiếp theo chứa ba số nguyên $l, r, k$ .

Output

Với mỗi truy vấn, in số phần tử lớn hơn $k$ trong đoạn $[l, r]$ trên một dòng.

Constraints

$1 \leq n \leq 3 \cdot 1 0^{4}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .
$1 \leq q \leq 2 \cdot 1 0^{5}$ .
$1 \leq l \leq r \leq n$ .
$1 \leq k \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n, q \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6
5 1 9 5 2 8
5
1 6 5
2 5 4
3 6 8
1 3 9
4 4 1

Output

Giải thích: Trong toàn mảng, chỉ $9$ và $8$ lớn hơn $5$ . Ở truy vấn thứ tư, không phần tử nào của đoạn $[1, 3]$ lớn hơn $9$ , còn đoạn một phần tử $[4, 4]$ chứa $5 > 1$ nên cho kết quả $1$ .

Ý tưởng: Nén các giá trị của mảng. Tạo root[i] là cây tần suất của tiền tố a_1..a_i. Mỗi gốc mới được tạo bằng cách tăng tần suất tại hạng của a_i.
Ý tưởng: Với truy vấn [l,r,k], dùng upper_bound để tìm hạng đầu tiên có giá trị lớn hơn k. Hiệu số đếm giữa root[r] và root[l-1] trên phần miền từ hạng này đến cuối chính là đáp án.
Ý tưởng: Đúng đắn. Hai cây tiền tố triệt tiêu mọi vị trí trước l và giữ đúng các vị trí từ l đến r. upper_bound loại cả các giá trị bằng k, nên phần miền được cộng chứa chính xác và chỉ những phần tử lớn hơn ngưỡng.
Ý tưởng: Độ phức tạp. Tiền xử lý O(n log n), mỗi truy vấn O(log n), bộ nhớ O(n log n).