Loading [MathJax]/jax/output/HTML-CSS/jax.js

【题解】「MtOI2019」手牵手走向明天 序列分块 — Qiuly

于由Qiuly发布

序列分块，每个块维护一个 √n×√n 的矩阵表示这个块中颜色与颜色的距离，再维护每个颜色到左右端点的最短距离。

容易发现查询的时候很好查询，问题在于修改操作：要对每一个块进行处理，光是枚举块就要用掉 O(√n) 的时间，那就只能在一个块上留下 O(1) 的时间来修改了，这似乎很难办。

深入思考一下，假设一个块中最开始有 m 个颜色，那么修改 x 为 y ：

  • x 没有：那就不要管了。
  • y 没有，但 x 有：记录一个颜色的实际值即可，修改的时候只需要修改指针。
  • x,y 都有：对于 x,y 以外的 m−2 个颜色，每一个颜色都需要进行 O(1) 次修改，然后合并 x,y 的颜色信息也是 O(m) 的，总时间复杂度是 O(m) ，并且操作完 m 减少一。

那么一个块最多产生多少次操作？因为 m 最大为 √n ，所以一个块中的操作次数其实是 O(n) 级别的。所以总操作次数就是 O(n√n) 。

关于操作：

  • 区间修改：
    • 整块：按照上述方式做。

    • 散块：散块的话最大的问题在于关于 y 的距离怎么修改，因为做的是 min ，直接修改似乎不好办。于是你可以考虑到，先用 O(√n) 的代价将这一块的 ai 的实际值求出来，然后对于 y 的相关信息直接求一遍，x 的相关信息也直接求一遍，这一部分的复杂度是 O(√n) 的。

    需要注意的是，因为散块的修改可能增加一个颜色，所以还需要重新分析一下这玩意的复杂度。事实上，首先定义一个 total=∑m2≤n√n 之内的，然后每次修改的整块其实就是花 O(x) 的代价将 total 减去 x 。散块增加一个颜色最多将 total 增加上 √n ，如果考虑最劣的散块情况，那么 total 大概是 O((n+m)√n) 的。

    因此这么做还是对的。

  • 区间查询：区间内的可以直接查表，不同区间的可以扫过去，记录一下上一个位置（因为我们维护了一个颜色到块两边的距离），常数不大。

关于实现：

  • 代码较长，细节多，一般卡常。
  • 关于整块修改：可以将 x 的编号和最大的编号交换，然后操作完后删去 x 就直接将最大编号减一即可。
  • 实现的时候关于并查集我不是按照值域记录 rt ，而是直接按照编号记录 rt，空间省了但是同时细节很多。
  • 散块修改常数巨大，把块大小调小点：√25n ，然后就过去了。

但我的常数还是很大 /ll

cint N=1e5+3;
cint S=2e2+3; // SqrtN
cint T=5e2+3;

int n,m,q,a[N];

// {{{ Data_Struct_Block

int sqrtn,id[N],L[T],R[T];
int dis[T][S][S],disl[T][S],disr[T][S],pot[T][N],rpot[T][S],lim[T];
int rt[T][S],col[N],fa[N];

int find(int x) {return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}

inline void upd_dis(cint &t,cint &_L,cint &_R,cint &y) { // {{{ upd_dis
    int tl=-inf; cint &py=pot[t][y]; lep(j,_L,_R) {
        if(col[find(j)]==y) tl=j;
        chkmin(dis[t][py][pot[t][col[find(j)]]],j-tl);
        chkmin(dis[t][pot[t][col[find(j)]]][py],j-tl);
    }
    tl=inf; rep(j,_R,_L) {
        if(col[find(j)]==y) tl=j;
        chkmin(dis[t][py][pot[t][col[find(j)]]],tl-j);
        chkmin(dis[t][pot[t][col[find(j)]]][py],tl-j);
    }
} // }}}

inline void init() { // {{{ init
    sqrtn=sqrt(n*2/5);

    for(int i=1,c=1,j;i<=n;i=j+1,++c) {
        L[c]=i,R[c]=j=min(n,i+sqrtn);
        lep(t,L[c],R[c]) id[t]=c;
    } m=id[n];

    memset(disl,60,sizeof(disl)),memset(disr,-61,sizeof(disr)),memset(dis,60,sizeof(dis));
    lep(t,1,m) {
        lep(i,L[t],R[t]) {
            if(!pot[t][a[i]]) 
                rpot[t][pot[t][a[i]]=++lim[t]]=a[i],col[rt[t][lim[t]]=i]=a[i];
            fa[i]=rt[t][pot[t][a[i]]];
        }
        lep(i,L[t],R[t]) if(fa[i]==i) upd_dis(t,L[t],R[t],a[i]);
        rep(i,R[t],L[t]) disl[t][pot[t][a[i]]]=i;
        lep(i,L[t],R[t]) disr[t][pot[t][a[i]]]=i;
    }
} // }}}

// {{{ query
inline int calc(cint &l,cint &r,cint &x,cint &y) {
    int ans=inf,lx=-inf,ly=-inf;
    lep(i,l,r) {
        if(col[find(i)]==x) lx=i,chkmin(ans,i-ly);
        if(col[find(i)]==y) ly=i,chkmin(ans,i-lx);
    }
    return ans;
}
inline int query(cint &l,cint &r,cint &x,cint &y) {
    if(x==y) {
        bool flag=false;
        if(id[l]==id[r]) lep(i,l,r) flag|=col[find(i)]==x;
        else {
            lep(i,l,R[id[l]]) flag|=col[find(i)]==x;
            lep(i,L[id[r]],r) flag|=col[find(i)]==x;
            lep(i,id[l]+1,id[r]-1) flag|=pot[i][x]>0;
        }
        return -1+flag;
    }
    if(id[l]==id[r]) return calc(l,r,x,y);

    int ans=min(calc(l,R[id[l]],x,y),calc(L[id[r]],r,x,y));
    int lx=disr[id[l]][pot[id[l]][x]]; if(lx<l) lx=-inf;
    int ly=disr[id[l]][pot[id[l]][y]]; if(ly<l) ly=-inf;

    lep(i,id[l]+1,id[r]-1) {
        if(pot[i][x]) chkmin(ans,disl[i][pot[i][x]]-ly);
        if(pot[i][y]) chkmin(ans,disl[i][pot[i][y]]-lx);
        if(pot[i][x]) lx=disr[i][pot[i][x]];
        if(pot[i][y]) ly=disr[i][pot[i][y]];
        chkmin(ans,dis[i][pot[i][x]][pot[i][y]]);
    }

    int rx=disl[id[r]][pot[id[r]][x]]; if(rx>r) rx=inf;
    int ry=disl[id[r]][pot[id[r]][y]]; if(ry>r) ry=inf;
    return min(ans,min(rx-ly,ry-lx));
}
// }}}

// {{{ modify
inline void deleteid(cint &t,int &px) {
    cint &lt=lim[t]; swap(rt[t][px],rt[t][lt]);
    lep(i,1,lt) swap(dis[t][px][i],dis[t][lt][i]),swap(dis[t][i][px],dis[t][i][lt]);
    swap(disl[t][px],disl[t][lt]),swap(disr[t][px],disr[t][lt]);
    swap(rpot[t][px],rpot[t][lt]),swap(pot[t][rpot[t][px]],px),--lim[t];
}
inline void rebuild(cint &t,cint &l,cint &r,cint &x,cint &y) {
    int live=0,&px=pot[t][x],&py=pot[t][y]; cint &_L=L[t],&_R=R[t];
    lep(i,l,r) live+=col[find(i)]==x; if(!live) return ;

    if(!py) {
        rpot[t][py=++lim[t]]=y,disl[t][py]=inf,disr[t][py]=-inf;
        lep(i,1,lim[t]) dis[t][py][i]=dis[t][i][py]=inf;
    }
    lep(i,1,lim[t]) dis[t][px][i]=dis[t][i][px]=inf;

    lep(i,_L,_R) a[i]=col[find(i)],rt[t][pot[t][a[i]]]=0;
    lep(i,l,r) if(a[i]==x) a[i]=y,--live;
    lep(i,_L,_R) live+=a[i]==x; if(!live) deleteid(t,px);

    lep(i,_L,_R) {
        if(!rt[t][pot[t][a[i]]]) col[rt[t][pot[t][a[i]]]=i]=a[i];
        fa[i]=rt[t][pot[t][a[i]]];
    }

    upd_dis(t,_L,_R,y); if(live) upd_dis(t,_L,_R,x);
    rep(i,_R,_L) disl[t][pot[t][a[i]]]=i;
    lep(i,_L,_R) disr[t][pot[t][a[i]]]=i;
    if(!live) px=0;
}
inline void modify(cint &l,cint &r,cint &x,cint &y) {
    if(x==y) return ;
    if(id[l]==id[r]) return rebuild(id[l],l,r,x,y),void();

    rebuild(id[l],l,R[id[l]],x,y);
    rebuild(id[r],L[id[r]],r,x,y);

    lep(t,id[l]+1,id[r]-1) {
        int &px=pot[t][x],&py=pot[t][y];
        if(!px) continue;
        if(!py) {rpot[t][py=px]=y,px=0,col[rt[t][py]]=y; continue;}

        fa[rt[t][px]]=rt[t][py],rt[t][px]=0;
        rep(i,lim[t],1) chkmin(dis[t][py][i],dis[t][px][i]),chkmin(dis[t][i][py],dis[t][i][px]);
        chkmin(disl[t][py],disl[t][px]),chkmax(disr[t][py],disr[t][px]);
        rep(i,lim[t],1) dis[t][px][i]=dis[t][i][px]=inf;
        deleteid(t,px),px=0;
    }
}
// }}}

// }}}

int op,l,r,x,y;
int main() {
    IN(n,q);
    lep(i,1,n) IN(a[i]);
    init();

    lep(i,1,q) {
        IN(op,l,r,x,y);
        if(op==1) modify(l,r,x,y);
        if(op==2) {
            int ans=query(l,r,x,y);
            printf("%d\n",ans>n?-1:ans);
        }
    }
    return 0;
}
C++
Copy
分类： 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

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