关于莫队

回复帖子

@explpl2007 2021-04-08 19:14 回复

这是求区间有多少种数,我在一个月以前曾经搞过,遗留问题就是这个排序是怎么一回事。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=1e5+5;
const int B=sqrt(N);
int a[N],cnt[N],n,m,res,ans[N];
struct Q
{
    int l,r,id;
    bool operator<(const Q &t) const
    {
        if(l/B==t.l/B)
        {
            return r<t.r;
        }
        else
        {
            return l/B<t.l/B;
        }
    }
}q[N];
inline void update(int x,int f)
{
    cnt[x]+=f;
    if(cnt[x]==0&&f==-1)
    {
        res--;
    }
    if(cnt[x]==1&&f==1)
    {
        res++;
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].l=read();
        q[i].r=read();
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(l<q[i].l)
        {
            update(a[l++],-1);
        }
        while(l>q[i].l)
        {
            update(a[--l],1);
        }
        while(r<q[i].r)
        {
            update(a[++r],1);
        }
        while(r>q[i].r)
        {
            update(a[r--],-1);
        }
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)
    {
        write(ans[i]);
        puts("");
    }
}

有dalao解释一下吗

@dead_X  2021-04-08 19:16 回复 举报

保证左端点移动次数和右端点移动次数都为 $O(n\sqrt m)$。

@xzggzh1 2021-04-08 19:26 回复 举报

@explpl2007 莫队的核心就在于这里的复杂度分析,要是这都不知道的话就重新学一遍吧,,,

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。