主页 / 问题 / 1536751
Accepted
Alexander
Asked:2023-08-20 13:27:41 +0000 UTC2023-08-20 13:27:41 +0000 UTC

O(1) 循环左移时重新计算反转次数

  • 772

有一个排列，还有q查询：求这个排列向左循环移位A个元素的反转次数。只有一个问题，排列大小是 3⋅10^5。我只能找到 n⋅log(n) 中的反转次数，但我不知道在移位时如何回答查询。如果您有任何想法，请写信，我将不胜感激！

c++

1 个回答

  1. Best Answer

    如果您的班次是A，即 A重新排列第- 个位置的零件

       L          R
_______ _______________

    V

            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)中处理

    • 4

相关问题