Ở trong bài viết này, tất cả các xâu đều được đánh chỉ số từ \(1.\) Truy vấn 1 i c là truy vấn loại \(1\) và truy vấn 2 l r t là truy vấn loại \(2\).

Subtask 1

• Với mỗi truy vấn loại \(1\) thực hiện thay đổi kí tự xâu \(s\) trong \(O(1)\).
• Với mỗi truy vấn loại \(2\) duyệt \(i\) từ vị trí \(l\) đến \(r\) rồi đếm số lượng vị trí \(i\) thỏa mãn \(s[i] = t[(i-l) \mod |t| + 1]\).

Độ phức tạp: \(O\left(q \cdot n\right)\).

Subtask 2

Ở truy vấn \(2\) vì \(|t| = 1\) nên ta chỉ cần đếm số lượng kí tự \(t[1]\) trong xâu \(s\) từ \(l\) đến \(r\).

Vì tất cả các xâu chỉ có \(4\) kí tự nên ta có thể dựng \(4\) mảng độ dài \(|s|\), mỗi mảng tương ứng với một kí tự và giá trị của phần tử thứ \(i\) bằng \(1\) nếu \(s[i]\) trùng với kí tự đó và bằng \(0\) nếu ngược lại.

Bằng cách dùng các cấu trúc dữ liệu như IT hoặc BIT, ta có thể xử lí truy vấn loại \(1\) và trả lời truy vấn loại \(2\) trong \(O\left(\log\left(n\right)\right)\).

Độ phức tạp: \(O\left(q \cdot \log\left(n\right)\right)\).

Subtask 3

Xét một xâu \(t\), xâu \(t' = ttt\ldots\) là xâu chứa các xâu \(t\) được viết liên tiếp. Nếu như các kí tự được đánh số từ \(1\), khi đó các kí tự \(t[i]\) \((1 \le i \le |t|)\) sẽ lặp lại trên xâu \(t'\) theo một khoảng là \(|t|\), tức là \(t'[i] = t'[i+|t|] = t'[i+2 \cdot |t|] = t'[i+3 \cdot |t|] = \ldots\).

Nếu như viết xâu \(t'\) dưới xâu \(s\) bắt đầu từ vị trí \(l\) đến \(r\) thì để đếm số lượng cặp kí tự trùng nhau, ta có thể duyệt hết từng kí tự của xâu \(t\) và đếm số lượng số \(1\) trên mảng ứng với kí tự đó (\(4\) mảng đã dựng ở subtask 2) ở các vị trí cách nhau một khoảng là \(|t|\).

Để ý rằng vì khoảng cách giữa các vị trí tối đa là \(|t| \le 10\). Vì vậy ta có thể lưu \(10\) bản sao của từng mảng trong \(4\) mảng ở trên. Bản sao thứ \(k\) của mảng ứng với kí tự nào đó sẽ được sắp xếp lại sao cho các phần tử đầu là các phần tử ở vị trí \(i\) thỏa mãn \(i \equiv 1 \pmod{k}\) rồi tiếp theo sau đó là các vị trí \(i\) thỏa mãn \(i \equiv 2 \pmod{k}\) và cuối cùng là \(i \equiv k \pmod{k}\).

Khi đó khi thực hiện truy vấn loại \(1\), cụ thể là thay kí tự \(c\) thành \(c'\), ta sẽ phải cập nhật cho \(10\) mảng bản sao ứng với kí tự \(c\) và \(10\) mảng bản sao ứng với kí tự \(c'\) trong \(O(\log(n))\). Còn khi thực hiện truy vấn \(2\), ta có thể duyệt từng kí tự \(t[i]\) \((1 \le i \le |t|)\) và tìm tổng đoạn con liên tiếp tương ứng trong mảng bản sao thứ \(|t|\) ứng với kí tự \(t[i]\) trong \(O(\log(n))\) rồi tính tổng các kết quả đó lại.

Độ phức tạp: \(O\left(q \cdot \log\left(n\right) \right)\).