题解 P1972 【[SDOI2009]HH的项链】

· · 题解

[SDOI2009]HH的项链

Description

　　HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

Solution

namespace List{
    struct Node{
        int v,nxt;
    }e[N];
    int head[M],tail[M],pos[M],cnt;
    void AddEdge(int color,int posit){
        if(!head[color]){head[color]=++cnt;e[cnt]=(Node){posit,0};tail[color]=head[color]=cnt;;}
        else e[tail[color]].nxt=++cnt,e[cnt]=(Node){posit,0},tail[color]=cnt;
    }
    int Next(int col,int l){int i;for(i=pos[col]?pos[col]:head[col];e[i].v<l&&i;i=e[i].nxt);pos[col]=i;if(e[i].v)return e[i].v;else return n+1;}
};using namespace List;

　　然后将查询按左端点从小到大排序.

struct Query{
    int l,r,id;
    bool operator<(const Query& b)const{return l<b.l;}
}q[M];

　　在每个查询中, 找出从左端点l开始的每一种颜色的坐标, 记颜色i的第一个大于l的坐标为p_i, 那么表示p_i处开始出现了一种颜色, 那么l-r出现的颜色总数就为答案, 可以用树状数组来维护.

namespace BIT{
    int t[N];
    int lowbit(int i){return i&(-i);}
    void Add(int p,int c){int i=p;while(i<=n)t[i]+=c,i+=lowbit(i);}
    int query(int r){int i=r,ans=0;while(i)ans+=t[i],i-=lowbit(i);return ans;}
    int QUEry(int l,int r){return query(r)-query(l-1);}
};using namespace BIT;

　　还有一个问题是如何快速从一个查询过度到另一个查询? 因为从l过度到l', 必定有一些颜色处于[l,l')之中, 而树状数组是统计不了它们的答案的.

  1. 可以枚举每一种颜色是否需要更新第一次在[l,n]出现的坐标, 复杂度O(km)(k为颜色数量).结果:T成沙茶.
  2. 直接枚举[l,l')之内的颜色是否需要更新, 均摊复杂度O(n).结果:通过

Code

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define M 200005
#define N 500005
#define P 1000005
#define inf 0x3f3f3f3f
using namespace std;

int read(){
    char ch=getchar();int s=0;
    for(;!isdigit(ch);ch=getchar());
    for(s=0;isdigit(ch);s=s*10+ch-'0',ch=getchar());
    return s;
}

int col[N],s[N];
int Answer[M];
int n,m,tot;
/*******************************************************************/
struct Query{
    int l,r,id;
    bool operator<(const Query& b)const{return l<b.l;}
}q[M];
/*******************************************************************/
namespace Map{
    int rank[N];
    int vis[P];
    void init(){
        for(int i=1;i<=n;++i)if(!vis[col[i]])s[++tot]=col[i],vis[col[i]]=true;
        sort(s+1,s+tot+1);
        for(int i=1;i<=tot;++i)rank[s[i]]=i;
        for(int i=1;i<=n;++i)s[i]=rank[col[i]];
    }
};
/*******************************************************************/
namespace List{
    struct Node{
        int v,nxt;
    }e[N];
    int head[M],tail[M],pos[M],cnt;
    void AddEdge(int color,int posit){
        if(!head[color]){head[color]=++cnt;e[cnt]=(Node){posit,0};tail[color]=head[color]=cnt;}
        else e[tail[color]].nxt=++cnt,e[cnt]=(Node){posit,0},tail[color]=cnt;
    }
    int Next(int col,int l){int i;for(i=pos[col]?pos[col]:head[col];e[i].v<l&&i;i=e[i].nxt);pos[col]=i;if(e[i].v)return e[i].v;else return n+1;}
};using namespace List;
/*******************************************************************/
namespace BIT{
    int t[N];
    int lowbit(int i){return i&(-i);}
    void Add(int p,int c){int i=p;while(i<=n)t[i]+=c,i+=lowbit(i);}
    int query(int r){int i=r,ans=0;while(i)ans+=t[i],i-=lowbit(i);return ans;}
    int QUEry(int l,int r){return query(r)-query(l-1);}
};using namespace BIT;
/*******************************************************************/
int visit[N];
int main(){
    scanf("%d",&n);int u,v,c;
    for(int i=1;i<=n;++i)
        col[i]=read();
    Map::init();
    for(int i=1;i<=n;++i)List::AddEdge(s[i],i);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)q[i].l=read(),q[i].r=read();
    for(int i=1;i<=m;++i)q[i].id=i;
    sort(q+1,q+m+1);int po=0;
    for(int i=1;i<=tot;++i)Add(Next(i,1),1);
    for(int i=1;i<=m;++i){
        if(q[i].l>q[i-1].l){
            for(int j=q[i-1].l;j<q[i].l;++j)
                if(visit[s[j]]!=i){
                    Add(Next(s[j],q[i].l),1),visit[s[j]]=i;
                }
        }
        Answer[q[i].id]=QUEry(q[i].l,q[i].r);
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",Answer[i]);
    return 0;
}