P5397 [Ynoi2018] 天降之物题解

401rk8 · 2022-02-07 08:51:26 · 题解

题面

做法仍是根号分治，相比其他题解避免了冗余的分类讨论，使得思路和代码都简洁许多

记一个数 x 的出现次数为 siz[x]

使用数组 mp 建立真实数值与代码中数值的映射（值 x 在代码中应为 mp[x]），这允许我们在操作 1 中令 siz[x]\le siz[y]（若不然，swap(mp[x],mp[y]) 即可等价于将 y 变成 x）

设定阈值 B，把每个数出现的位置分为两部分：主要集合 S 和附属集合 P，其中 |S|>B,|P|\le B。称 S\ne\varnothing 的数为大数，否则为小数

容易发现大数只有 \frac{n}{B} 个，可以使用二维数组 ans 保存每个大数只考虑 S 集对其他数的答案，这部分时空复杂度为 O(\frac{n^{2}}{B})。再使用 vector 保存每个数的 P 集

修改时先更新每个大数对 y 的答案，然后合并 P 集，分两类讨论：

x$ 为大数：$O(n)$ 修改所有 $x$ 为 $y$，重构 $y$。这种情况不会出现超过大数个数次，复杂度为 $O(\frac{n^{2}}{B})
x$ 为小数：通过 $P$ 修改所有 $x$ 为 $y$，若 $|P_{y}|>B$ 则重构 $y$。复杂度为 $O(nB)

询问时先考虑 P_{x},P_{y} 中位置的答案，若 x,y 中有大数再用 ans 更新答案

由于常数影响，B 应略大于 \sqrt{n}，时空复杂度 O(n\sqrt{n})

并不卡常因此偷懒用了 std::merge

const int N = 1e5+5, B = 500, BN = N/B+5;
int n,m,ind,lstans,a[N],mp[N],id[N],ans[BN][N];
VI p[N];

void build(int x) { // calculate ans, clear p[x]
    if( !id[x] ) id[x] = ++ind; int u = id[x];
    // the value is x, the index of x is u
    memset(ans[u],0x3f,sizeof ans[u]), ans[u][x] = 0;
    For(i,1,n, len = N)
        if( a[i] == x ) len = 0;
        else ckmin(ans[u][a[i]],++len);
    rFor(i,n,1, len = N)
        if( a[i] == x ) len = 0;
        else ckmin(ans[u][a[i]],++len);
    VI().swap(p[x]);
}

void merge(VI &res,const VI &a,const VI &b) {
    VI c; c.resize(sz(a)+sz(b)); merge(all(a),all(b),c.begin());
    res = c;
}
void mdf(int &x,int &y) {
    if( x == y || !x ) return;
    if( !y ) return y = x, x = 0, void();
    if( id[x] ) swap(x,y);
    For(i,1,ind) ckmin(ans[i][y],ans[i][x]);
    if( id[x] ) { // x is a big number
        For(i,1,n) if( a[i] == x ) a[i] = y;
        build(y);
    } else {
        for(int i : p[x]) a[i] = y;
        merge(p[y],p[x],p[y]);
        if( sz(p[y]) > B ) build(y);
    }
    VI().swap(p[x]), x = 0;
}

int qry(const int &x,const int &y) {
    if( !x || !y ) return -1; if( x == y ) return 0;
    int res = N;
    VI pp; merge(pp,p[x],p[y]);
    Rep(i,1,sz(pp)) if( a[pp[i]] != a[pp[i-1]] ) ckmin(res, pp[i]-pp[i-1]);
    // better method: www.luogu.com.cn/blog/123384/solution-p5397
    // in function `merge_(int,int)`
    if( id[x] ) ckmin(res,ans[id[x]][y]);
    if( id[y] ) ckmin(res,ans[id[y]][x]);
    return res;
}

signed main() {
    read(n,m); For(i,1,n) read(a[i]), mp[a[i]] = a[i], p[a[i]].pb(i);
    For(i,1,n) if( sz(p[i]) > B ) build(i);
    while( m-- ) {
        int op,x,y; read(op,x,y); x^=lstans,y^=lstans;
        if( op == 1 ) mdf(mp[x],mp[y]);
        else {
            lstans = qry(mp[x],mp[y]);
            if( ~lstans ) write(lstans); else lstans = 0, put("Ikaros");
        }
    }
    return ocl();
}

P5397 [Ynoi2018] 天降之物 题解

P5397 [Ynoi2018] 天降之物题解