Dãy Con Tốt Nhất

Đ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

Farmer John có một xâu nhị phân độ dài $N$ , ban đầu toàn số 0. Anh thực hiện $M$ thao tác lật (flip), mỗi thao tác đảo tất cả ký tự từ vị trí $l$ đến $r$ ( $0 \to 1$ , $1 \to 0$ ).

Sau đó trả lời $Q$ truy vấn. Mỗi truy vấn cho ba số $l, r, k$ : tìm dãy con (subsequence) có thứ tự từ điển lớn nhất độ dài $k$ từ đoạn $[l, r]$ của xâu. Kết quả được biểu diễn dưới dạng giá trị nhị phân modulo $10^{9} + 7$ .

Cụ thể, nếu dãy con tìm được là $s_{1} s_{2} \dots s_{k}$ , in ra $\sum_{i = 0}^{k - 1} 2^{i} \cdot s_{k - i} (\mod 10^{9} + 7)$ .

Dữ liệu vào

Dòng 1: Ba số nguyên $N, M, Q$ ( $1 \leq N \leq 10^{9}$ , $1 \leq M \leq 2 \times 10^{5}$ , $1 \leq Q \leq 2 \times 10^{5}$ )
$M$ dòng tiếp theo: Hai số $l, r$ — đoạn cần lật ( $1 \leq l \leq r \leq N$ )
$Q$ dòng tiếp theo: Ba số $l, r, k$ ( $1 \leq l \leq r \leq N$ , $1 \leq k \leq r - l + 1$ )

Dữ liệu ra

$Q$ dòng, mỗi dòng là kết quả của truy vấn tương ứng modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{9}$
$1 \leq M, Q \leq 2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
5 3 9 1 5 2 4 3 3 1 5 5 1 5 4 1 5 3 1 5 2 1 5 1 2 5 4 2 5 3 2 5 2 2 5 1	21 13 7 3 1 5 5 3 1	Sau 3 thao tác lật, xâu trở thành "10101". Truy vấn $(1, 5, 5)$ : dãy con duy nhất là "10101" = 21. Truy vấn $(1, 5, 4)$ : dãy con lớn nhất là "1101" = 13.

Bình luận

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