Truy Vấn LCP Trên Đoạn

Buổi 56 — Suffix Array & LCP
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề 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|$
Draft saved