[ARC141D] Non-divisible Set 题解

题目链接

点击打开链接

题目解法

很思维的题，需要用好所有的特殊性质

暴力的做法是建出图，然后求包含点 \(i\) 的最长反链，但这明显过不了

上面的做法没用到 \(a_i<2m\) 的性质
如何用？把 \(a_i\) 拆分成 \(q\times 2^k\;(k\) 为奇数\()\) 的形式，那么对于同一个 \(q\)，只能在其中选一个数，可以发现 \(q\) 为 \(1-2m\) 中的所有奇数，所以一共有 \(m\) 个不同的 \(q\)
题目需要求大小 \(m\) 的子集，所以每一个 \(q\in[1,2m],q\in odd\) 中都需要选恰好一个

考虑一个比较显然的缩小范围
若 \(q_1|q_2\)，则有 \(L_{q_1}>L_{q_2},\;R_{q_2}<R_{q_1}\)
这样可以在 \(O(n\ln n)\) 的时间内缩放 \(L_i\) 和 \(R_i\) 的范围
注意一定要使 \(L_i,R_i\) 都有数

然后就只需要判断当前数是否在合法区间内即可
为什么？考虑构造 \(R_1,R_3,...,R_{k_i-2},i,L_{k_i+2},...,L_{2m-1}\) 一定是一个合法的子集

时间复杂度 \(O(n\ln n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=600100;
int n,m,L[N],R[N],a[N],k[N];
vector<int> nums[N];
void End(){ F(i,1,n) puts("No");exit(0);}
int main(){
    n=read(),m=read();
    F(i,1,n){
        a[i]=read();
        while(~a[i]&1) k[i]++,a[i]>>=1;
        a[i]=a[i]/2+1,nums[a[i]].pb(k[i]);assert(1<=a[i]&&a[i]<=m);
    }
    F(i,1,m) if(nums[i].empty()) End();
    F(i,1,m) sort(nums[i].begin(),nums[i].end(),greater<int>());
    DF(i,m,1){
        int v=2*i-1;
        for(int j=3*v;j<=m<<1;j+=v<<1){
            int k=j/2+1;
            while(!nums[i].empty()&&nums[i].back()<=nums[k].back()) nums[i].pop_back();
        }
        if(nums[i].empty()) End();
    }
    F(i,1,m) L[i]=nums[i].back();
    F(i,1,m) nums[i].clear();
    F(i,1,n) nums[a[i]].pb(k[i]);
    F(i,1,m) sort(nums[i].begin(),nums[i].end());
    F(i,1,m){
        if(nums[i].empty()) End();
        int v=2*i-1;
        for(int j=3*v;j<=m<<1;j+=v<<1){
            int k=j/2+1;
            while(!nums[k].empty()&&nums[k].back()>=nums[i].back()) nums[k].pop_back();
        }
    }
    F(i,1,m) R[i]=nums[i].back();
    F(i,1,m) if(L[i]>R[i]) End();
    F(i,1,n){
        if(L[a[i]]<=k[i]&&k[i]<=R[a[i]]) puts("Yes");
        else puts("No");
    }
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}