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 ;
}