MO的算法來尋找兩陣列

Question

中存在的元素的數目我有陣列，before[N+1]（索引）和after[]（的before[]子陣列）。現在爲M查詢，我需要找到after[]before[]中存在多少個元素，給定範圍l,r。

例如：
N = 5
之前：（2,1，3，4，5）
之後：（1，3，4，5）
M = 2
L = 1 ，R = 5 →在[1]之前和之前[5]之間存在[]之後的4個元素（1,3,4,5）L = 2，R = 4 → 3個元素（1,3,5） 4）after []之前[2]之前[4]

我想用MO的算法找到這個。以下是我的代碼：

using namespace std; 

int N, Q; 

// Variables, that hold current "state" of computation 
long long current_answer; 
long long cnt[100500]; 

// Array to store answers (because the order we achieve them is messed up) 
long long answers[100500]; 
int BLOCK_SIZE; 


// We will represent each query as three numbers: L, R, idx. Idx is 
// the position (in original order) of this query. 
pair< pair<int, int>, int> queries[100500]; 


// Essential part of Mo's algorithm: comparator, which we will 
// use with std::sort. It is a function, which must return True 
// if query x must come earlier than query y, and False otherwise. 
inline bool mo_cmp(const pair< pair<int, int>, int> &x, 
     const pair< pair<int, int>, int> &y) 
{ 
    int block_x = x.first.first/BLOCK_SIZE; 
    int block_y = y.first.first/BLOCK_SIZE; 
    if(block_x != block_y) 
     return block_x < block_y; 
    return x.first.second < y.first.second; 
} 

// When adding a number, we first nullify it's effect on current 
// answer, then update cnt array, then account for it's effect again. 
inline void add(int x) 
{ 
    current_answer -= cnt[x] * cnt[x] * x; 
    cnt[x]++; 
    current_answer += cnt[x] * cnt[x] * x; 
} 

// Removing is much like adding. 
inline void remove(int x) 
{ 
    current_answer -= cnt[x] * cnt[x] * x; 
    cnt[x]--; 
    current_answer += cnt[x] * cnt[x] * x; 
} 

int main() 
{ 
    cin.sync_with_stdio(false); 
    cin >> N >> Q; // Q- number of queries 
    BLOCK_SIZE = static_cast<int>(sqrt(N)); 


    long long int before[N+1]; // 1 indexed 
    long long int after[]  // subarray 

    // Read input queries, which are 0-indexed. Store each query's 
    // original position. We will use it when printing answer. 
    for(long long int i = 0; i < Q; i++) { 
     cin >> queries[i].first.first >> queries[i].first.second; 
     queries[i].second = i; 
    } 

    // Sort queries using Mo's special comparator we defined. 
    sort(queries, queries + Q, mo_cmp); 

    // Set up current segment [mo_left, mo_right]. 
    int mo_left = 0, mo_right = -1; 

    for(long long int i = 0; i < Q; i++) { 
     // [left, right] is what query we must answer now. 
     int left = queries[i].first.first; 
     int right = queries[i].first.second; 

     // Usual part of applying Mo's algorithm: moving mo_left 
     // and mo_right. 
     while(mo_right < right) { 
      mo_right++; 
      add(after[mo_right]); 
     } 
     while(mo_right > right) { 
      remove(after[mo_right]); 
      mo_right--; 
     } 

     while(mo_left < left) { 
      remove(after[mo_left]); 
      mo_left++; 
     } 
     while(mo_left > left) { 
      mo_left--; 
      add(after[mo_left]); 
     } 

     // Store the answer into required position. 
     answers[queries[i].second] = current_answer; 
    } 

    // We output answers *after* we process all queries. 
    for(long long int i = 0; i < Q; i++) 
     cout << answers[i] << "\n"; 

現在的問題是我無法弄清楚如何定義add function和remove function。

有人可以幫我解決這些功能嗎？

Answer 1

注：我將表示給定的陣列爲a和b。

1. 讓我們來學習如何添加一個新的位置（向右移動）。如果a[r]已經存在，則可以忽略它。否則，我們需要添加a[r]並將b[r]的出現次數添加到a到目前爲止的答案。最後，如果b[r]已經在a，我們需要添加一個答案。請注意，我們需要兩個數組來執行該操作：一個用於第一個數組，另一個用於第二個數組。

2. 我們知道如何在O(1)中添加一個位置，所以我們快到了。我們如何處理刪除？

3. 讓我們假設我們想要刪除一個子段。我們可以輕鬆修改計數數組。但是，我們如何恢復答案？那麼，我們沒有。您的解決方案是這樣的：

   • 保存當前的答案
   • 添加子片段
   • 答案查詢
   • 刪除它（我們需要關心的計數陣列和忽略的答案）
   • 恢復已保存的答案

就是這樣。當我們將左指針移動到下一個塊時，需要重建結構，但在最壞的情況下它仍然需要O(N sqrt(N))時間。

注意：當我們刪除一個位置時，可能直接使用count數組重新計算答案，但我上面顯示的方式看起來更容易。