[SPOJ DQUERY]DQUERY - D-query

這題目不好找，附上題目連結

說明：
$S_{i}$為序列中第$i$個元素

和這題一樣，我們可以考慮對每個$i$儲存上一個$S_{i}$出現的位置，叫它$PRE[i]$好了
如果$S_{i}$是第一個出現，$PRE[i]=0$

你可以用任何方法將$PRE[i]$ $O(N\log N)$預處理出來
我偷懶用了$map$

那麼，要怎麼利用$PRE[i]$來求出區間$[l,r]$ (題中的$[i,j]$) 的答案呢？

我們可以用區間長度減掉重複的次數
重複的次數怎麼算呢？
就是$PRE[l\sim r]$中有幾個$\geq l$啦 (因為上一個$S_{i}$也在區間裡面，所以$S_{i}$不是區間中第一次出現)
可以發現，$PRE[1\sim l-1]$一定都$<l$，因此答案也等於$PRE[1\sim r]$中有幾個$\geq l$

可以用線段樹實現$O(\log N)$單點修改、區間求和
然後對於每個$r$，維護$PRE[1\sim r]$中有幾個位於任意區間內
有兩個方向
1. 離線操作
2. 持久化

我的code使用了持久化

時間複雜度：$O(N\log N+Q\log N)$

code:

#include<cstdio>
#include<cassert>
#include<map>
using namespace std;
struct Node
{
    Node *ch[2];
    int sum;
    Node(const int _sum):ch{NULL,NULL},sum(_sum){}
};
Node *Build(const int l,const int r)
{
    Node *ans=new Node(0);
    if(l<r)
    {
        const int mid=(l+r)/2;
        ans->ch[0]=Build(l,mid),ans->ch[1]=Build(mid+1,r);
    }
    return ans;
}
Node *Modify(Node *o,const int l,const int r,const int loc,const int val)
{
    Node *ans=new Node((o->sum)+val);
    if(l<r)
    {
        const int mid=(l+r)/2;
        if(loc<=mid)ans->ch[0]=Modify(o->ch[0],l,mid,loc,val),ans->ch[1]=o->ch[1];
        else ans->ch[0]=o->ch[0],ans->ch[1]=Modify(o->ch[1],mid+1,r,loc,val);
    }
    return ans;
}
int Query(Node *o,const int l,const int r,const int loc)
{
    if(l>=loc)return o->sum;
    if(r<loc)return 0;
    const int mid=(l+r)/2;
    return Query(o->ch[0],l,mid,loc)+Query(o->ch[1],mid+1,r,loc);
}
int N,S[30001],PRE[30001];
Node *TREE[30001];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%d",&S[i]);
    map<int,int>pre;
    for(int i=1;i<=N;i++)
    {
        PRE[i]=pre[S[i]];
        pre[S[i]]=i;
    }
    TREE[0]=Build(0,N);
    for(int i=1;i<=N;i++)
    {
        TREE[i]=TREE[i-1];
        TREE[i]=Modify(TREE[i],0,N,PRE[i],1);
    }
    int querycount;scanf("%d",&querycount);
    for(int i,j;querycount--;)
    {
        scanf("%d%d",&i,&j);
        printf("%d\n",(j-i+1)-Query(TREE[j],0,N,i));
    }
    return 0;
}