AC日记——[SDOI2009]HH的项链 洛谷 P1972

[SDOI2009]HH的项链

思路；

　　莫队；

代码：

#include <bits/stdc++.h>

#define maxn 100005

#define maxm 400005

#define maxnnum 2000005

using namespace std;

int bel[maxn];

struct QueryType {

    int l,r,id;

    bool operator <(const QueryType pos)const

    {

        if(bel[l]==bel[pos.l]) return r<pos.r;

        else return bel[l]<bel[pos.l];

    }

};

struct QueryType qu[maxm];

int n,m,ai[maxn],ans[maxn],blo,now,num[maxnnum];

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void updata(int x,bool di)

{

    x=ai[x];

    if(di)

    {

        if(!num[x]) now++;

        num[x]++;

    }

    else

    {

        if(num[x]==) now--;

        num[x]--;

    }

}

int main()

{

    in(n),blo=sqrt(n);

    for(int i=;i<=n;i++) in(ai[i]),bel[i]=(i+)/blo;

    in(m);

    for(int i=;i<=m;i++) in(qu[i].l),in(qu[i].r),qu[i].id=i;

    sort(qu+,qu+m+);

    int l=,r=;

    for(int no=;no<=m;no++)

    {

        while(r<qu[no].r) updata(++r,true);

        while(r>qu[no].r) updata(r--,false);

        while(l<qu[no].l) updata(l++,false);

        while(l>qu[no].l) updata(--l,true);

        ans[qu[no].id]=now;

    }

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

    return ;

}