BZOJ 3809: Gty的二逼妹子序列（莫队+分块）

题目

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。

对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。

为了方便，我们规定妹子们的美丽度全都在[1,n]中。

给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。

分析

要么写树套树，可是只有28M的空间，所以莫队吧。

莫队+树状数组很好想，但是这样就是O(n^1.5logn)。

有个很厉害的思路就是用分块把修改变成O(1),查询变成O(n^0.5)

这样最终时间复杂度就是O(n*1.5)

卡一卡就能过去

这里的优化思路可以这么分析：

用树状数组则修改O(n*n^0.5*logn),查询O(n*(n^0.5+logn)),所以想个办法再综合一下，分块刚刚好嘛

orzPoPoQQQ大爷的加速输入

顺便，由于分块没有初始化，然后TLE了3次，每次卡80S,卡住了不少人，对不起大家QAQ。

代码

注意：

1、分块的初始化操作即使不做也不会错，但是会T很惨

2、莫队注意修改的时候++i和i++不同情况不一样。

#include<cmath>
#include<queue>
#include<cctype>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=e5+,maxm=e6+;
namespace IStream{  
    const int L=<<;  
    char buffer[L],*S,*T;  
    inline char Get_Char()  
    {  
        if(S==T)  
        {  
            T=(S=buffer)+fread(buffer,,L,stdin);  
            if(S==T) return EOF;  
        }  
        return *S++;  
    }  
    inline void Rd(int &re) 
    {  
        char c; 
        re=;
        for(c=Get_Char();(c<'0'||c>'9');c=Get_Char());  
        while(c>='0'&&c<='9')  
            re=(re<<)+(re<<)+(c-'0'),c=Get_Char();  
    } 
    int tt[],sz;
    inline void Pt(int x)
    {
        sz=;
        do{
            tt[++sz]=x%10;
            x/=;
        }while(x);
        for(int i=sz;i;i--)putchar(tt[i]^);
        putchar('\n');
    }
}
int n,m;
int co[maxn],belong[maxn];
struct block{
    static const int TIM=;
    int num,vis[maxn],d[maxn/TIM+],L[maxn/TIM+],R[maxn/TIM+];
    void Build()
    {
        L[]=R[]=;
        for(num=;num*TIM<n;num++)
        {
            L[num]=R[num-]+,R[num]=L[num]+TIM-;
            for(int i=L[num];i<=R[num];i++)belong[i]=num;
        }
        L[num]=R[num-]+,R[num]=n;
        for(int i=L[num];i<=R[num];i++)belong[i]=num;
    } 
    void add(int v)
    {
        if(!vis[v])d[belong[v]]++;
        vis[v]++;
    }
    void del(int v)
    {
        if(vis[v]==)d[belong[v]]--;
        vis[v]--;
    }
    int query(int l,int r)
    {
        int ret=;
        if(belong[l]==belong[r])
        {
            for(int i=l;i<=r;i++)if(vis[i])ret++;
            return ret;
        }
        for(int i=l;i<=R[belong[l]];i++)if(vis[i])ret++;
        for(int i=belong[l]+;R[i]<r;i++)ret+=d[i];
        for(int i=L[belong[r]];i<=r;i++)if(vis[i])ret++;
        return ret;
    }
}blo;
namespace modui
{
    int ans[maxm];
    struct data{
        int l,r,a,b,id;
        friend bool operator<(data a,data b)
        {
            return belong[a.l]!=belong[b.l]?belong[a.l]<belong[b.l]:a.r<b.r;
        }
    }q[maxm];
    void Init()
    {
        IStream::Rd(n);IStream::Rd(m);
        blo.Build();
        for(int i=;i<=n;i++)IStream::Rd(co[i]);
        for(int i=;i<=m;i++)
        {
            q[i].id=i;
            IStream::Rd(q[i].l);
            IStream::Rd(q[i].r);
            IStream::Rd(q[i].a);
            IStream::Rd(q[i].b);
        }
        sort(q+,q+m+);
    }   
    void modui()
    {
        int L=,R=;
        for(int i=;i<=m;i++)
        {
            while(L<q[i].l)blo.del(co[L++]);
            while(L>q[i].l)blo.add(co[--L]);
            while(R<q[i].r)blo.add(co[++R]);
            while(R>q[i].r)blo.del(co[R--]);
            ans[q[i].id]=blo.query(q[i].a,q[i].b);
        }
    }
    void work()
    {
        Init();
        modui();
        for(int i=;i<=m;i++)
            IStream::Pt(ans[i]);
    }
}
int main()
{
    modui::work();
    return ;
}