【题解】[Ynoi2018] 未来日记 序列分块+值域分块 Luogu P4119 —— Demoe

于由Demoe发布

题目传送门

2020 的遗愿

题意

  • 给定一个序列，支持区间替换和区间 $\text{kth}$ 操作。

Sol

因为是最初分块所以考虑序列分块。（

一般情况我们查询区间 $\text{kth}$ 都是树套树啥的。

带上二分，线段树套平衡树是 $\log^3 n$ 的。

我们这里也考虑树套树（？

好像想不出来咋整

这个修改对于树状结构很不方便。

那么我们考虑序列分块和值域分块。

首先预处理 $cnt1_{i,j}$ 表示前 $i$ 块中值域在第 $j$ 块的数出现次数，$cnt2_{i,j}$ 表示前 $i$ 块中 $j$ 出现次数 。

预处理 $O(n\sqrt n)$

那么查询 $\text{kth}$ 就很方便了。

整块用 $cnt1$ 和 $cnt2$ 处理，散块开个桶记一下即可。

从小到大先扫值域块 找到目标后再扫值即可。

复杂度 $O(\sqrt n)$

inline int kth(int l,int r,int k){
    int sum=0;
    if(bl[l]==bl[r]){
        restore(bl[l]);
        for(re i=l;i<=r;++i) sum2[i]=a[i];
        nth_element(sum2+l,sum2+l+k-1,sum2+r+1);int ans=sum2[l+k-1];
        for(re i=l;i<=r;++i) sum2[i]=0;
        return ans;
    }
    restore(bl[l]);restore(bl[r]);
    for(re i=l;i<=R[bl[l]];++i) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(re i=L[bl[r]];i<=r;++i) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(re i=1;i<=(N-1)/len+1;++i)
        if(sum+sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i]>=k){
            for(re j=(i-1)*len+1;j<=i*len;++j)
                if(sum+sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j]>=k){
                    for(re i=l;i<=R[bl[l]];++i) --sum1[bl[a[i]]],--sum2[a[i]];
                    for(re i=L[bl[r]];i<=r;++i) --sum1[bl[a[i]]],--sum2[a[i]]=0;
                    return j;
                }
                else sum+=sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j];
        }
        else sum+=sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i];
}

考虑区间替换。

散块暴力修即可。

对于每个整块，考虑一下咋整。

我不太会 参考了神仙题解

考虑对块内每个权记一个对应权，记做 $id_{x,i}$（$x$ 是块，$i$ 是原权）

同时其逆也记下，记做 $rid_{x,i}$（$x$ 是块，$i$ 是对应权）

再用 $pos_i$ 记录每一位的对应权。（$i$ 是序列上位置）

如果要还原序列，只需要让 $a_i=rid_{block_i,pos_i}$。

块内无 $x$

跳过

块内有 $x$ 无 $y$

可将 $id_{block,y}=id_{block,x}$ 同时 $rid_{block,id_{block,x}}=y$，记得 $id_{block,x}=0$

块内有 $x$ $y$

考虑此时块内权值种类少 $1$。

而权值种类总共不超过 $n+m$。

均摊后暴力重构复杂度总和为 $O((n+m)\sqrt n)$。

暴力重构即可。

对于两个 $cnt$ 数组的更新，可以先将其差分为每块的，最后再合并。一次 $O(\sqrt n)$。

inline void modify(int l,int r,int x,int y){
    if(x==y||cnt2[bl[r]][x]-cnt2[bl[l]-1][x]==0) return ;
    for(re i=bl[n];i>=bl[l];--i) cnt2[i][x]-=cnt2[i-1][x],cnt2[i][y]-=cnt2[i-1][y],cnt1[i][bl[x]]-=cnt1[i-1][bl[x]],cnt1[i][bl[y]]-=cnt1[i-1][bl[y]];
    if(bl[l]==bl[r]){
        restore(bl[l]);
        reconstruct(l,r,x,y);
        build(bl[l]);
        for(re i=bl[l];i<=bl[n];++i) cnt2[i][x]+=cnt2[i-1][x],cnt2[i][y]+=cnt2[i-1][y],cnt1[i][bl[x]]+=cnt1[i-1][bl[x]],cnt1[i][bl[y]]+=cnt1[i-1][bl[y]];
        return ;
    }
    restore(bl[l]);restore(bl[r]);
    reconstruct(l,R[bl[l]],x,y);reconstruct(L[bl[r]],r,x,y);
    build(bl[l]);build(bl[r]);
    for(re i=bl[l]+1;i<bl[r];++i){
        if(!cnt2[i][x]) continue;
        if(cnt2[i][y]){
            restore(i);
            reconstruct(L[i],R[i],x,y);
            build(i);
        }
        else{
            cnt1[i][bl[y]]+=cnt2[i][x],cnt1[i][bl[x]]-=cnt2[i][x];
            cnt2[i][y]=cnt2[i][x];cnt2[i][x]=0;
            change(i,x,y);
        }
    }
    for(re i=bl[l];i<=bl[n];++i) cnt2[i][x]+=cnt2[i-1][x],cnt2[i][y]+=cnt2[i-1][y],cnt1[i][bl[x]]+=cnt1[i-1][bl[x]],cnt1[i][bl[y]]+=cnt1[i-1][bl[y]];
}

总复杂度 $(n+m)\sqrt n$。

记得 $\text{Change}$ 时清空 $\text{id}$。

$\text{Code}$

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back

using namespace std;
typedef long long ll;

template <typename T> void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(int x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}

// ---------- IO ---------- //

const int N=1e5+20,SQ=320;
int n,m,a[N],len,bl[N],L[N],R[N],sum1[SQ],sum2[N];
int id[SQ][N],rid[SQ][N],pos[N];  // id[i][j] 第 i 块中 j 离散化值 rid[i][j] 为 id 的逆运算 

int cnt1[SQ][SQ],cnt2[SQ][N];  // cnt1[i][j] 前 i 块中值域在第 j 块的数出现次数 cnt2[i][j] 前 i 块中 j 出现次数 

inline void build(int x){
    int tot=0;
    for(re i=1;i<=len;++i) id[x][rid[x][i]]=0;
    for(re i=L[x];i<=R[x];++i)
        if(!id[x][a[i]]) id[x][a[i]]=++tot,rid[x][tot]=a[i];
    for(re i=L[x];i<=R[x];++i) pos[i]=id[x][a[i]];
}

inline void restore(int x){
    for(re i=L[x];i<=R[x];++i) a[i]=rid[x][pos[i]];
}

inline void reconstruct(int l,int r,int x,int y){
    for(re i=l;i<=r;++i)
        if(a[i]==x){
            --cnt2[bl[l]][x],++cnt2[bl[l]][y];
            --cnt1[bl[l]][bl[x]],++cnt1[bl[l]][bl[y]];
            a[i]=y;
        }
}

inline void change(int i,int x,int y){
    id[i][y]=id[i][x];rid[i][id[i][x]]=y;id[i][x]=0;
}

// ---------- Sqrt On Range ---------- //

inline void modify(int l,int r,int x,int y){
    if(x==y||cnt2[bl[r]][x]-cnt2[bl[l]-1][x]==0) return ;
    for(re i=bl[n];i>=bl[l];--i) cnt2[i][x]-=cnt2[i-1][x],cnt2[i][y]-=cnt2[i-1][y],cnt1[i][bl[x]]-=cnt1[i-1][bl[x]],cnt1[i][bl[y]]-=cnt1[i-1][bl[y]];
    if(bl[l]==bl[r]){
        restore(bl[l]);
        reconstruct(l,r,x,y);
        build(bl[l]);
        for(re i=bl[l];i<=bl[n];++i) cnt2[i][x]+=cnt2[i-1][x],cnt2[i][y]+=cnt2[i-1][y],cnt1[i][bl[x]]+=cnt1[i-1][bl[x]],cnt1[i][bl[y]]+=cnt1[i-1][bl[y]];
        return ;
    }
    restore(bl[l]);restore(bl[r]);
    reconstruct(l,R[bl[l]],x,y);reconstruct(L[bl[r]],r,x,y);
    build(bl[l]);build(bl[r]);
    for(re i=bl[l]+1;i<bl[r];++i){
        if(!cnt2[i][x]) continue;
        if(cnt2[i][y]){
            restore(i);
            reconstruct(L[i],R[i],x,y);
            build(i);
        }
        else{
            cnt1[i][bl[y]]+=cnt2[i][x],cnt1[i][bl[x]]-=cnt2[i][x];
            cnt2[i][y]=cnt2[i][x];cnt2[i][x]=0;
            change(i,x,y);
        }
    }
    for(re i=bl[l];i<=bl[n];++i) cnt2[i][x]+=cnt2[i-1][x],cnt2[i][y]+=cnt2[i-1][y],cnt1[i][bl[x]]+=cnt1[i-1][bl[x]],cnt1[i][bl[y]]+=cnt1[i-1][bl[y]];
}

inline int kth(int l,int r,int k){
    int sum=0;
    if(bl[l]==bl[r]){
        restore(bl[l]);
        for(re i=l;i<=r;++i) sum2[i]=a[i];
        nth_element(sum2+l,sum2+l+k-1,sum2+r+1);int ans=sum2[l+k-1];
        for(re i=l;i<=r;++i) sum2[i]=0;
        return ans;
    }
    restore(bl[l]);restore(bl[r]);
    for(re i=l;i<=R[bl[l]];++i) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(re i=L[bl[r]];i<=r;++i) ++sum1[bl[a[i]]],++sum2[a[i]];
    for(re i=1;i<=(N-1)/len+1;++i)
        if(sum+sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i]>=k){
            for(re j=(i-1)*len+1;j<=i*len;++j)
                if(sum+sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j]>=k){
                    for(re i=l;i<=R[bl[l]];++i) --sum1[bl[a[i]]],--sum2[a[i]];
                    for(re i=L[bl[r]];i<=r;++i) --sum1[bl[a[i]]],--sum2[a[i]]=0;
                    return j;
                }
                else sum+=sum2[j]+cnt2[bl[r]-1][j]-cnt2[bl[l]][j];
        }
        else sum+=sum1[i]+cnt1[bl[r]-1][i]-cnt1[bl[l]][i];
}

// ---------- Sqrt ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);len=(int)sqrt(n);
    for(re i=1;i<N;++i) bl[i]=(i-1)/len+1;
    for(re i=1;i<=n;++i) rd(a[i]);
    for(re i=1;i<=bl[n];++i) L[i]=(i-1)*len+1,R[i]=i*len;R[bl[n]]=n;
    for(re i=1;i<=bl[n];++i) build(i);
    for(re x=1;x<=bl[n];++x){
        for(re i=1;i<=bl[N-1];++i) cnt1[x][i]=cnt1[x-1][i];
        for(re i=1;i<N;++i) cnt2[x][i]=cnt2[x-1][i];
        for(re i=L[x];i<=R[x];++i) ++cnt1[x][bl[a[i]]],++cnt2[x][a[i]];
    }
    int op,l,r,x,y;
    for(re i=1;i<=m;++i){
        rd(op);rd(l);rd(r);
        if(op==1) rd(x),rd(y),modify(l,r,x,y);
        else rd(x),wr(kth(l,r,x)),puts("");
    }
    return 0;
}

// ---------- Main ---------- //
分类： 文章

Demoe

菜菜/kk | 原 id Daniel_Jiang

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注