自动搬运

查看原文

来自洛谷，原作者为

	Ireliaღ 逝去的是刀锋，不变的是意志

搬运于2025-08-24 22:09:54，当前版本为作者最后更新于2020-06-12 20:19:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一句话题意

给一个长度为$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;
}