P9323 [EGOI2022] Toy Design / 玩具设计 题解

· · 题解

题目实际上是要求图的连通块情况。

不妨设 fa_i 为 与 i 联通的点的最小编号，那么题目就能转化为求 fa_i。

于是有两种情况：

1.fa_i=i，即 i 与 1 \sim i-1 的点均不连通，是一个新加入的连通块。

2.fa_i < i。

先考虑如何判断第一种情况。

设 rt_i 表示满足前 i 个点联通的礼物编号，那么只要满足 rt_{i-1} \ne rt_i = Connected(rt_{i-1},i-1,i) 即可。

而对于第二种情况，可以二分查找 fa_i，通过查询 Connected(rt_{mid},mid,i) 是否为 rt_{mid} 来判断。

设连通块个数为s，则询问次数为 \mathcal{O}((n-s) \log n)。

但是这样可以被特定的数据卡掉。

优化：

显然，如果 Connected(rt_x,x,i)=rt_x，那么 Connected(rt_{fa_x},fa_x,i)=rt_{fa_x}，而 fa_x \le x。

因此如果 x 满足条件，fa_x 必定也满足条件。

于是我们只要二分 fa_i=i 的点就好了。

询问次数 \mathcal{O}((n-s) \log s)。

优化效果：构造 n=m=200 的数据，不加优化询问次数 1390。

优化之后询问次数 570。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int rt[N],fa[N],cnt,las;
int a[N],top;
vector<pair<int,int> > ans;
int Connected(int a, int i, int j);
void DescribeDesign(std::vector<std::pair<int, int>> result);
void ToyDesign(int n,int max_ops){
    fa[1]=1;rt[1]=0;a[top=1]=1;
    for(int i=2;i<=n;++i){
        rt[i]=Connected(rt[i-1],i-1,i);cnt++;
        if(rt[i]!=rt[i-1]){
            fa[i]=i;
            a[++top]=i;
            continue;
        }
        int l=1,r=top,res=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(a[mid]==i-1) {r=mid-1;continue;} 
            cnt++;
            if(Connected(rt[a[mid]],a[mid],i)==rt[a[mid]]) r=mid-1;
            else l=mid+1,res=mid;
        }
        fa[i]=a[res+1];
    }
    for(int i=1;i<=n;++i) if(fa[i]!=i) ans.push_back(make_pair(fa[i],i));
    DescribeDesign(ans);
    return;
}