Удалить повторяющиеся элементы и дать сумму дальности
У меня есть вопрос относительно уже заданного этого вопроса:
SPOJ DQUERY: TLE даже с битом?
Что если я не хотел бы учитывать повторяющийся элемент при подсчете диапазона?
Ниже приведен пример:
Input
Line 1: n (1 ≤ n ≤ 10^6).
Line 2: n numbers a1, a2, ..., an (-10^9 ≤ ai ≤ ).
Line 3: q (1 ≤ q ≤ 10^6), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j
representing a d-query (1 ≤ i ≤ j ≤ n).
Output
For each d-query (i, j), print the number of distinct elements in the
subsequence ai, ai+1, ..., aj in a single line.
Example
Input
9
1 2 3 2 4 1 2 3 4
3
1 9
2 4
5 9
2 7
Output
0 //Explanation: all elements have been repeated.
1 //Explanation: only 3 has not repeated.
3 //Explanation: only 4 is repeated, so count only 1, 2 and 3.
3 //Explanation: only 2 is repeated, so count only 3, 4 and 1.
какие могут быть необходимые изменения, которые должны были быть сделаны в ответе @kraskevich (что является эффективным решением для этого конкретного случая)? Я пытался add 0 в БИТ, а не -1 в вышеупомянутом решении, которое не помогает для всех типов запросов. Кто-нибудь может дать мне идею?
Решение
Я наконец сделал это с помощью алгоритма МО. Следующее будет работать как положено.
/** For the given set of queries find the Unique element
* count of an array using MO's Algorithum. */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <unordered_map>
using namespace std;
struct Query // struct for storing the queries
{
int Left;
int Right;
int Index;
};
inline void Add(const int i, int &ans, vector<int> &Arr, vector<int> &countArray)
{
++countArray[Arr[i]];
if(countArray[Arr[i]] == 1)
ans += countArray[Arr[i]];
if(countArray[Arr[i]] == 2)
ans -= countArray[Arr[i]];
}inline void Remove(const int i, int &ans, vector<int> &Arr, vector<int> &countArray)
{
--countArray[Arr[i]];
if(countArray[Arr[i]] == 1)
ans += countArray[Arr[i]];
if(countArray[Arr[i]] == 0)
ans -= countArray[Arr[i]];
}
int main()
{
int _size; cin >> _size;
vector<int> Arr; Arr.reserve(_size);
copy_n(istream_iterator<int>(cin), _size, back_inserter(Arr));
//copy(Arr.cbegin(), Arr.cend(), ostream_iterator<int>(cout, "\t"));
int id = -1;
int sqrt_n = sqrt(_size);
int Q; cin >> Q;
vector<Query> qArr(Q);
unordered_map<int, int> Map;
for (int i = 0; i < _size; ++i)
{
if (Map.count(Arr[i]) == 0)
Map[Arr[i]] = ++id;
Arr[i] = Map[Arr[i]];
}
// read queries
for (int i = 0; i < Q; ++i)
{
int L,R;
cin >> L >> R;
qArr[i].Left = L-1;
qArr[i].Right = R-1;
qArr[i].Index = i;
}
// sort the queries according to(MO's Algorithum)
sort(qArr.begin(),qArr.end(),
[&](const Query &lhs, const Query &rhs)->bool
{
return ( (lhs.Left/sqrt_n == rhs.Left/sqrt_n) ?
lhs.Right < rhs.Right: // Qs with same Left case
(lhs.Left / sqrt_n) < (rhs.Left / sqrt_n) ); // Qs with diff values case
});
int currStart = 0;
int currEnd = 0;
int tempAnswer= 0;
vector<int> Answer(Q);
vector<int> countArray(_size);
for (int i = 0; i < Q; ++i)
{
int L = qArr[i].Left;
int R = qArr[i].Right;
/** Remove extra elements of previous range. For
* example if previous range is [0, 3] and current
* range is [2, 5], then a[0] and a[1] are subtracted */
while (currStart < L)
{
Remove(currStart, tempAnswer, Arr, countArray);
++currStart;
}
/** Add Elements of current Range */
while (currStart > L)
{
Add(currStart - 1, tempAnswer, Arr, countArray);
--currStart;
}
while (currEnd <= R)
{
Add(currEnd, tempAnswer, Arr, countArray);
++currEnd;
}
/** Remove elements of previous range. For example
* when previous range is [0, 10] and current range
* is [3, 8], then a[9] and a[10] are subtracted */
while (currEnd > R + 1)
{
Remove(currEnd - 1, tempAnswer, Arr, countArray);
--currEnd;
}
Answer[qArr[i].Index] = tempAnswer;
}
for(const auto &it: Answer) cout<<it<<endl;
return 0;
}
Другие решения
Других решений пока нет …