美文网首页
莫队算法

莫队算法

作者: fo0Old | 来源:发表于2017-06-21 00:02 被阅读0次
namespace mo
{
    int n,q,blo;
    ll a[__],ans[__],res;
    struct query{int l,r,id;}qj[__];

    void sfd(){fup(i,1,n)scanf("%lld",a+i);}
    void sfq(){fup(i,1,q)scanf("%d%d",&qj[i].l,&qj[i].r),qj[i].id=i;}
    void pf(){fup(i,1,q)printf("%lld\n",ans[i]);}
    void add(int x)
    {
    }
    void cut(int x)
    {
    }
    bool cmp(const query& x,const query& y)
    {
        if(x.l/blo==y.l/blo)return x.r<y.r;
        return x.l<y.l;
    }
    void solve()
    {
        blo=sqrt(n+0.1);
        sort(qj+1,qj+q+1,cmp);
        int l=1,r=0;res=0;
        fup(i,1,q)
        {
            while(r<qj[i].r)++r,add(r);
            while(l>qj[i].l)--l,add(l);
            while(r>qj[i].r)cut(r),--r;
            while(l<qj[i].l)cut(l),++l;
            ans[qj[i].id]=res;
        }
    }
};

带修改莫队

const int __=10005;
int a[__],b[__],n,qdx=0,mdx=0,bsz;
int ans[__],times[1000005];

struct query
{
    int l,r,md,id;
    void set(int _l,int _r,int _md,int _id)
    {
        l=_l,r=_r,md=_md,id=_id;
    }
    bool operator<(const query &b)const
    {
        if(l/bsz!=b.l/bsz)return l<b.l;
        if(r/bsz!=b.r/bsz)return r<b.r;
        return id<b.id;
    }
}que[__];

struct modfiy
{
    int wz,x,y;
    void set(int _wz,int _x,int _y)
    {
        wz=_wz,x=_x,y=_y;
    }
}mod[__];

int res=0;

void add(int x)
{
    if(!times[x])++res;
    ++times[x];
}

void cut(int x)
{
    if(times[x]==1)--res;
    --times[x];
}

void upd(int l,int r,int t)
{
    if(l<=mod[t].wz && mod[t].wz<=r)
        cut(mod[t].x),add(mod[t].y);
    a[mod[t].wz]=mod[t].y;
}

void del(int l,int r,int t)
{
    if(l<=mod[t].wz && mod[t].wz<=r)
        add(mod[t].x),cut(mod[t].y);
    a[mod[t].wz]=mod[t].x;
}

void work()
{
    bsz=(int)pow(n,2.0/3);
    sort(que+1,que+1+qdx);
    int l=1,r=0,t=0;
    fup(i,1,qdx)
    {
        while(t<que[i].md)++t,upd(l,r,t);
        while(t>que[i].md)del(l,r,t),--t;
        while(l<que[i].l)cut(a[l]),++l;
        while(l>que[i].l)--l,add(a[l]);
        while(r<que[i].r)++r,add(a[r]);
        while(r>que[i].r)cut(a[r]),--r;
        ans[que[i].id]=res;
    }
}

int main()
{
    int q;sf("%d%d",&n,&q);
    fup(i,1,n)sf("%d",&a[i]),b[i]=a[i];
    fup(i,1,q)
    {
        char op[2];int l,r;
        sf("%s%d%d",op,&l,&r);
        if(op[0]=='Q')
            ++qdx,que[qdx].set(l,r,mdx,qdx);
        if(op[0]=='R')
            mod[++mdx].set(l,0,r);
    }
    fup(i,1,mdx)
    {
        mod[i].x=b[mod[i].wz];
        b[mod[i].wz]=mod[i].y;
    }
    work();
    fup(i,1,qdx)
        pf("%d\n",ans[i]);
    return 0;
}

相关文章

  • 莫队算法

    莫队算法详解DQUERY - D-query题意:求区间内不同元素的数量,也就是求出现次数>=1的元素个数 小Z的...

  • 莫队算法

    带修改莫队

  • 2018-04-03 查漏补缺

    优雅的暴力-莫队莫队专题 A 区间不同个数的多少 C 因为没有快速读入 超时了。 没有强制转换成long long...

  • 燥热

    莫兮今天在辩论队队训的时候觉得很热,而且最近似乎又上火了,脸上也不平整,莫兮很是烦躁。 今天队训是对官僚主义的看法...

  • 广东队官宣签下北京夺冠功勋外援莫里斯,这步棋你怎么看?

    据广东队官方透露,目前球队已与兰多夫-莫里斯完成签约,他将代表广东队征战下赛季的CBA联赛,莫里斯将在新赛季与阿联...

  • 无奈的莫泰

    首先介绍下今天的主人公NBA火箭队中锋穆迪埃尤纳斯,中国球迷喜欢叫他-莫泰,其实关注过火箭队,关注过莫泰的人,都知...

  • 遗传算法helloworld级别的python实现(结果可视化)

    问题描述: 用遗传算法求使得F(X)最大的X,问题来源:莫烦的python教程之遗传算法 最终效果:

  • 2019体考我来了

    体训队合照 马老师和莫老师 东湖风光 武汉体育学院

  • 心法与算法

    虽然失去了NBA总冠军,但是作为连续5年进总决赛3次夺冠的勇士队,它的统治力也是源于心法与算法。 心法,勇士队的队...

  • 桥之队问问大家伙:百度算法究竟让你是喜是忧?

    百度算法的更新究竟是喜是忧?桥之队为你深度揭秘对待百度算法的态度该是何种!百度算法更新,有人欢喜有人忧!欢喜的是排...

网友评论

      本文标题:莫队算法

      本文链接:https://www.haomeiwen.com/subject/bgxzqxtx.html