题解 P5355 【[Ynoi2017]由乃的玉米田】

· · 题解

一句话题意

给一个长度为n序列a，每次询问给定l, r, x，问区间[l, r]内是否能找出两个数，它们的差/和/积/商为x。n、询问次数、值域均不超过10 ^ 5。

解法

首先，看到[Ynoi]，并且没有强制在线，那么我们可以直接考虑离线算法。

弱化版：=>传送门

莫队，同时维护两个大小为值域的bitset，暂且叫它们bs1和bs2。如果x在当前区间出现，令bs1[i]、bs2[100000 - i]都=1。

对于减法操作，答案是((bs1 << x) & bs1).any()

对于加法操作，答案是ans[qs[i].i] = ((bs1 << (100000 - x)) & bs2).any()

对于乘法操作，可以直接暴力，令i从1遍历到\lfloor \sqrt {x} \rfloor，查询是否i和\frac{x}{i}同时存在，注意x必须被i整除。

前三种操作在P3674的各路大佬的题解中有详细的复杂度证明，这里就不证了，讲一下第四种操作。

值域N = 10 ^ 5，那么我们可以把\sqrt N作为阈值，按x大小把第四类询问分成两类，设计两种算法。

对于x \geq \sqrt N的询问，我们可以直接枚举i，令i从1遍历到\lfloor \frac{N}{x} \rfloor，查询是否i和ix是否同时存在。由于x不低于\sqrt N，所以\lfloor \frac{N}{x} \rfloor不超过\sqrt N。那么，在莫队处理好区间信息后，这次查询的复杂度是\Theta (\sqrt N)。

对于x < \sqrt N的询问，我们单独处理，不使用莫队。

枚举x。对于每一个x，我们\Theta (n)令p从1扫到n，同时维护两个数组las[i]和res[i]。las[i]代表扫到p时，i最后一次出现的位置，res[p]代表扫到p时，满足在[l, p]同时出现y和xy，或同时存在y和\frac{y}{x}的l的最靠右的位置。每扫到一个点，我们用p更新las[a[p]]，再用las[a[p] \times x]和las[\frac{a[p]}{x}]更新当前的res就可以了。

显然，利用刚才处理出的res[]数组，对于x为当前x的所有询问，它的答案均可以\Theta (1)求出，即判断l是否\leq res[r]。由于枚举了\sqrt N个x，每次遍历了整个序列，所以这一类询问总复杂度是\Theta (n \sqrt N)

代码如下

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 5;

int n, m;
int a[MAXN];
int block, blo[MAXN];
int ans[MAXN];
int limit = 300;

struct Data{
    int l, r, x, i, t;
    Data() {}
    Data(int l, int r, int x, int i, int t) : l(l), r(r), x(x), i(i), t(t) {}
};

Data qs[MAXN];
int qcnt;
int cnt[MAXN];
bitset<MAXN> bs1, bs2;

int Comp(const Data &a, const Data &b) {
    if (blo[a.l] != blo[b.l]) return a.l < b.l;
    return (blo[a.l] & 1) ? a.r < b.r : a.r > b.r;
}

void Ins(int x) {
    if (!cnt[x]) bs1[x] = 1, bs2[100000 - x] = 1;
    cnt[x]++;
}

void Del(int x) {
    cnt[x]--;
    if (!cnt[x]) bs1[x] = 0, bs2[100000 - x] = 0;
}

int CalcMul(int x) {
    for (int i = 1; i * i <= x; i++)
        if (x % i == 0 && bs1[i] && bs1[x / i])
            return 1;
    return 0;
}

int CalcDiv(int x) {
    for (int i = 1; i * x <= 100000; i++)
        if (bs1[i] && bs1[i * x])
            return 1;
    return 0;
}

void CaptainMo() {
    sort(qs + 1, qs + qcnt + 1, Comp);
    int nl = 1, nr = 0;
    for (int i = 1; i <= qcnt; i++) {
        int l = qs[i].l, r = qs[i].r, x = qs[i].x;
        while (nr < r) Ins(a[++nr]);
        while (nr > r) Del(a[nr--]);
        while (nl > l) Ins(a[--nl]);
        while (nl < l) Del(a[nl++]);
        if (qs[i].t == 1) ans[qs[i].i] = ((bs1 << x) & bs1).any();
        else if (qs[i].t == 2) ans[qs[i].i] = ((bs1 << (100000 - x)) & bs2).any();
        else if (qs[i].t == 3) ans[qs[i].i] = CalcMul(x);
        else ans[qs[i].i] = CalcDiv(x);
    }
}

vector<int> ql[MAXN], qr[MAXN], qi[MAXN];
int pre[MAXN], maxl[MAXN];

void Solve() {
    for (int x = 1; x <= limit; x++) {
        if (ql[x].empty()) continue;
        int l = 0;
        for (int i = 1; i <= n; i++) {
            int y = a[i];
            pre[y] = i;
            if (x * y <= 100000) l = max(l, pre[x * y]);
            if (y % x == 0) l = max(l, pre[y / x]);
            maxl[i] = l;
        }
        for (unsigned i = 0; i < ql[x].size(); i++)
            ans[qi[x][i]] = (ql[x][i] <= maxl[qr[x][i]]);
        memset(pre, 0, sizeof(pre));
        memset(maxl, 0, sizeof(maxl));
    }
}

int main() {
    scanf("%d%d", &n, &m);
    block = sqrt(n);
    for (int i = 1; i <= n; i++) blo[i] = (i - 1) / block + 1;
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= m; i++) {
        int opt, l, r, x;
        scanf("%d%d%d%d", &opt, &l, &r, &x);
        if (opt == 4 && x <= limit)
            ql[x].push_back(l), qr[x].push_back(r), qi[x].push_back(i);
        else
            qs[++qcnt] = Data(l, r, x, i, opt);
    }
    CaptainMo();
    Solve();
    for (int i = 1; i <= m; i++) puts(ans[i] ? "yuno" : "yumi");
    return 0;
}