用查詢更新數組

Question

最初有N的學生都有0分。現在我們在每個查詢中給出Q查詢，我們增加A index students by B的標記。現在重新安排學生我增加排名即最高分將是一個，第二個最高第二個等等......

對於每個學生，他或她的地方等於擁有更多分數的學生人數，增加1。

讓我們將hash of participant定義爲他/她的位置和點數的乘積。每次查詢後，發現參與者

例如哈希，sum：

N=4 Q=4 
3 100 
2 60 
1 80 
2 20 
1 20 

After the first query, participant 3 has 100 and is 1, with hash equal to 
100. The sum of hashes is 100+0+0+0=100 


After the second query, participant 2 has the second place with 60 and hash 
120, in total 100+120+0+0 = 220 


After the third query, the Rank looks like follows: 
(100,80,60,0). The sum of hashes is 200+160+180+0= 440 

In the fourth query participant the rank is (100,80,80,0) then, with the sum 
100⋅1+80⋅2+80⋅2+0⋅4=420. 

我們怎樣纔能有效的一個簡單的計算策略做的是在這裏找到索引並替換：

while(Q>0){ 
    Q--; 
    int a = in.nextInt()-1; 
    long b = in.nextInt(); 
    if(score.size()==0){ 
     score.add(b); 
     A[a]=b; 
     System.out.println(b); 
    }else{ 
     int index =-1; 
     if(A[a]!=0){ 


      int s =0; 
      int e = score.size()-1; 
      while(s<=e){ 

       int mid = (s+e)/2; 
       if(score.get(mid)==A[a]){ 
        index = mid; 
        break; 
       }else if(score.get(mid)>A[a]) s = mid+1; 
       else e = mid-1; 
      } 
     } 
     A[a]+=b; 
     int replace= score.size(); 
     int s =0; 
     int e = score.size()-1; 
     while(s<=e){ 

      int mid = (s+e)/2; 
      if(score.get(mid)>A[a]) s = mid+1; 
      else{ 
       replace = mid; 
       e = mid-1; 
      } 
     } 

     score.add(replace,A[a]); 
     if(index!=-1) score.remove(index+1); 


     long o= score.get(0); 
     long prev =1; 
     for(int i=1;i<score.size();i++){ 

      if(score.get(i)!=score.get(i-1)){ 

        prev =i+1; 
        o+=score.get(i)*prev; 
      }else o+=score.get(i)*(prev); 

     } 
     System.out.println(o); 



    } 
} 

如何我們可以通過使用分段樹或任何其他數據結構來更有效地實現它。

Answer 1

解決方案的一個緩慢部分是在每次查詢（O（N * Q））之後重新計算散列值。

爲了使速度更快，您需要儘可能重複使用以前的結果。所以讓我們看一下查詢後哈希總和會發生什麼。

比方說，你選擇位置x的學生，並將他移動到有序列表中，將其移動到位置y（通過提高分數）。對於哈希總和：

• 直至y-1的部分總和保持不變（這裏沒有變化）。
• x + 1之後的部分和保持不變（這裏沒有變化）。
• 您需要減少x old_score並添加y new_score來解釋學生移動。
• 對於y和x-1之間的學生，它們變成y +1 ... x。所以哈希總和需要增加他們的分數之和。

所有這些操作最多可以用O（logN）來完成，以將總體複雜度降低到O（QlogN）（好得多）。

所以你需要一個數據結構，允許你插入，刪除和計算O（logN）或更好的部分總和。我會建議一個平衡的二叉樹（或一個跳過列表）。每個節點應該跟蹤下面有多少個節點以及它們的總分是多少。要查找第x個元素，可以使用節點數量並找出可以使用部分和的總和。

使用此樹，您不需要更改節點的索引（當您在它們前面插入某些內容時，它們會自動更改）。如果你想用分段樹來做，你會需要很多的關注，因爲移動節點。

實施例：

說分數的當前狀態的樣子[100, 90, 80, 70, 60, 50, 40, 30]。下一個查詢是5 35，所以我們找到第五個元素（得分60的元素，你可以使用節點下面的元素數來指導你的搜索），並增加35。增加後得分爲95，因此進入第二位（通過查找二進制搜索樹中的值來找到該值）。所以x是5，y是2.Hashsum更新是hashsum += 95 * 2 - 60 * 5 + (90+80+70)。你可以在二叉樹中找到最後一筆總和，用上面提到的部分和。