去掉重复元素，给出Range Sum

Question

我有一个关于已经问过的问题： SPOJ DQUERY : TLE Even With BIT?

如果我不想在进行范围查询时将重复元素计入计数怎么办？下面是一个例子：

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 的回答中应该做哪些必要的更改（这是针对特定情况的有效解决方案）？我尝试在 BIT 中使用 add 0，而不是在上述解决方案中使用 -1，这对所有类型的查询都没有帮助。谁能给我个主意？

Answer 1

终于用MOs算法搞定了。以下将按预期工作。

/** 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;
}

去掉重复元素，给出Range Sum

Remove repeated elements and give a Range Sum

c++

c++11

segment-tree

fenwick-tree