CF103102H AND = OR

题意：给定一个长度为 $n$ 的序列，$q$ 次给出 $l, r$，问 $[l, r]$ 区间能否拆成两个集合使得第一个集合的 OR 是第二个集合的 AND。$n, q\leq 10 ^ 5$，$0\leq a_i < 2 ^ {30}$，3s，1GB。

首先考虑一个结论：

如果合法，假设两个集合 OR/AND 的值 $mid$ 满足 $|mid| = x$，则一定存在一种方案，使得 $|v| < x$ 的所有 $v$（$|v|$ 表示 $v$ 中 1 的个数）都放在 OR 里面，$|v| > x$ 的所有 $v$ 都放在 AND 里面。

证明：容易发现如果 $|v| > x$ 的放在 OR 里面，那么 OR 的结果一定 满足 $|v| > x$，就不可能合法。$|v| < x$ 放在 AND 同理。

那么对于每次询问，考虑枚举 $x$，那么按照该方式，所有 $|v|< x$ 的都放在 OR 里面。求出这些所有的 OR 可以把每个数按照 $|v|$ 放入对应的线段树，然后查一下前缀即可。AND 同理。

最后注意一下细节即可。一个可能的合法方案是枚举 $x$，$|v| < x$ 的 OR 和 $|v| \geq x$ 的 AND 相同。另外一种方案是 $|v|\leq x$ 的 OR 和 $|v|\geq x$ 的 AND 相同，并且 $|v| = x$ 的个数不少于两个。容易发现如果满足前面的条件，所有满足 $|v| = x$ 的 $v$ 都相同。于是上面这个是对的。

用线段树维护一下即可。时间复杂度 $O(n\log ^ 2n + q\log ^ 2 n)$，空间复杂度 $O(n\log n)$，可以通过。

int query(int l, int r)
{
	static int le[31], ri[31], prehav[31], sufhav[31], hav[31];
	le[0] = orseg[0].query(l, r), prehav[0] = havseg[0].query(l, r);
	ri[30] = andseg[30].query(l, r), sufhav[30] = havseg[30].query(l, r);
	for (int i = 1; i <= 30; ++ i)
		le[i] = le[i - 1] | orseg[i].query(l, r), prehav[i] = prehav[i - 1] | (hav[i] = havseg[i].query(l, r));
	for (int i = 29; ~i; -- i)
		ri[i] = ri[i + 1] & andseg[i].query(l, r), sufhav[i] = sufhav[i + 1] | hav[i];
	for (int i = 0; i <= 30; ++ i)
	{
		if (i && prehav[i - 1] && sufhav[i] && le[i - 1] == ri[i]) return true;
		auto iter = std::lower_bound(app[i].begin(), app[i].end(), l);
		if (iter == app[i].end() || *iter > r || nxt[i][iter - app[i].begin()] <= r) continue;
		int ccnt = std::upper_bound(app[i].begin(), app[i].end(), r) - iter;
		if (le[i] == ri[i] && ccnt >= 2) return true;
	}
	return false;
}

int main()
{
	std::cerr << std::abs(&mem1 - &mem2) / 1048576. << " MB\n";
	int q, l = 2, r = n - 1;
	std::cin >> n >> q;
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= n; ++ i) app[__builtin_popcount(a[i])].push_back(i);
	for (int i = 0; i <= 30; ++ i) {
		nxt[i].resize(app[i].size());
		if (!app[i].size()) continue;
		nxt[i].back() = n + 1;
		for (int j = app[i].size() - 2; ~j; -- j)
			if (a[app[i][j]] != a[app[i][j + 1]]) nxt[i][j] = app[i][j + 1];
			else nxt[i][j] = nxt[i][j + 1];
	}
	for (int i = 0; i <= 30; ++ i) orseg[i].build(n), andseg[i].build(n), havseg[i].build(n);
	for (int i = 0; i <= 30; ++ i)
		for (int &x : app[i]) orseg[i].modify(x, a[x]), andseg[i].modify(x, a[x]), havseg[i].modify(x, 1);
	
	while (q --)
	{
		scanf("%d %d", &l, &r);
		puts(query(l, r) ? "YES" : "NO");
	}
	return 0;
}