[SPOJ DQUERY][BIT][Persistent Segment Tree] D-query

原題連結
這題如果沒有想到一個關鍵點的話就會很難做
這邊提供在線和離線的作法，兩種作法本質相去不遠。

假設有一序列長這樣：
2 5 3 2 6 3 3 5 1 7

我們考慮R=10的詢問。假設我們站在第10個數字往回看，不妨將序列看成這樣：
0 0 0 1 1 0 1 1 1 1

我們將第一次遇見某數字的地方設成1，其他地方為0。
這樣有什麼好處呢？其實只要得到這個序列，任何以R為結尾的詢問[L,R]都是後綴[L,R]的和，例如L= 5,R=10，答案就是5。這可以用任何一個區間求和資料結構完成。
如果對這個作法沒有什麼直觀的感受，建議反覆閱讀理解一下。

我們就有了一個離線作法：將所有詢問讀入，以R從小到大排序，這樣我們就可以一次回答所有以某個R為右界的詢問了。

時間複雜度:O(NlgN+QlgQ) , QlgQ的由來是sort。

那麼要如何在線呢？我們想要隨時查詢「以序列開頭為左界，以某個R為右界」的線段樹(或BIT)，因此我們想要保留以1~n為結尾的線段樹。這不就是持久化最簡單的應用嗎？
所以，對原序列做出持久化線段樹，對於每個詢問[L,R]，從root[R]下去獲得L~R的區間和就好了。
有一些細節要注意的，說出來就無趣了，可以直接參考code。(Hint:跟new 有關)

時間複雜度:O(NlgN + QlgN)

在線版本code:

#include<cstdio>
#include<new>
using namespace std;
const int maxn=30000+5;
const int maxc=1000000+5;
struct Node
{
    Node *lc,*rc;
    int Sum;
    void pull() {Sum=(lc?lc->Sum:0)+(rc?rc->Sum:0);}
    Node() {Sum=0;lc=rc=NULL;}
}*root[maxn];
void modify(Node* last,Node*& now,int L,int R,int mx,int mv,int first)
{
    if(first || !now)
    {
        if(!last) now=new Node();
        else now=new Node(*last);
    }
    if(L==R) {now->Sum+=mv;return;}
    int M=L+(R-L)/2;
    if(mx<=M) modify(last?last->lc:0,now->lc,L,M,mx,mv,first);
    else modify(last?last->rc:0,now->rc,M+1,R,mx,mv,first);
    now->pull();
}
int query(Node* now,int L,int R,int ql,int qr)
{
    if(!now) return 0;
    int M=L+(R-L)/2,ret=0;
    if(ql<=L && R<=qr) return now->Sum;
    if(ql<=M) ret+= query(now->lc,L,M,ql,qr);
    if(qr >M) ret+= query(now->rc,M+1,R,ql,qr);
    return ret;
}
int last[maxc];
int main()
{
    int n,Q;
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++)
    {
        int first=1;
        scanf("%d",&x);
        if(last[x]) {modify(root[i-1],root[i],1,maxn,last[x],-1,first);first=0;}
        modify(root[i-1],root[i],1,maxn,i,1,first);
        last[x]=i;
    }
    scanf("%d",&Q);
    while(Q--)
    {
        int L,R;
        scanf("%d%d",&L,&R);
        printf("%d\n",query(root[R],1,maxn,L,R));
    }
}

離線版本code:

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=30000+5;
const int maxQ=200000+5;
const int maxc=1000000+5;
int n,Q,a[maxn],last[maxc];
struct Query
{
    int id,L,R;
    bool operator < (const Query& rhs) const {return R<rhs.R || (R==rhs.R && L<rhs.L);}
}qu[maxQ];
int c[maxn];
inline int lowbit(int x) {return x&(-x);}
void add(int p,int x)
{
    while(p<=n)
    {
        c[p]+=x;
        p+=lowbit(p);
    }
}
int query(int p)
{
    int ret=0;
    while(p)
    {
        ret+=c[p];
        p-=lowbit(p);
    }
    return ret;
}
int ans[maxQ];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    scanf("%d",&Q);
    for(int i=0;i<Q;i++) {qu[i].id=i;scanf("%d%d",&qu[i].L,&qu[i].R);}
    sort(qu,qu+Q);
    
    memset(last,0,sizeof last);
    memset(c,0,sizeof c);
    int R=0;
    for(int i=0;i<Q;i++)
    {
        while(R+1<=qu[i].R)
        {
            if(last[a[R+1]]) add(last[a[R+1]],-1);
            add(R+1,1);
            last[a[R+1]]=R+1;
            R++;
        }
        ans[qu[i].id]=query(qu[i].R)-query(qu[i].L-1);
    }
    for(int i=0;i<Q;i++) printf("%d\n",ans[i]);
}