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

· · 题解

看了大家的题解，有莫队，主席树，树状数组.....

但似乎没有人写在线的分块（可能太慢？）

下面是我的分块：

首先我们用\ a\ [\ i\ ]\ 表示 \ i\ 这个位置的贝壳种类。

我们定义一个数组\ pre[\ i\ ]\ 表示：从\ i\ 这个位置往前找，第一个种类为\ a\ [\ i\ ]\ 的位置。

例如： \ a\ [\ i\ ]\ ：1 3 2 2 1 3 3 。

则： \ pre[\ i\ ]\ ：0 0 0 3 1 2 6 。

请务必理解清楚下面这句话：

我们要求一段区间 l 到 r 的不同种类的贝壳的数量，就是求解区间\ [\ l ，\ r\ ] 里有多少位置的\ pre[\ i\ ]\ 小于\ l\ 。因为区间内\ pre[\ i\ ]\ 大于 l 的位置都将在区间中出现两次以上; 换句话说，一个\ pre[\ i\ ]\ 小于 l 的位置，必然是该位置上的贝壳种类在\ [\ l , r\ ] 中第一次出现的位置，所以我们只需要统计\ pre[\ i\ ]\ 小于 l 的位置即可。

然后我们就可以分块了。

将整段序列分为 sqrt(n)块，每块大小为sqrt(n)。

将块内排序，维护排序后的数组(即代码中的preb[\ ]数组)，在查询的时候，对于整块，块内二分求复合条件的数的个数；对于非完整块，暴力找即可。这部分不理解的可以结合代码模拟一下。

排序的复杂度O(n*log(\ sqrt(n)\ )\ )。

每次查询O(sqrt(n)*log(\ sqrt(n)\ )+sqrt(n))

总复杂度O(\ m*sqrt(n)*log(\ sqrt(n)\ )\ )

看起来这复杂度想AC有点不稳啊。

不加优化TLE了后两个点，加了优读、快写、register、inline就过了。

评测记录：

代码：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

namespace Qza {

    const int nn=300;
    const int N=50005;
    const int NN=1000005;

    int n,m,a[N],p[NN],pre[N];
    int preb[N],l[nn],r[nn],sizb,numb,belong[N];
    int buf[15];

    inline void build()
    {
        sizb=sqrt(n);
        numb=n/sizb;
        if(n%sizb) ++numb;
        for(register int i=1;i<=numb;++i) {
            l[i]=(i-1)*sizb+1;
            r[i]=i*sizb;
        }
        r[numb]=n;
        for(register int i=1;i<=n;++i) {
            belong[i]=(i-1)/sizb+1;
            preb[i]=pre[i];
        }
        for(register int i=1;i<=numb;++i) {
            sort(preb+l[i],preb+r[i]+1);
        }
    }
    inline int queryb(int l,int r,int x)
    {
        register int L=l, R=r, mid;
        while(L<=R) {
            mid=(L+R)>>1;
            if(preb[mid]<x) L=mid+1;
            else R=mid-1;
        }
        return L-l;
    }
    inline int query(int nowl,int nowr)
    {
        register int ans=0;
        if(belong[nowl]==belong[nowr]) {
            for(int i=nowl;i<=nowr;++i) 
                if(pre[i]<nowl) ++ans;
            return ans;
        }
        for(register int i=nowl;i<=r[belong[nowl]];++i) {
            if(pre[i]<nowl) ++ans;
        }
        for(register int i=l[belong[nowr]];i<=nowr;++i) {
            if(pre[i]<nowl) ++ans;
        }
        for(register int i=belong[nowl]+1;i<=belong[nowr]-1;++i) {
            ans+=queryb(l[i],r[i],nowl);
        }
        return ans;
    }

    inline void read(int &x)
    {
        char ch=getchar(); x=0;
        while(ch<'0') ch=getchar();
        while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    }
    inline void writ(int x)
    {
        register int cnt=0;
        while(x) buf[++cnt]=(x%10)+48,x/=10;
        while(cnt) putchar(buf[cnt--]);
        putchar('\n');
    }

    void main()
    {
        register int x,y;
        read(n);
        for(register int i=1;i<=n;++i) {
            read(a[i]);
            pre[i]=p[a[i]];
            p[a[i]]=i;
        } 
        build();
        read(m);
        for(register int i=1;i<=m;++i) {
            read(x); read(y);
            writ(query(x,y));
        }
        return ;
    }
}

int main()
{
    Qza::main();
    return 0;
}

如果对代码有什么不懂的地方，可以私信我。

其实主席树更稳。

然而我非常的菜。