bzoj4810 [Ynoi2017]由乃的玉米田 莫队+bitset(+数论)

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4810

题解

看数据范围和题目名字应该是根号算法。

因为询问除了区间外，还有第 (3) 个参数，所以不太可能是分块。

所以考虑莫队离线维护。

根据经验，差为某值的数对的存在性可以用 bitset 移位判断。用 bitset 维护当前区间内每一个数是否出现，那么减法就可以转化为 (s & (s << x))) 是否为空判断。

加法的话可以把 bitset 翻转以后类似减法判断。

乘法的话，因为乘积 (leq c)，所以可以 (sqrt c) 枚举每一个因数判断。

---

总的时间复杂度为 (O(m(sqrt n + frac c{64})))。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

const int N = 100000 + 7;
const int M = 100000;

#define bl(x) (((x) - 1) / blo + 1)

int n, m, blo;
int a[N], ans[N], cnt[N];
std::bitset<N> s, t;

struct Query {
	int opt, l, r, x, *ans;
	inline bool operator < (const Query &b) const { return bl(l) != bl(b.l) ? l < b.l : r < b.r; }
} q[N];

inline void madd(int x) {
	++cnt[a[x]];
	if (cnt[a[x]] == 1) s.set(a[x]), t.set(M - a[x]);
}
inline void mdel(int x) {
	--cnt[a[x]];
	if (!cnt[a[x]]) s.reset(a[x]), t.reset(M - a[x]);
}

inline void work() {
	std::sort(q + 1, q + m + 1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; ++i) {
		while (l > q[i].l) madd(--l);
		while (r < q[i].r) madd(++r);
		while (l < q[i].l) mdel(l++);
		while (r > q[i].r) mdel(r--);
		if (q[i].opt == 1) *q[i].ans = (s & (s << q[i].x)).any();
		else if (q[i].opt == 2) *q[i].ans = (t & (s << (M - q[i].x))).any();
		else {
			int x = q[i].x;
			for (int j = 1, p = sqrt(x); j <= p; ++j)
				if (x % j == 0 && s[j] && s[x / j]) { *q[i].ans = 1; break; }
		}
	}
	for (int i = 1; i <= m; ++i) if (ans[i]) puts("yuno"); else puts("yumi");
}

inline void init() {
	read(n), read(m), blo = sqrt(n);
	for (int i = 1; i <= n; ++i) read(a[i]);
	for (int i = 1; i <= m; ++i) read(q[i].opt), read(q[i].l), read(q[i].r), read(q[i].x), q[i].ans = ans + i;
}

int main() {
#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
#endif
	init();
	work();
	fclose(stdin), fclose(stdout);
	return 0;
}