SPOJ DQUERY: TLE даже с битом?

Question

Вот проблема, которую я хочу решить, я использую The Fact That Prefix Sum[i] - Prefix Sum[i-1] Приводит к тому, что частота становится больше нуля, чтобы идентифицировать отдельные цифры, а затем я устраняю частоту, но даже с BIT я получаю TLE

Дана последовательность из n чисел a1, a2, ..., an и ряда d-запросов.

D-запрос - это пара (i, j) (1 ≤ i ≤ j ≤ n).

Для каждого d-запроса (i, j) вы должны вернуть количество различных элементов в подпоследовательности ai, ai+1, ..., aj.

Input

Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), 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
5 
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3

код:

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
typedef long long int ll;
using namespace std;
void update(ll n, ll val, vector<ll> &b);
ll read(ll n,vector<ll> &b);
ll readsingle(ll n,vector<ll> &b);
void map(vector<ll> &a,vector<ll> &b,ll n)  /**** RElative Mapping ***/
{
    ll temp;
    a.clear();
    b.clear();
    for(ll i=0; i<n; i++)
    {
        cin>>temp;
        a.push_back(temp);
        b.push_back(temp);
    }
    sort(b.begin(),b.end());
    for(ll i=0; i<n; i++)
        *(a.begin()+i) = (lower_bound(b.begin(),b.end(),a[i])-b.begin())+1;
    b.assign(n+1,0);
}
int main()
{
    ll n;
    cin>>n;
    vector<ll> a,b;
    map(a,b,n);
    ll t;
    cin>>t;
    while(t--)
    {
        ll l ,u;
        b.assign(n+1,0);
        cin>>l>>u;
        l--;/*** Reduce For Zero Based INdex ****/
        u--;
        for(ll i=l;i<=u;i++)
            update(a[i],1,b);
        ll cont=0;
        for(ll i=l;i<=u;i++)
            if(readsingle(a[i],b)>0)
        {
            cont++;
            update(a[i],-readsingle(a[i],b),b); /***Eliminate The Frequency */
        }
        cout<<cont<<endl;
    }
    return 0;
}
ll readsingle(ll n,vector<ll> &b)
{
    return read(n,b)-read(n-1,b);
}
ll read(ll n,vector<ll> &b)
{
    ll sum=0;
    for(; n; sum+=b[n],n-=n&-n);
    return sum;
}
void update(ll n, ll val, vector<ll> &b)
{
    for(; n<=b.size(); b[n]+=val,n+=n&-n);
}

Answer 1

Алгоритм, который вы используете, слишком медленный. Для каждого запроса вы выполняете итерацию по всему диапазону запросов, что уже дает n * q операции (очевидно, это слишком много). Вот лучшее решение (оно имеет O((n + q) * log n) время и O(n + q) Пространственная сложность (это автономное решение):

1. Давайте отсортируем все запросы по их правому концу (нет необходимости явно сортировать их, вы можете просто добавить запрос в соответствующую позицию (из 0 в n - 1)).

2. Теперь давайте переберем все позиции в массиве слева направо и сохраним BIT. Каждая позиция в BIT является либо 1(это означает, что в позиции есть новый элемент i) или же 0(изначально он заполнен нулями).

3. Для каждого элемента a[i]: если это первое вхождение этого элемента, просто добавьте его к i положение в БИТ. В противном случае добавьте -1 в положение предыдущего вхождения этого элемента, а затем добавить 1 к i позиция.

4. Ответ на запрос (left, right) это просто сумма для всех элементов из left в right,

Чтобы сохранить последнее вхождение каждого элемента, вы можете использовать карту.

Возможно сделать это онлайн, используя постоянное дерево сегментов (временная сложность была бы той же самой, такая же сложность стала бы O(n * log n + q)), но здесь это не требуется.