За O(1) пересчитывать количество инверсий при циклическом сдвиге влево
Есть перестановка, а также q запрос: найти количество инверсий в циклическом сдвиге этой перестановки на A элементов влево. Есть только одна проблема, размер перестановки 3⋅10^5. …