So Sánh Chuỗi Con Cuộn

Binary-search Buổi 53 — String Hashing
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho chuỗi $S$ có độ dài $N$ và $Q$ truy vấn. Mỗi truy vấn gồm bốn số nguyên $l_1, r_1, l_2, r_2$, hãy so sánh theo thứ tự từ điển hai chuỗi con $S[l_1..r_1]$ và $S[l_2..r_2]$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
  • Dòng thứ hai chứa chuỗi $S$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $l_1, r_1, l_2, r_2$ ($1$-indexed).
Dữ liệu ra
  • Với mỗi truy vấn, in ra:
    • -1 nếu $S[l_1..r_1] < S[l_2..r_2]$
    • 0 nếu $S[l_1..r_1] = S[l_2..r_2]$
    • 1 nếu $S[l_1..r_1] > S[l_2..r_2]$
Ví dụ
Input Output
6 3\nabcabc\n1 3 4 6\n1 2 2 3\n1 3 1 3 0\n-1\n0
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le Q \le 10^5$
  • $1 \le l_1 \le r_1 \le N$, $1 \le l_2 \le r_2 \le N$
  • Chuỗi chỉ chứa ký tự in thường từ a đến z.
Draft saved