Truy Vấn LCP Trên Đoạn
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho xâu $S$ gồm các chữ cái in thường. Xây dựng mảng hậu tố và mảng LCP. Sau đó trả lời $Q$ truy vấn, mỗi truy vấn cho hai số $l, r$ ($1$-indexed trong mảng hậu tố) và yêu cầu tìm giá trị nhỏ nhất trong mảng LCP trên đoạn $[l, r-1]$ (tức là $\min(lcp[l], lcp[l+1], \ldots, lcp[r-1])$). Đây chính là LCP chung của tất cả các hậu tố từ vị trí $l$ đến $r$ trong mảng hậu tố.
Sử dụng bảng thưa (sparse table) để trả lời mỗi truy vấn trong $O(1)$.
Dữ liệu vào
Dòng đầu tiên chứa xâu $S$ ($1 \le |S| \le 2 \times 10^5$). Dòng thứ hai chứa số nguyên $Q$ ($1 \le Q \le 2 \times 10^5$). $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l, r$ ($1 \le l < r \le |S|$).
Dữ liệu ra
Với mỗi truy vấn, in ra giá trị nhỏ nhất trên đoạn LCP.
Ví dụ
| Input | Output |
|---|---|
| banana\n2\n1 3\n2 6 | 1\n0 |
Giới hạn
- $1 \le |S| \le 2 \times 10^5$
- $1 \le Q \le 2 \times 10^5$
- $1 \le l < r \le |S|$
Community Discussion