Есть перестановка, а также q запрос: найти количество инверсий в циклическом сдвиге этой перестановки на A элементов влево. Есть только одна проблема, размер перестановки 3⋅10^5. Просто найти количество инверсий у меня получается за n⋅log(n), но как отвечать на запрос при сдвиге я не знаю. Если у вас какие-либо идеи, пожалуйста, пишите, буду благодарен за любую помощь!
Если у вас происходит сдвиг на A, т.е. перестановка частей на A-м месте
L R
_______ _______________
в
R L
_______________ _______
то при этом внутренние инверсии в части L остаются на месте, внутренние инверсии в части R остаются на месте, а инверсии между частями инвертируются. Т.е. если было K(A) взаимных инверсий, то они исправляются, однако новое количество взаимных инверсий Len(L)*Len(R)-K(A), так что изменение количества будет
DeltaInv = Len(L)*Len(R)-2*K(A) = A*(N-A) - 2*K(A)
Пример
[1,3,7, 0,2,4,5,6,8,9] =>
[0,2,4,5,6,8,9, 1,3,7]
было 8 инверсий, становится 13, изменение на 5 (3*7-2*8)
[7,3,1, 0,2,4,6,8,9,5] =>
[0,2,4,6,8,9,5, 7,3,1]
было 14, становится 19, изменение на те же 5
(поскольку количество взаимных инверсий сохранено)
Остаётся ;) предпосчитать количество взаимных инверсий левой и правой части исходной перестановки на каждом индексе и сохранить, тогда каждый запрос будет обработан за O(1)