SubArray中的相等元素

我有一個包含N個元素的數組，我需要找到索引中等於元素的子陣列之間的距離;我們將以查詢的形式得到（L R），其中L是子數組的起始索引，R是結束索引。數組元素的總數可以是N < = 10^5和查詢Q < = 10^5。SubArray中的相等元素

例如：

7 

0 4 0 8 0 32 0 

2 

0 2 

0 5

//答案第一查詢將是2（索引2-0）

爲第二查詢

//答案將是8（索引（2-0） +（4-2）+（4-0））

編輯：我不期待的代碼

來源

2015-05-14 Ryan Stein

如果您不希望代碼，請不要添加編程語言標籤。 –

這是sqrt分解的工作。

我們希望保持狀態，使我們能夠回答當前範圍並將當前範圍的端點向上或向下調整。爲此，我們維護從元素到（當前範圍內該元素的所有索引的總和，當前範圍內出現的次數）的映射。我們也保持當前的答案。要調低下端點以包含索引爲i的元素x，我們通過範圍內的索引之和來增加答案 - （在範圍* i中x的發生次數），然後增加總數和出現次數。其他三個操作是相似的。

要實現sqrt分解，我們按（低端點樓層除以sqrt N，高端端點）對查詢進行排序，並按順序調整範圍。

來源

2015-05-14 20:35:10

創建一個映射，其關鍵是數組的元素，值是它們出現的位置列表（您的示例將變爲{0: [0, 2, 4, 6], 8: [3], 4: [1], 32: [5]}）。這些羣體形成無關的問題。找到答案的一種方法是將它們視爲maximum flow problems，其中每個索引形成兩個頂點。
每個索引都連接到它後面的所有索引以及它之前的所有索引都連接到它。邊的權重是數組中元素的距離，即兩個索引之間的差異。所有「源」頂點連接到一個無限源，所有「目標」頂點連接到一個接收器。
所有問題的最大流量值的總和就是您正在查找的總和。

舉個例子，讓我們使用索引項0：

  +-------- 0 ----------+  0 --------+ 
      |      |    | 
      |      |    | 
Source ----+-------- 2 -------+ +----> 2 --------+---- Sink 
      |     | |    | 
      |     | |    | 
      +-------- 4 ----+ +--+----> 4 --------+ 
      |    | | |    | 
      |    | | |    | 
      +-------- 6  +--+--+----> 6 --------+ 


Weight of arc (u, v) = v - u

注意邊緣的數量增長爲V^2，因爲每一條邊對應於你必須以計算做一個差異結果，這是在每個指數和它的所有後繼者之間。這使得解決方案O（n^3）的複雜性比天真算法更差，它只是從另一個角度觀察事物的好方法:)

來源

2015-05-14 21:23:10 BlackBear

SubArray中的相等元素

回答

相關問題