SPOJ DQUERY:TLE即使有BIT？

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在BIT中的位置添加一个元素.否则,添加-1到此元素上一次出现的位置,然后添加1到该i位置.

4. 这个问题的答案查询(left, right)是从所有元素只是总和left来right.

要保持每个元素的最后一次出现,可以使用地图.

可以使用持久性分段树在线进行(时间复杂度相同,复杂度也相同O(n * log n + q)),但这里不需要.