题解：P12410 「知りたくなかった、失うのなら」

yzq_yzq · 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;
}