[bzoj 4810] [Ynoi2017]由乃的玉米田

一个长度为n的自然数序列, m个询问: 某区间是否存在两数 (可以在同一位置), 它们的差/和/积等于x? (序列中的数,x,n,m≤10^5, x≥2) 我: 我发现一道有趣的题, 叫由乃的玉米田. 某同学: 牛奶的玉米田?

积可以这样处理: 因数分解, 判断区间是否存在这两个因数. 这启发我们跑个莫队算法.

我想实时维护存在哪些和, 差. 此路不通......至少我不会搞.

a[i] - a[j] = x <=> a[i] = a[j] + x
a[i] + a[j] = x <=> a[i] = x - a[j] <=> a[i] = (x - N) + (N - a[j])

把x考虑进去就好搞多了. 两个bitset, 分别维护当前区间是否存在 a[i] = k, N - a[i] = k. 查询简化为左/右移, 跟原来的自己取交.

时间复杂度: .

const int N = 1e5;

bitset<N + 1> u, v;
int a[N], blk[N], cnt[N+1];
bool ans[N];

struct Query {
	int l, r, op, x, k;
	bool operator<(const Query& o) const
	{
		return blk[l] < blk[o.l] || (blk[l] == blk[o.l] && r < o.r);
	}
} Q[N];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	rep (i, 0, n) scanf("%d", a+i);
	int sz = 1;
	while (sz*sz < n) ++sz;
	int j = 0;
	rep (i, 0, sz) {
		for (int k = min(j+sz, n); j < k; ++j)
			blk[j] = i;
	}
	rep (i, 0, m) {
		scanf("%d%d%d%d", &Q[i].op, &Q[i].l, &Q[i].r, &Q[i].x);
		--Q[i].l;
		--Q[i].r;
		Q[i].k = i;
	}
	sort(Q, Q+m);

	int l = Q[0].l, r = l-1;
	rep (i, 0, m) {
		const Query& q = Q[i];
		while (r < q.r)
			if (!cnt[a[++r]]++)
				u[a[r]] = v[N-a[r]] = 1;
		while (l > q.l)
			if (!cnt[a[--l]]++)
				u[a[l]] = v[N-a[l]] = 1;
		while (r > q.r)
			if (!--cnt[a[r--]])
				u[a[r+1]] = v[N-a[r+1]] = 0;
		while (l < q.l)
			if (!--cnt[a[l++]])
				u[a[l-1]] = v[N-a[l-1]] = 0;
		switch (Q[i].op) {
		case 1:
			ans[q.k] = (u & (u << q.x)).any();
			break;
		case 2:
			ans[q.k] = (u & (q.x > N ? v << (q.x - N) : v >> (N - q.x))).any();
			break;
		default:
			for (j = 1; j*j <= q.x; ++j)
				if (q.x % j == 0 && cnt[j] && cnt[q.x/j]) {
					ans[q.k] = true;
					break;
				}
		}
	}

	rep (i, 0, m)
		puts(ans[i] ? "yuno" : "yumi");

	return 0;
}