这个题不是网络流。
problem
我们说一个集合 \(D\) 是一个好的集合，当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。
给定 \(N\) 个整数的一个集合 \(S\)，值域均落在 \([1, 2*M]\) 内。
对 \(S\) 中的每个元素 \(A_i\) 询问：是否存在一个恰好包含 \(A_i\) 的 \(M\) 个元素的好的集合。
- \(M \leq N \leq 2M\)
- \(1 \leq M \leq 3 \times 10^5\)
- \(1 \leq A_1 < A_2 < \dots < A_N \leq 2M\)
- All values in input are integers.
solution
考虑将数字 \(x\) 表示为 \(2^k\cdot y\) 其中 \(y\) 是一个奇数，那么最终选出的好的集合中每个 \(y\) 唯一对应一个 \(k\) 且每个 \(y\) 都要有对应。考虑预处理每个 \(y\) 对应的可能的 \(k\)。
考虑对于两个奇数 \(a,b\)，满足 \(a|b\)，则 \(a\) 选出来的 \(k_a\) 必须大于 \(b\) 选出来的 \(k_b\)。考虑到 \(a|b\) 这样的关系，类似于一个 DAG，我们可以在 DAG 上 DP，获得一组合法方案，所以我们考虑能不能把 DP 去掉？我们考虑到：对于 \(a|b\)，如果已经确定 \(k_b\)，那么 \(k_a>k_b\)，也就是说若 \(\{k_b\}\) 确定，则 \(\min k_a > \min k_b\)，删除很小的 \(k_a\) 以达到这一点，将这些不可能符合条件的 \(k_a\) 踢掉。同理反过来，如果 \(k_a\) 确定，那么必须要 \(\max k_a > \max k_b\)，通过删除很大的 \(k_b\) 达到这一点，将这些不可能符合条件的 \(k_b\) 删掉。如此一来，无论我们钦定哪一个 \(k_y\)，我们的前面都能符合条件，后面都能符合条件，那么总的就能符合条件。
\(O(n\ln n)\)
code
点击查看代码
#include <functional>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n, m, a[600010];
vector<int> b[600010];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
int x = a[i], k = 0;
while (x % 2 == 0) x >>= 1, k++;
b[x].push_back(k);
}
for (int x = m * 2 - 1; x >= 1; x -= 2) {
// debug("x = %d, b[%d] = {", x, x);
// for (int i: b[x]) debug("%d,", i);
// debug("}\n");
sort(b[x].begin(), b[x].end(), greater<int>());
for (int y = x * 2; y <= m << 1; y += x)
while (!b[x].empty() && !b[y].empty()
&& b[x].back() <= b[y].back())
b[x].pop_back();
}
// debug("========================\n");
for (int x = 1; x <= m << 1; x += 2)
reverse(b[x].begin(), b[x].end());
for (int x = 1; x <= m << 1; x += 2){
for (int y = x * 2; y <= m << 1; y += x)
while (!b[x].empty() && !b[y].empty()
&& b[x].back() <= b[y].back())
b[y].pop_back();
// debug("x = %d, b[%d] = {", x, x);
// for (int i: b[x]) debug("%d,", i);
// debug("}\n");
}
bool flg = 0;
for (int x = 1; x <= m << 1; x += 2)
flg |= b[x].empty();
for (int i = 1; i <= n; i++) {
int x = a[i], k = 0;
while (x % 2 == 0) x >>= 1, k++;
auto it = lower_bound(b[x].begin(), b[x].end(), k);
puts(flg || it == b[x].end() || *it != k ? "No" : "Yes");
}
return 0;
}