Dãy Con Không Giảm

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một dãy gồm $N$ số nguyên, mỗi số trong khoảng $[1, K]$ . Có $Q$ truy vấn: với mỗi truy vấn $(L, R)$ , đếm số dãy con không giảm (kể cả dãy rỗng) trong đoạn vị trí $L$ đến $R$ , modulo $10^{9} + 7$ .

Dãy con là một tập con các phần tử lấy theo thứ tự ban đầu (không nhất thiết liên tiếp). Dãy con không giảm là dãy con mà mỗi phần tử $\leq$ phần tử tiếp theo.

Dữ liệu vào

Dòng 1: $N$ và $K$ ( $1 \leq N \leq 5 \times 10^{4}$ , $1 \leq K \leq 20$ ).
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq K$ ).
Dòng 3: $Q$ ( $1 \leq Q \leq 2 \times 10^{5}$ ).
$Q$ dòng tiếp theo: mỗi dòng gồm $L_{i}$ và $R_{i}$ ( $1 \leq L_{i} \leq R_{i} \leq N$ ).

Dữ liệu ra

Với mỗi truy vấn, in kết quả trên một dòng.

Ví dụ

Input	Output	Giải thích
5 2 1 2 1 1 2 3 2 3 4 5 1 5	3 4 20	Truy vấn $[2, 3]$ : dãy con từ ${2, 1}$ : rỗng, ${2}$ , ${1}$ → 3 dãy không giảm.

Bình luận

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