MO, чтобы найти число элементов, присутствующих в обоих массиве

Question

У меня массивы, before[N+1] (индексируется) и after[] (подмассива before[]). Теперь для M Запросов, мне нужно найти, сколько элементов after[] присутствует в before[] для данного диапазона l,r.

Например:
N = 5
Перед: (2, 1, 3, 4, 5)
После того, как: (1, 3, 4, 5)
М = ​​2
L = 1 , R = 5 → 4 элемента (1, 3, 4, 5) после [] присутствуют между до [1] и до [5]
L = 2, R = 4 → 3 элемента (1, 3, 4) of 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. Предположим, что мы хотим удалить подсегмент. Мы можем легко модифицировать массивы count. Но как мы можем восстановить ответ? Ну, мы этого не делаем. Ваше решение выглядит следующим образом:

   • сохранить текущий ответ
   • добавить подсегменте
   • ответа на запрос
   • удалить его (мы заботимся о количества массивов и игнорировать ответ)
   • восстановить сохраненный ответ

Вот так. Это потребовало бы перестройки структуры, когда мы переместим левый указатель на следующий блок, но в худшем случае все еще требуется O(N sqrt(N)).

Примечание: возможно было бы перекомпоновать ответ напрямую, используя массивы count, когда мы удаляем одну позицию, но способ, который я показал выше, мне тоже легче.