【Luogu】P1972HH的项链（链表+树状数组）

　　题目链接

　　难题，所以会讲得细一些。

　　首先我们想如何统计区间[l,r]内不同贝壳的个数。

　　第一个思路就是线段树/树状数组，query(1,r)-query(1,l-1)对不对？

　　然而这样是不对的。

　　然后我们举个例子：

　　例如有一段区间是[ 1 2 3 1 2 3 1 2 3 ]这样子，如果要统计不同贝壳的个数，那么一个贝壳就可以代表所有同色贝壳。

　　也就是说，假设要统计这个区间内1有没有出现，那这个区间变成这样子：[ 1 2 3 0 2 3 0 2 3 ] 或 [ 0 2 3 1 2 3 1 2 3 ] 或什么样子，都是一样的，只要1出现过一次，那就说明1出现过了。

　　所以可以把所有询问按左端点排序，左端点相同的按照右端点排序，然后挨个统计：

　　设next[ j ] 表示：x为j位置贝壳的颜色，next[j]表示的就是j后面第一个颜色为x的位置。如在我们举的例子中，next[1]=4，next[2]=5，next[5]=8。

　　然后我们在刚开始初始化的时候，只有所有颜色第一次出现的位置作为该颜色的代表贝壳，也就是说只有这几个位置有1个不同的贝壳。

　　然后在扫描询问数组的时候，把q[i-1].l到q[i].l之间的不同贝壳个数更新。具体方法是把next[当前位置]所指向的位置不同的贝壳变成1。

　　这样就可以树状数组查询了。

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<cstring>

#include<algorithm>

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

struct line{

    int l,r,id,ans;

    bool operator <(const line &a)const{

        if(l!=a.l)    return l<a.l;

        return r<a.r;

    }

}q[];

bool cmp(line a,line b){    return a.id<b.id;    }

int n;

int tree[];

inline void add(int pos){

    while(pos<=n){

        tree[pos]++;

        pos+=pos&(-pos);

    }

}

inline int query(int pos){

    int ans=;

    while(pos){

        ans+=tree[pos];

        pos-=pos&(-pos);

    }

    return ans;

}

int pre[];

int next[];

int vis[];

int que[];

int main(){

    n=read();

    for(int i=;i<=n;++i){

        que[i]=read();

        next[pre[que[i]]]=i;

        if(!pre[que[i]]){

            add(i);

            vis[i]=;

        }

        pre[que[i]]=i;

    }

    int m=read();

    for(int i=;i<=m;++i)    q[i]=(line){read(),read(),i};

    std::sort(q+,q+m+);

    q[].l=;

    for(int i=;i<=m;++i){

        if(q[i-].l!=q[i].l)

            for(int j=q[i-].l;j<q[i].l;++j)

                if(next[j]&&!vis[next[j]]){

                    vis[next[j]]=;

                    add(next[j]);

                }

        q[i].ans=query(q[i].r)-query(q[i].l-);

    }

    std::sort(q+,q+m+,cmp);

    for(int i=;i<=m;++i)    printf("%d\n",q[i].ans);

    return ;

}

巴特西

【Luogu】P1972HH的项链（链表+树状数组）

最新文章

热门文章