题解 CF940F 【Machine Learning】

ouuan · 2018-09-30 18:02:31 · 题解

其实这题根本不用把数字也分块..

如果不会带修莫队的话可以到网上找教程，也可以看我写的教程

首先将数列中原本的数字以及所有修改中的数字全部离散化，然后就是普通的带修莫队，不同之处在于更新答案时不是记录某个数字出现了几次，而是在更新数字出现的次数的同时更新“数字出现的次数”出现的次数，即：

void add(int x)
{
    --tot[cnt[x]];
    ++tot[++cnt[x]];
}

void del(int x)
{
    --tot[cnt[x]];
    ++tot[--cnt[x]];
}

然后是为什么可以暴力求mex：

考虑答案为 x，那么存在出现了 1 次的数、出现了 2 次的数……出现了 x-1 次的数。所以，\sum\limits_{i=1}^{x-1}i<=n，就是说答案是 O(\sqrt{n}) 级别的，暴力求解的复杂度为 O(n\sqrt{n})，而带修莫队的复杂度为 O(n^{\frac{5}{3}})，也就是说暴力求mex完全不影响总复杂度。

所以一行求mex就好了：

for (ans[q[i].id]=1;tot[ans[q[i].id]]>0;++ans[q[i].id]);

完整代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

inline int read()
{
    char c;int out=0;
    for (c=getchar();c<'0'||c>'9';c=getchar());
    for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}
    return out;
}
void write(int x)
{
    if (x>9){write(x/10);}
    putchar(x%10+'0');
}

const int B=2154;

struct Query
{
    int l,r,t,id;
    bool operator<(Query& y)
    {
        return l/B==y.l/B?(r/B==y.r/B?t<y.t:r<y.r):l<y.l;
    }
} q[100010];

struct Change
{
    int p,x;
} c[100010];

void add(int x);
void del(int x);
void modify(int ti,int qu);

int n,m,a[100010],b[200010],cnt[200010],tot[100010],qcnt,ccnt,qaq,now,ans[100010];

int main()
{
    int i,j,l=1,r=0,type;

    n=read();
    m=read();

    for (i=1;i<=n;++i)
    {
        b[qaq++]=a[i]=read();
    }

    for (i=0;i<m;++i)
    {
        type=read();
        if (type==1)
        {
            q[++qcnt].l=read();
            q[qcnt].r=read();
            q[qcnt].t=ccnt;
            q[qcnt].id=qcnt;
        }
        else
        {
            c[++ccnt].p=read();
            b[qaq++]=c[ccnt].x=read();
        }
    }

    sort(b,b+qaq);
    qaq=unique(b,b+qaq)-b;

    for (i=1;i<=n;++i)
    {
        a[i]=lower_bound(b,b+qaq,a[i])-b;
    }

    for (i=1;i<=ccnt;++i)
    {
        c[i].x=lower_bound(b,b+qaq,c[i].x)-b;
    }

    sort(q+1,q+qcnt+1);

    for (i=1;i<=qcnt;++i)
    {
        while (l>q[i].l)
        {
            add(a[--l]);
        }
        while (r<q[i].r)
        {
            add(a[++r]);
        }
        while (l<q[i].l)
        {
            del(a[l++]);
        }
        while (r>q[i].r)
        {
            del(a[r--]);
        }
        while (now<q[i].t)
        {
            modify(++now,i);
        }
        while (now>q[i].t)
        {
            modify(now--,i);
        }
        for (ans[q[i].id]=1;tot[ans[q[i].id]]>0;++ans[q[i].id]);
    }

    for (i=1;i<=qcnt;++i)
    {
        write(ans[i]);
        putchar('\n');
    }

    return 0;
}

void add(int x)
{
    --tot[cnt[x]];
    ++tot[++cnt[x]];
}

void del(int x)
{
    --tot[cnt[x]];
    ++tot[--cnt[x]];
}

void modify(int ti,int qu)
{
    if (c[ti].p>=q[qu].l&&c[ti].p<=q[qu].r)
    {
        del(a[c[ti].p]);
        add(c[ti].x);
    }
    swap(c[ti].x,a[c[ti].p]);
}