Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
E. Цагаан толгойн сэлгэлт
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n$ урттай Англи цагаан толгойн эхний $k$ жижиг үсгээс бүрдэх $s$ тэмдэгт мөр өгөгдсөн.
Бид $q$ тэмдэгт мөрийн $c$ давталтаас бүрдэх тэмдэгт мөр буюу $q$ тэмдэгт мөрийн $c$ давталтыг тэмдэгт мөр хэлбэрээр тодорхойлно. Жишээлбэл "$acbacbacbacb$" тэмдэгт мөр бол $"abc"$ тэмдэгт мөрийг $4$ удаа давтсан тэмдэгт мөр.
Хэрвээ $b$ тэмдэгт мөр $a$ тэмдэгт мөрийн зарим үсгийг арилгаад гарч байвал $a$ тэмдэгт мөрийг $b$ тэмдэгт мөрийг дэд дараалал хэлбэрээр өөртөө агуулж байна гэж хэлье.
$p$-г Англи цагаан толгойн эхний $k$ жижиг үсгүүдийг сэлгэж үүссэн тэмдэгт мөр гэе. Бид $p$ тэмдэгт мөрийн $d(p)$ ширхэг давталт $s$ тэмдэгт мөрийг дэд дараалал хэлбэрээр өөртөө агуулж чадах хамгийн бага бүхэл тоог олдог $d(p)$ функцийг тодорхойлно.
$s$ тэмдэгт мөрөнд хийж болох дараах хоёр төрлийн $m$ үйлдэл байгаа:
- $l_{i}$-с $r_{i}$ хүртэлх байрлалд байгаа бүх тэмдэгтүүдийг $c_{i}$ тэмдэгтээр солих.
- Англи цагаан толгойн эхний $k$ жижиг үсгүүдийг сэлгэж үүссэн өгөгдсөн $p$-н хувьд $d(p)$ функцийн утгыг ол.
Бүх үйлдлүүд оролтонд харагдаж буй дарааллаараа ээлжлэн хийгдэнэ. Таны ажил бол хоёр дахь төрлийн үйлдэл бүрийн хувьд $d(p)$ функцийн утгыг тодорхойлох юм.
Оролт
Эхний мөрөнд гурван эерэг бүхэл тоон утга $n$, $m$ ба $k$ ($1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10$) байх ба харгалзан $s$ тэмдэгт мөрийн урт, үйлдлийн тоо, цагаан толгойн үсгийн хэмжээ. Хоёр дахь мөрөнд $s$ тэмдэгт мөр өөрөө байна.
Дараагийн $m$ мөр бүрт нэг үйлдлийн тодорхойлолт байна:
- Эхний төрлийн үйлдэл нь $1$-ээр эхлэх ба залгуулаад $l_{i}$, $r_{i}$, $c_{i}$ байх ба $l_{i}$-с $r_{i}$ байрлалд байгаа бүх тэмдэгтийг $c_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) тэмдэгтээр солихыг заах ба $c_{i}$ нь Англи цагаан толгойн эхний $k$ жижиг үсгийн нэг байна.
- Хоёр дахь төрлийн үйлдэл нь $2$-оор эхлэх ба залгуулаад Англи цагаан толгойн эхний $k$ жижиг үсгийг сэлгэж үүссэн тэмдэгт мөр байна.
Гаралт
Хоёр дахь төрлийн үйлдэл бүрийн хувьд $d(p)$ функцийн утга.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
7 4 3 abacaba 1 3 5 b 2 abc 1 4 4 c 2 cba
Гаралт
6 5
Тэмдэглэл
Эхний үйлдлийн дараа тэмдэгт мөр $s$ нь $abbbbba$ болно.
Хоёр дахь үйлдлийн хариу нь $abc$-н $6$ давталт: $ABcaBcaBcaBcaBcAbc$.
Гурав дахь үйлдлийн дараа тэмдэгт мөр $s$ нь $abbcbba$ болно.
Дөрөвдүгээр үйлдлийн хариу нь $cba$-н $5$ давталт: $cbAcBacBaCBacBA$.
Том үсэгнүүд нь $s$-н тэмдэгтүүдийн тохиолдож буй тохиолдлууд юм.