【AtCoder Regular 141D】Non-divisible Set 题解

题目大意

  给定长度为 $n$ 的序列 $a_1,\cdots,a_n$ 和一个参数 $m$，对于每个 $i$，问是否能从序列中选出满足如下条件的子集：

• 集合包含 $a_i$；
• 集合大小为 $m$；
• 集合内不存在一个数是另一个数的倍数。

  $m \le 3 \cdot 10^5,\ m \le n \le 2m$
  $1 \le a_1 < a_2 < \cdots < a_n \le 2m$
  2s

题解

  如果建出一个“倍数关系图”，那么每次询问就是去掉一个点之后求最大独立集，这就很不可做，所以这个倍数关系一定是要利用的。
  子集大小为 $m$ 而每个数最多只有 $2m$，看着就有玄机，只是没想到竟然是这样用的。。。

  每个 $a_i$ 可以表示成 $2^c \cdot d$，其中 $d$ 为奇数。按照 $d=1,3,\cdots,2m-1$ 把所有的 $a_i$ 分门别类放好，这样总共有 $m$ 个类，且每个类最多只能选 1 个数，又因为最后要选 $m$ 个数，因此每个类恰好选一个数。
  考虑如果选了 $2^{c_1}d_1$ 和 $2^{c_2}d_2$，如果 $d_1 | d_2$，那么必须有 $c_1 > c_2$。因此直观来看，$d$ 较小的类 $c$ 应该较大，$d$ 较大的类 $c$ 应该较小。因此可以用 $O(m \log m)$ 的时间从左到右、从右到左分别求出每个类的 $c$ 的上限和下限，那么只要夹在上限和下限之间的数都一定是可行的（比它小的类全部选上限、比它大的类全部选下限即可）。

  虽然它真的很巧妙，不过似乎只能用于判断 $m$ 为“$d$ 的种类数”是否可行。能用于判断比这更小的 $m$ 是否可行吗？

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=6e5+5, maxm=6e5+5;

int n,m;
vector<pair<int,int>> V[maxm];

void Invalid() {
	fo(i,1,n) puts("No");
	exit(0);
}

int L[maxm],R[maxm],lim[maxm];
bool ans[maxn];
int main() {
	scanf("%d %d",&n,&m);
	fo(i,1,n) {
		int a;
		scanf("%d",&a);
		int er=0;
		while (!(a&1)) a>>=1, er++;
		V[a].push_back(make_pair(er,i));
	}
	
	for(int i=1; i<2*m; i+=2) if (V[i].empty()) Invalid();
	
	memset(lim,127,sizeof(lim));
	for(int i=1; i<2*m; i+=2) {
		if (lim[i]<=(V[i].begin())->first) Invalid();
		R[i]=(lower_bound(V[i].begin(),V[i].end(),make_pair(lim[i],0))-1)->first;
		for(int j=i*3; j<2*m; j+=i+i) lim[j]=min(lim[j],R[i]);
	}
	for(int i=2*m-1; i>0; i-=2) {
		int lim=-1;
		for(int j=i*3; j<2*m; j+=i+i) lim=max(lim,L[j]);
		if (lim>=(V[i].rbegin())->first) Invalid();
		L[i]=upper_bound(V[i].begin(),V[i].end(),make_pair(lim,n+1))->first;
	}
	
	for(int i=1; i<2*m; i+=2)
		for(auto p:V[i]) ans[p.second]=(L[i]<=p.first && p.first<=R[i]);
	
	fo(i,1,n) puts(ans[i] ?"Yes" :"No");
}