自动搬运

查看原文

来自洛谷，原作者为

	yzq_yzq 色づく世界の明日から | END?

搬运于2025-08-24 23:15:21，当前版本为作者最后更新于2025-05-04 15:07:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一眼经典根号分治题，但是懒得写。

发现这东西数据包不好造的，于是考虑暴力。

注意到判断一个区间是否存在一个数 $x$ 这个东西是简单的，用 vector 存相同数的位置然后二分就行。

然后用这个东西直接暴力，搜到答案就停下就有 50pts 了。

最后一步，限制一下枚举次数，限制到大概 $200$ 次就行了，但是这样 Wa 了一个点，想下出题人怎么卡你，肯定是用 $a$ 很小的点，并且肯定值上有很多连续的东西，于是直接从小到大枚和从大到小两个方向各枚举 $200$ 次，因为大部分答案都是 NO，直接就过了。

后边出题人赛后卡时间，然后试了下发现两个方向各枚举 $30$ 次就过了，最大点不到 300ms。

代码很简单。

#include <bits/stdc++.h>
#define ll long long
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)
#define drep(i, x, y) for (int i = (x); i >= (y); --i)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define mem(a, b) memset((a), b, sizeof(a))
#define ALL(a) (a).begin(), (a).end()
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
template <typename T> inline void cmin(T &x, T y) { if(x > y) x = y; }
template <typename T> inline void cmax(T &x, T y) { if(x < y) x = y; }

const int N = 500050;
int n, m, c[N];
vector<int> vec[N];
inline int rd() {
	static char c; static int x;
	x = 0, c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}
int main() {
	n = rd(), m = rd();
	rep(i, 1, n) c[i] = rd(), vec[c[i]].pb(i);
	while(m--) {
		int l = rd(), r = rd(), x = rd(), y = rd(), a = rd(), b = rd();
		int d = (x - b + a - 1) / a * a + b, e = (y - b) / a * a + b;
		if(d > y) puts("YES");
		else {
			bool f = 1;
			for(int i = 30; d <= y && i; d += a, --i) {
				if(!vec[d].size()) { f = 0; break; }
				auto p = lower_bound(ALL(vec[d]), l);
				if(p == vec[d].end() || *p > r) { f = 0; break; }
			}
			for(int i = 30; e >= x && i; e -= a, --i) {
				if(!vec[e].size()) { f = 0; break; }
				auto p = lower_bound(ALL(vec[e]), l);
				if(p == vec[e].end() || *p > r) { f = 0; break; }
			}
			if(f) puts("YES"); else puts("NO");
		}
	}
	return 0;
}