洛谷P4119 [Ynoi2018]未来日记 题解

Jun 18th, 2020
  • 在其它设备中阅读本文章

太毒瘤了这个... 窝本来星期天晚上困得不行想做点什么提提神, 然后就跳进了这个大坑, 花了整整四个晚上来填... 另外就是建议看一下窝的 另一道题的题解 (虽然过不了就是了), 很多操作和里面都是类似的.

解题思路

首先看到 Ynoi 就想到分块, 并且看到值域和 $n$ 一样都是 $\le10^5$ 可以大胆猜测值域也要分块.好吧为什么要分块别的大佬们已经说得很清楚了, 那么窝说一下具体的操作.

首先是保存数据的方式. 不妨像 Snow_Miku 大佬一样先用并查集搞一下,$fat(i)$ 即是 $i$ 的父亲.

根放在最左边好写一些.
引自 Snow_Miku,2020/06/17

所以就记录 $frt(i,j)$ 为第 $i$ 块内最靠前的 $j$ 的位置. 同时值域也要分块, 维护 $sbk(i,j)$ 为 前 $i$ 块 中在值域块 $j$ 当中的数的个数, 护 $snm(i,j)$ 为 前 $i$ 块 中 $a_{x\in 第 i 块}=j$ 的个数. 但是这样对修改操作比较不友好, 所以还要维护辅助数组 $cbk(i,j)$ 和 $cnm(i,j)$(友善度数组 ) 分别表示 第 $i$ 块 中的信息.

查询 ($opt=2$)

虽然查询操作的 $opt$ 理论上排在后面但是比较好写所以就先写了.

首先值域分块找区间第 $k$ 大这个操作已经没什么好特别的了. 暴力将两边的块的内容统计一下, 中间的块有前缀和, 就可以快速求出值域块 $i$ 内的数和 $a_{x\in 第 i 块}=i$ 的个数. 首先将第 $k$ 小数定位到值域块 $u$ 满足前 $u-1$ 块的数的个数少于 $k$ 且前 $u$ 块的个数不少于 $k$, 然后再扫一遍 $u$ 这个块求一个数 $v$ 满足小于 $v$ 的数的个数少于 $k$ 且小于 $v+1$ 的数的个数不少于 $k$. 这个 $v$ 显然就是答案.

另外要注意的就是窝的写法是不能用memset()的, 因为每一次都是统计了边缘块里所有的数, 统计数组的最大值达到了 $10^5$. 所以只能再扫一遍一个一个地减掉. 还有就是记得特判 $l$ 和 $r$ 在同一个块内的情况. 写出伪代码 

function find_kth(l,r,k)
    if l和r在同一块 then
        /*特判,单独处理并返回*/
    end if
    sum←0 /*sum表示当前已经统计了多少个数*/
    /*统计两侧的散块*/
    for i←l to l所在块右端点 by 1 do
        fbk[a[i]所在块]←fbk[a[i]所在块]+1
        fnm[a[i]]←fnm[a[i]]+1
    end for
    for i←r to r所在块左端点 by -1 do
        fbk[a[i]所在块]←fbk[a[i]所在块]+1
        fnm[a[i]]←fnm[a[i]]+1
    end for
    for i←1 to q by 1 do /*q就是$sqrt n$*/
        sum←sum+cbk[r所在块-1][i]-cbk[l所在块][i]+fbk[i]
        if sum>=k then /*前面已经有不少于k个数了*/
            for j←(i+1)*p to i*p by -1 do /*逆序统计第i块值域*/
                sum←sum-cnm[r所在块-1][j]+cnm[l所在块][j]-fnm[j]
                if sum<k then /*前面的数少于k个*/
                    ret←k /*记录下来,不能直接返回是因为还要清空统计数组*/
                end if
            end for
        end if
    end for
    /*清空统计数组,用memset()会T飞*/
    for i←l to l所在块右端点 by 1 do
        fbk[a[i]所在块]←fbk[a[i]所在块]-1
        fnm[a[i]]←fnm[a[i]]-1
    end for
    for i←r to r所在块左端点 by -1 do
        fbk[a[i]所在块]←fbk[a[i]所在块]-1
        fnm[a[i]]←fnm[a[i]]-1
    end for
    return ret
end function

Snow_Miku 大佬的写法 和窝的有点不一样. 她是先扫到 $u$, 然后只统计 $u$ 里面数的情况, 统计数组是连续的 $\sqrt n$ 大小的值域, 所以可以直接memset(). 并且这两种写法结合起来也是 $\Theta(\sqrt n)$ 的复杂度, 并不能优化.

更新 ($opt=1$)

整体上来说如果修改一个数就要重新更新一遍前缀和数组的话显然就

会被艹飞
引自 Snow_Miku 的题解

(因为每次扫一遍前缀和的复杂度是至少 $\Theta(\sqrt n)$ 的), 所以需要 $cbk(i,j)$ 和 $cnm(i,j)$ 来存储每个块当前的状况, 区间更新完后再一次性更新 $sbk(i,j)$ 和 $snm(i,j)$. 并且显然更新操作只会影响包括 $x$ 和 $y$ 在内的前缀和, 所以扫前缀和的时候只需要扫这两个数组. 这样单次更新后维护前缀和的复杂度就是 $\Theta(\sqrt n)$. 写出伪代码

sbk[0][x所在块]←cbk[0][x所在块]
snm[0]←cnm[0]
sbk[0][y所在块]←cbk[0][y所在块]
snm[0]←cnm[0]
for i←1 to q by 1 do
    sbk[i][x所在块]←sbk[i-1][x所在块]+cbk[i][x所在块]
    snm[i][x]←snm[i-1][x]+cnm[i][x]
    sbk[i][y所在块]←sbk[i-1][y所在块]+cbk[i][y所在块]
    snm[i][y]←snm[i-1][y]+cnm[i][y]
end for

如果 $x=y$

显然跳过就好了.

对于左边的散块

可以暴力重构这个区间, 但是好像没有别的大佬写具体怎么暴力法, 所以窝就试着具体讲一下.

  • 首先显然对于 $a_i\not\in\{x,y\}$ 显然不会有任何影响, 所以直接跳过这一部分即可.

  • 然后因为要保证性质 $frt(i,j)$ 在最左边所以开始讨论

    • $y$ 的根在 $l$ 的左边或者在 $x$ 的根的左边($frt(l 所在块,y)<\min\{l,frt(l 所在块,x)\}$), 那么直接把 $l$ 右边所有的 $x$ 的 $fat(x)$ 设为 $frt(l 所在块,y)$ 即可;
    • $y$ 的根的位置不满足上一条或者这个区间内根本没有 $y$, 就从 $l$ 开始往右扫, 扫到的第一个 $x$ 或 $y$ 作为根, 剩下的 $fat(x)$ 和 $fat(y)$ 都指向它, 并将 $a_根 $ 设为 $y$.
  • 另外就是如果 $x$ 的根在 $l$ 右边那么修改后这个区间就没有 $x$ 了, 记得 $frt(l 所在块,x)=-1$.

对于右边的散块

和左边的散块类似, 但是对于根的处理没有那么多讨论.

  • 同样跳过 $a_i\not\in\{x,y\}$, 并且开始时先 $frt(r 所在块,x)=-1$.
  • 然后直接从 $r$ 所在的块的最左边开始扫, 扫到的第一个 $x$ 或 $y$ 作为根, 剩下的 $fat(\mathop x_\limits{x\le r})$ 和 $fat(y)$ 都指向它, 并将 $a_根 $ 设为 $y$, 并且注意对于 $a_{i>r}=x$ 不修改.
  • 如果此时 $i>r$ 且 $a_i=x$, 那么意味着修改后 $r$ 所在块内还有 $x$ 存在, 将第一个满足以上条件的 $x$ 作为根, 剩下的 $fat(\mathop x_\limits{x>r})$ 和指向它.

对于中间的整块

这个就比较容易了, 直接判一下 $x$ 存不存在, 然后看 $x$ 和 $y$ 的根哪个比较靠前, 把靠后的根指过去即可. 当然同样要记得 $a_根 =y$.

如果 $l$ 和 $r$ 在同一块内

结合一下左右散块的写法即可,留作课后习题.

好吧还是说一下, 该跳过的跳过, 然后像处理右边的散块一样扫一遍, 只是将 $x\le r$ 的条件换成 $l\le x\le r$ 即可.

另外, 每次修改的时候都要对应修改 $cbk(i,j)$ 和 $cnm(i,j)$.

复杂度分析

首先分块自带的 $\sqrt n$ 显然在, 然后虽然有并查集但是因为都只是在同一块内操作就是 $\lg\sqrt n$. 这样总复杂度就是 $\Theta(n\sqrt n\lg\sqrt n)$, 就很悬.

交上去发现有 $36\%$ 的点 被艹飞 T 掉了, 于是调一下块长. 根据 Snow_Miku 大佬的建议 $500$ 到 $600$, 实测 $525$ 过 $91\%$,$600$ 可 AC, 此时总共有 $167$ 个块. 另外这里的块长是指数组块长, 值域块长还是 $\lceil\sqrt n\rceil=317$.

Code

还有什么疑问可以看代码,虽然并没有注释.

#include <cstdio>
#include <cstring>
using namespace std;

#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048577,stdin),p0==p1)?EOF:*p0++)

inline int read() {
    static char buf[1048577],*p0,*p1;
    int re=0; char ch=gc();
    while (ch<48||ch>57) ch=gc();
    while (ch>47&&ch<58) {
        re=(re<<3)+(re<<1)+(ch^48);
        ch=gc();
    }
    return re;
}

const int qa=317;
const int qb=600; 
const int qc=167;

int n,a[100505];
int pa[100505],pb[100505];
int cbk[601][318],cnm[601][100505];
int sbk[601][318],snm[601][100505];
int fat[100505],frt[601][100505];

int find_fat(int ops) {
    return ops==fat[ops]?ops:fat[ops]=find_fat(fat[ops]);
}

inline void update(int opl,int opr,int opx,int opy) {
    if (opx==opy) return;
    if (pb[opl]==pb[opr]&&frt[pb[opl]][opx]!=-1) {
        int urt=frt[pb[opl]][opx]=-1;
        for (int i=pb[opl]*qb;pb[i]==pb[opl];++i) a[i]=a[find_fat(i)];
        for (int i=pb[opl]*qb;pb[i]==pb[opl];++i) {
            if (a[i]==opx) {
                if (i>=opl&&i<=opr) {
                    urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
                    --cbk[pb[opl]][pa[opx]]; --cnm[pb[opl]][opx];
                    ++cbk[pb[opl]][pa[opy]]; ++cnm[pb[opl]][opy];
                }
                else {
                    if (frt[pb[opl]][opx]!=-1) fat[i]=frt[pb[opl]][opx];
                    else frt[pb[opl]][opx]=fat[i]=i;
                }
            }
            else if (a[i]==opy)
                urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
        }
        a[frt[pb[opl]][opy]=urt]=opy;
    }
    else {
        int urt;
        if (frt[pb[opl]][opx]==-1);
        else if (frt[pb[opl]][opy]!=-1&&frt[pb[opl]][opy]<opl) {
            urt=frt[pb[opl]][opy];
            for (int i=pb[opl]*qb;pb[i]==pb[opl];++i) a[i]=a[find_fat(i)];
            for (int i=opl;pb[i]==pb[opl];++i)
                if (a[i]==opx) {
                    fat[i]=urt;
                    --cbk[pb[opl]][pa[opx]]; --cnm[pb[opl]][opx];
                    ++cbk[pb[opl]][pa[opy]]; ++cnm[pb[opl]][opy];
                }
        }
        else {
            urt=-1;
            for (int i=pb[opl]*qb;pb[i]==pb[opl];++i) a[i]=a[find_fat(i)];
            for (int i=opl;pb[i]==pb[opl];++i) {
                if (a[i]==opx) {
                    urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
                    --cbk[pb[opl]][pa[opx]]; --cnm[pb[opl]][opx];
                    ++cbk[pb[opl]][pa[opy]]; ++cnm[pb[opl]][opy];
                }
                else if (a[i]==opy)
                    urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
            }
            a[frt[pb[opl]][opy]=urt]=opy;
        }
        if (frt[pb[opl]][opx]>=opl) frt[pb[opl]][opx]=-1;
        if (frt[pb[opr]][opx]!=-1) {
            urt=frt[pb[opr]][opx]=-1;
            for (int i=pb[opr]*qb;pb[i]==pb[opr];++i) a[i]=a[find_fat(i)];
            for (int i=pb[opr]*qb;pb[i]==pb[opr];++i) {
                if (a[i]==opx) {
                    if (i<=opr) {
                        urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
                        --cbk[pb[opr]][pa[opx]]; --cnm[pb[opr]][opx];
                        ++cbk[pb[opr]][pa[opy]]; ++cnm[pb[opr]][opy];
                    }
                    else {
                        if (frt[pb[opr]][opx]!=-1) fat[i]=frt[pb[opr]][opx];
                        else frt[pb[opr]][opx]=fat[i]=i;
                    }
                }
                else if (a[i]==opy)
                    urt!=-1?(fat[i]=urt):(urt=fat[i]=i);
            }
            a[frt[pb[opr]][opy]=urt]=opy;
        }
        for (int i=pb[opl]+1;i<pb[opr];++i) if (frt[i][opx]!=-1) {
            if (frt[i][opx]<frt[i][opy]||frt[i][opy]==-1) {
                a[fat[frt[i][opy]]=frt[i][opx]]=opy;
                frt[i][opy]=frt[i][opx];
            }
            else fat[frt[i][opx]]=frt[i][opy];
            cbk[i][pa[opy]]+=cnm[i][opx]; cbk[i][pa[opx]]-=cnm[i][opx];
            cnm[i][opy]+=cnm[i][opx]; cnm[i][opx]=0;
            frt[i][opx]=-1;
        }
    }
    sbk[0][pa[opx]]=cbk[0][pa[opx]]; snm[0][opx]=cnm[0][opx];
    sbk[0][pa[opy]]=cbk[0][pa[opy]]; snm[0][opy]=cnm[0][opy];
    for (int i=1;i<qc;++i) {
        sbk[i][pa[opx]]=sbk[i-1][pa[opx]]+cbk[i][pa[opx]];
        snm[i][opx]=snm[i-1][opx]+cnm[i][opx];
        sbk[i][pa[opy]]=sbk[i-1][pa[opy]]+cbk[i][pa[opy]];
        snm[i][opy]=snm[i-1][opy]+cnm[i][opy];
    }
}

inline int find_kth(int opl,int opr,int opk) {
    static int fbk[318],fnm[100505]; int sum=0,ret=-1;
    if (pb[opl]==pb[opr]) {
        for (int i=opl;i<=opr;++i) {
            ++fbk[pa[a[find_fat(i)]]];
            ++fnm[a[find_fat(i)]];
        }
        for (int i=0;i<qa;++i)
            if ((sum+=fbk[i])>=opk) {
                for (int j=(i+1)*qa-1;;--j)
                    if ((sum-=fnm[j])<opk) {
                        ret=j; break;
                    }
                break;
            }
        for (int i=opl;i<=opr;++i) {
            --fbk[pa[a[find_fat(i)]]];
            --fnm[a[find_fat(i)]];
        }
        return ret;
    }
    for (int i=opl;pb[i]==pb[opl];++i) {
        ++fbk[pa[a[find_fat(i)]]];
        ++fnm[a[find_fat(i)]];
    }
    for (int i=opr;pb[i]==pb[opr];--i) {
        ++fbk[pa[a[find_fat(i)]]];
        ++fnm[a[find_fat(i)]];
    }
    for (int i=0;i<qa;++i)
        if ((sum+=sbk[pb[opr]-1][i]-sbk[pb[opl]][i]+fbk[i])>=opk) {
            for (int j=(i+1)*qa-1;;--j)
                if ((sum-=snm[pb[opr]-1][j]-snm[pb[opl]][j]+fnm[j])<opk) {
                    ret=j; break;
                }
            break;
        }
    for (int i=opl;pb[i]==pb[opl];++i) {
        --fbk[pa[a[find_fat(i)]]];
        --fnm[a[find_fat(i)]];
    }
    for (int i=opr;pb[i]==pb[opr];--i) {
        --fbk[pa[a[find_fat(i)]]];
        --fnm[a[find_fat(i)]];
    }
    return ret;
}

int main() {
    int m,opt,opl,opr,opx,opy,opk;
    n=read(); m=read();
    memset(frt,0xff,sizeof(frt));
    for (int i=0;i<100001;++i) {
        pa[i]=i/qa; pb[i]=i/qb;
    }
    for (int i=0;i<n;++i) {
        a[i]=read(); ++cbk[pb[i]][pa[a[i]]]; ++cnm[pb[i]][a[i]];
        fat[i]=frt[pb[i]][a[i]]!=-1?frt[pb[i]][a[i]]:(frt[pb[i]][a[i]]=i);
    }
    for (int i=0;i<qa;++i) sbk[0][i]=cbk[0][i];
    for (int i=0;i<100001;++i) snm[0][i]=cnm[0][i];
    for (int i=1;i<qc;++i) {
        for (int j=0;j<qa;++j) sbk[i][j]=sbk[i-1][j]+cbk[i][j];
        for (int j=0;j<100001;++j) snm[i][j]=snm[i-1][j]+cnm[i][j];
    }
    while (m--) {
        opt=read(); opl=read()-1; opr=read()-1;
        if (opt==1) {
            opx=read(); opy=read();
            update(opl,opr,opx,opy);
        }
        else {
            opk=read();
            printf("%d\n",find_kth(opl,opr,opk));
        }
    }
    return 0;
}

owo

蛤mo-ha
Powered by Typecho
Theme Katerial