AC日记——大爷的字符串题 洛谷 P3709

大爷的字符串题

思路：

　　莫队，需开O2，不开50；

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
int bel[maxn],blo;
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[maxn];
int num[maxn],cnt[maxn],ai[maxn],n,m;
int bi[maxn],size,ans[maxn],now;
inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0') Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }        
}
inline void updata(int x,bool di)
{
    x=ai[x];
    if(di)
    {
        if(num[x]==now) now++;
        cnt[num[x]]--,num[x]++,cnt[num[x]]++;
    }
    else
    {
        if(num[x]==now&&cnt[num[x]]==1) now--;
        cnt[num[x]]--,num[x]--,cnt[num[x]]++;
    }
}
int main()
{
    in(n),in(m),blo=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        in(ai[i]);
        bi[i]=ai[i];
        bel[i]=(i+1)/blo;
    }
    sort(bi+1,bi+n+1);
    size=unique(bi+1,bi+n+1)-bi-1;
    for(int i=1;i<=n;i++)ai[i]=lower_bound(bi+1,bi+size+1,ai[i])-bi;
    for(int i=1;i<=m;i++)in(qu[i].l),in(qu[i].r),qu[i].id=i;
    sort(qu+1,qu+1+m);int l=1,r=0;
    for(int no=1;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,true);
        while(l<qu[no].l) updata(l++,false);
        ans[qu[no].id]=now;
    }
    for(int i=1;i<=m;i++) printf("%d
",-ans[i]);
    return 0;
}