На одной из прошлых тренировок ИТМО я наткнулся на одну интересную задачу. В ней давалась строка и делались следующие запросы, перевернуть отрезок с L по R, найти LCP двух суффиксов i, j, длина строки 106, да и запросов тоже 105. На контесте тогда я не успел добраться до нее, заступорился на более простых задачах, а в дорешивании не смог придумать как решать. Подозрительное слово переворот так и напрашивает декартово дерево из хешей, но как его поддерживать не очень понятно =)
В общем, Хотелось бы узнать как решается эта замечательная задача =). Жду комментариев!=)
Комментарии (8)
+3
