Тема: timus 1553
http://acm.timus.ru/problem.aspx?space=1&num=1553
Здравствуйте!
Собственно сабж. На первый взгляд я подумал что все просто - такая же задача как и LCA при помощи RMQ, только ищем максимум по уровню радиации. Но если разобрать пару примеров - становиться понятно что эта идея неверна. Кстате говоря если бы нужно было искать сумму значений радиации - то она бы так и решалась, на этом сайте есть описание этой задачи.
Собственно в обсуждениях этой задачи на тимусе - кто то, что то писал, но честно говоря я толком ничего не понял. Точнее там пишут, что можно применить sqrt-декомпозицию, понятно что при поиске максимум некоторые группы целиком пропускаем - это собственно принцип декомпозиции, но вот толком как это дело обновлять чего то непонятно....
В общем кто нибудь может рассказать внятный алгоритм или как то чего то намекнуть?