CF1777C题解

• 分析

  看到题面里面的子序列觉得很恶心，如果是子段感觉就会比较好做。
  如果直接填上子序列中间的空隙就可能会取一些比必须要取的数更大或者更小的数，影响我们的答案。
  那么就可以直接排序，使得子序列中间的空隙的数必然 \(\geq\) 左端且 \(\leq\) 右端，不会影响我们的答案（因为极差只看最大最小值）。

  那么问题就变成了选取子段 \([L,R]\) 满足 \(\{x|x\in[1,m]\}\in \{x|(x|a_i, i\in[L,R])\}\)。
  由于一个子段的子段的答案肯定不劣于原子段，考虑two-pointers。
  思路跟NOI2016区间一样，先向右找到合法的右端点 \(r\)，然后选取最大的合法左端点 \(l\)。
  对于每个新选择的右端点的答案肯定劣于原来的，所以要右移左端点保证不劣。

  然后用线段树维护区间的最大最小值计算答案。

  寻找合法区间的过程与HH的项链莫队做法大致相同，开一个桶数组，如果要加一个原本桶里面是0的因数就给记录因数个数的变量 \(cnt\) 加一，如果减了一个因数使这个因数的桶里面是0就给\(cnt\)减一。

• 代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int MAXN(1000007);
constexpr int INF(0x3f3f3f3f);
int minn[MAXN], maxn[MAXN], a[MAXN], tot[MAXN];
int T, n, m, cnt;
inline void load(int x) {
	for (int i(1); i * i <= x; ++i) {
		if (i * i == x && i <= m)  cnt += (tot[i] == 0), ++tot[i];
		else if (x % i == 0) {
			if (i <= m)  cnt += (tot[i] == 0), ++tot[i];
			if (x / i <= m)  cnt += (tot[x / i] == 0), ++tot[x / i];
		}
	}
}
inline void unload(int x) {
	for (int i(1); i * i <= x; ++i) {
		if (i * i == x && i <= m)  --tot[i], cnt -= (tot[i] == 0);
		else if (x % i == 0) {
			if (i <= m)  --tot[i], cnt -= (tot[i] == 0);
			if (x / i <= m)  --tot[x / i], cnt -= (tot[x / i] == 0);
		}
	}
}
struct SGT{
	#define ls (p << 1)
	#define rs (p << 1 | 1)
	#define mid ((l + r) >> 1)
	inline void pushup(int p) { minn[p] = min(minn[ls], minn[rs]), maxn[p] = max(maxn[ls], maxn[rs]); }
	void build(int p, int l, int r) {
		if (l == r)  return minn[p] = a[l], maxn[p] = a[l], void();
		build(ls, l, mid), build(rs, mid + 1, r);
		pushup(p);
	}
	int qmax(int p, int l, int r, int s, int t) {
		if (s <= l && t >= r)  return maxn[p];
		int res(0);
		if (s <= mid)  res = max(res, qmax(ls, l, mid, s, t));
		if (t > mid)  res = max(res, qmax(rs, mid + 1, r, s, t));
		return res;
	}
	int qmin(int p, int l, int r, int s, int t) {
		if (s <= l && t >= r)  return minn[p];
		int res(INF);
		if (s <= mid)  res = min(res, qmin(ls, l, mid, s, t));
		if (t > mid)  res = min(res, qmin(rs, mid + 1, r, s, t));
		return res;
	}
	#undef ls
	#undef rs
	#undef mid
}Miku;
inline void read(int &temp) { cin >> temp; }
inline void work() {
	int ans(INF), l(1), r(0);
	memset(tot, 0, sizeof(tot));
	cnt = 0;
	read(n), read(m);
	for (int i(1); i <= n; ++i)  read(a[i]);
	sort(a + 1, a + n + 1);
	Miku.build(1, 1, n);
	while (1) {
		while (cnt < m && r <= n)  ++r, load(a[r]);
		if (r > n)  break;
		while (cnt == m && l <= r)  unload(a[l]), ++l;
		ans = min(ans, Miku.qmax(1, 1, n, l - 1, r) - Miku.qmin(1, 1, n, l - 1, r));
	}
	if (ans == INF)  return cout << "-1" << endl, void();
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	read(T);
	while (T--)  work();
	return 0;
}