P4119 Ynoi2018 未来日记

lxl 出的题好 duliu 啊。

感谢来自 fr200110217102 的博客 题解 P4119 【Ynoi2018未来日记】。

下标分块+值域分块+并查集

其实一开始的方向应该是尝试线段树或者其它的动态维护的算法，直到时间复杂度和空间复杂度对不上，你才会想到——要分块！

区间第 \(k\) 大

从分块做区间第 \(k\) 大出发，如果用二分以及其它的 \(\log\) 级的算法，单次查询的时间复杂度为 \(O(\sqrt n\log n)\)，肯定是直接 T 飞了。

从分块一点的角度考虑，维护每一个数在区间内出现了多少次，可以使用一个二维数组： \(sumc[i][j]=\) 前 \(i\) 块中 \(j\) 出现的次数。对于散块，我们可以开一个临时数组记录，这样子可以快速求出 \(x\) 在查询区间内出现了多少次。

但是这样子需要枚举第 \(k\) 大的数，单次查询的复杂的来到了 \(O(\log n)\)。

然后，本题的精髓——值域分块。

值域分块我们并不需要额外开数组统计在某个数在某块内出现了多少次，而是借助值域分块的思想，优化查询时间。

值域块长为 \(S\)，\(sums[i][k]=\) 前 \(i\) 块中，\((k-1)S+1\) 到 \(kS\) 的出现次数之和。

这样在求区间第 \(k\) 大时，我们先枚举答案在值域分块的那一块，在然后再在值域分块内枚举具体的数。枚举到某个数发现出现次数大于 \(k\)​ 了，那么就是它了。

时间复杂度 \(\sqrt V\)。

区间修改

每一个块内，用并查集把数字相同的点缩在一起，维护一个 \(rt[i][x]\) 表示第 \(i\) 块内某个值为 \(x\) 的数的位置。

整块修改

\(x\) 变 \(y\) 时，如果 \(rt[i][x]\) 不存在，无需更新 \(sums\) 和 \(sumc\) 即可。

如果 \(rt[i][x]\) 存在，分为两种情况：

1.\(rt[i][y]\) 存在，使 \(fa[rt[i][x]]=rt[i][y]\)。

2.\(rt[i][y]\) 不存在，使 \(rt[i][y]=rt[i][x]\) 并修改 \(a[rt[i][x]]\)​ 的值。

然后，更新 \(sums\) 和 \(sumc\) 即可。

散块修改

由于并查集的特殊结构，不能用类似整块的修改方式。但，这是散块。

直接强行将此块中 \(rt[i][x]\) 和 \(rt[i][y]\)​ 所在的并查集打散重新构建。

然后，更新 \(sums\) 和 \(sumc\) 即可。

单次修改复杂度在 \(O(\sqrt n)\) 级别。

另外由于空间限制，块长取 \(\sqrt n\) 会炸，所以这里块长取 \(600\)。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5,maxm=170,S=320;

int n,m,k,sz=600,vsz=317,mxv=1e5;
int a[maxn];
int L[maxm],R[maxm],bel[maxn];//bel 值的对应分块编号

int fa[maxn],rt[maxm][maxn];
inline int fr(int x){return fa[x]==x?x:fa[x]=fr(fa[x]);}
int cnt[maxm][maxn],sumc[maxm][maxn],sums[maxm][S];

void build(int p)
{
    for(int i=L[p];i<=R[p];i++)
    {
        if(!rt[p][a[i]]) rt[p][a[i]]=i;
        else fa[i]=rt[p][a[i]];
        ++cnt[p][a[i]];
    }
}
int stk[maxn];
inline void updata(int p,int l,int r,int x,int y)//散块更新
{
    int tmp=0,top=0;
    rt[p][x]=rt[p][y]=0;
    for(int i=L[p];i<=R[p];i++)
    {
        a[i]=a[fr(i)];
        if(a[i]==x||a[i]==y) stk[++top]=i;
    }
    for(int i=l;i<=r;i++) if(a[i]==x) a[i]=y,++tmp;
    for(int i=1;i<=top;i++) fa[stk[i]]=stk[i];
    for(int i=1;i<=top;i++)
    {
        int t=stk[i];
        int w=a[t];
        if(!rt[p][w]) rt[p][w]=t;
        else fa[t]=rt[p][w];
    }
    cnt[p][x]-=tmp,cnt[p][y]+=tmp;
    for(int i=p;i<=k;i++)
    {
        sumc[i][x]-=tmp,sumc[i][y]+=tmp;
        if(bel[x]!=bel[y])
            sums[i][bel[x]]-=tmp,sums[i][bel[y]]+=tmp;
    }
}

int c[maxn],s[S];
int main()
{
    scanf("%d%d",&n,&m);
    k=(n-1)/sz+1;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),fa[i]=i;
    for(int i=1;i<=mxv;i++) bel[i]=(i-1)/vsz+1;
    for(int i=1;i<=k;i++)
    {
        L[i]=(i-1)*sz+1,R[i]=min(i*sz,n);
        build(i);
        for(int j=1;j<=vsz;j++) sums[i][j]=sums[i-1][j];
        for(int j=1;j<=mxv;j++) sumc[i][j]=sumc[i-1][j]+cnt[i][j];
        for(int j=L[i];j<=R[i];j++) ++sums[i][bel[a[j]]];
    }

    while(m--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            int l,r,x,y;
            scanf("%d%d%d%d",&l,&r,&x,&y);
            if(x==y) continue;
            int lb=(l-1)/sz+1,rb=(r-1)/sz+1;
            if(lb==rb) updata(lb,l,r,x,y);
            else
            {
                updata(lb,l,R[lb],x,y);
                updata(rb,L[rb],r,x,y);
                int tmp,tmps=0;
                for(int i=lb+1;i<rb;i++)
                {
                    if(rt[i][x])
                    {
                        if(!rt[i][y]) rt[i][y]=rt[i][x],a[rt[i][x]]=y;
                        else fa[rt[i][x]]=rt[i][y];
                        rt[i][x]=0,tmp=cnt[i][x],tmps+=tmp;
                        cnt[i][y]+=tmp,cnt[i][x]=0;
                    }
                    sumc[i][x]-=tmps,sumc[i][y]+=tmps;
                    if(bel[x]!=bel[y]) sums[i][bel[x]]-=tmps,sums[i][bel[y]]+=tmps;
                }
                for(int i=rb;i<=k;i++)
                {
                    sumc[i][x]-=tmps,sumc[i][y]+=tmps;
                    if(bel[x]!=bel[y]) sums[i][bel[x]]-=tmps,sums[i][bel[y]]+=tmps;
                }
            }
        }
        else
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            int lb=(l-1)/sz+1,rb=(r-1)/sz+1;
            if(lb==rb)
            {
                for(int i=l;i<=r;i++) a[i]=a[fr(i)],++c[a[i]],++s[bel[a[i]]];
                int vl,vr,tmp=0;
                for(int i=1;i<=vsz;i++)
                {
                    tmp+=s[i];
                    if(tmp>=x){tmp-=s[i],vl=(i-1)*vsz+1,vr=i*vsz;break;}
                }
                for(int i=vl;i<=vr;i++)
                {
                    tmp+=c[i];
                    if(tmp>=x){printf("%d\n",i);break;}
                }
                for(int i=l;i<=r;i++) --c[a[i]],--s[bel[a[i]]];
            }
            else
            {
                for(int i=l;i<=R[lb];i++)
                {
                    a[i]=a[fr(i)];
                    ++c[a[i]],++s[bel[a[i]]];
                }
                for(int i=L[rb];i<=r;i++)
                {
                    a[i]=a[fr(i)];
                    ++c[a[i]],++s[bel[a[i]]];
                }
                int vl,vr,tmp=0;
                for(int i=1;i<=vsz;i++)
                {
                    tmp+=s[i]+sums[rb-1][i]-sums[lb][i];
                    if(tmp>=x){tmp-=s[i]+sums[rb-1][i]-sums[lb][i];vl=(i-1)*vsz+1,vr=i*vsz;break;}
                }
                for(int i=vl;i<=vr;i++)
                {
                    tmp+=c[i]+sumc[rb-1][i]-sumc[lb][i];
                    if(tmp>=x){printf("%d\n",i);break;}
                }
                for(int i=l;i<=R[lb];i++) --c[a[i]],--s[bel[a[i]]];
                for(int i=L[rb];i<=r;i++) --c[a[i]],--s[bel[a[i]]];
            }
        }
    }
}