Description
Link.
见 Link。
Solution
前三个操作就是小清新人渣的本愿。
这里简单讲解一下。
记录两个 bitset cla 和 inv。
我们考虑莫队。
cla[x]==1 表示 $x$ 这个数出现过。
inv[x]==1 表示 $100000-x$ 这个数出现过。
这两个 bitset 的维护很简单，就是在莫队的加减贡献操作里改就行了。
对于第一个减法的判断，我们的答案就是 ((cla<<x)&cla) 是否为 0。
如果为 0 的话表示应该输出有解。
正确性很好得到。
比如我们的询问是是否存在 $a,b$ 使得 $a-b=x$。
那么我们只需要存在 $a$ 以及 $a-x$ 即可。
第二个加法的判断也差不多，看作是加一个负数即可，判断是 ((cla<<(100000-x)&inv))。
第三个乘法的判断直接暴力枚举因子 $i$，判断 $i,\frac{x}{i}$ 是否同时存在即可。($i\mid x$)。
由于值域和 $n,m$ 同阶，所以我们的复杂度是对的。
对于第四个操作我们直接从乘法贺过来。
枚举一个 $i$，从 1 开始，终止条件为 $i\times x\le100000$。
其中 $x$ 为当前询问给出的商。
然后直接判断是否同时存在 $i$ 和 $i\times x$ 即可。
在 $x\ge\sqrt{n}$ 的时候我们的复杂度是对的。
那么 $x<\sqrt{n}$ 的时候我们就换一种方法吧。
我们枚举一个 $x\in[1,\sqrt{100000}]$。
然后维护两个数组 pre 和 mxp。
在 $x$ 的枚举里面我们再枚举一个 $i\in[1,n]$。
然后 pre[i] 表示 $a_{i}$ 的上一次出现位置。
mxp[i] 扫描到 $i$ 的时候出现了满足 $a\div b=x$ 的最右位置。
维护的具体方法看注释吧。
这道题就完了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
const int Maxn = 1e5 + 5, Maxs = 400 + 5, Maxv = 310;
int n, m, each, cube, isa[Maxn], cnt[Maxn], ans[Maxn], pre[Maxn], mxp[Maxn], bel[Maxn], lps[Maxs], rps[Maxs];
struct Query
{
int t, l, r, x, id;
Query() {}
Query(int t1, int t2, int t3, int t4, int t5)
{
t = t1;
l = t2;
r = t3;
x = t4;
id = t5;
}
};
struct Special
{
int l, r, id;
Special() {}
Special(int t1, int t2, int t3)
{
l = t1;
r = t2;
id = t3;
}
};
vector < Query > Mq; // Mo's Algorithm | Query
vector < Special > Vq[Maxn]; // Violence | Query
bitset < Maxn > cla, inv; // classic | inverse
bool cmp(const Query &one, const Query &ano)
{
if (bel[one.l] != bel[ano.l]) return one.l < ano.l;
else if (bel[one.l] & 1) return one.r < ano.r;
else return one.r > ano.r;
}
void Plus_Cont(int x)
{
x = isa[x];
if (cnt[x] == 0)
{
cla[x] = 1;
inv[100000 - x] = 1;
}
++cnt[x];
}
void Mins_Cont(int x)
{
x = isa[x];
--cnt[x];
if (cnt[x] == 0)
{
cla[x] = 0;
inv[100000 - x] = 0;
}
}
void Pare_v1()
{
int l = 1, r = 0;
for (auto it : Mq)
{
while (l > it.l) Plus_Cont(--l);
while (l < it.l) Mins_Cont(l++);
while (r > it.r) Mins_Cont(r--);
while (r < it.r) Plus_Cont(++r);
if (it.t == 1) ans[it.id] = ((cla << it.x) & cla).any();
else if (it.t == 2) ans[it.id] = ((cla << (100000 - it.x)) & inv).any();
else if (it.t == 3)
{
bool flag = 0;
for (int i = 1; i * i <= it.x; ++i)
{
if (it.x % i == 0 && cla.test(i) && cla.test(it.x / i))
{
ans[it.id] = 1;
flag = 1;
break;
}
}
if (flag == 0) ans[it.id] = 0;
}
else
{
bool flag = 0;
for (int i = 1; i * it.x <= 100000; ++i)
{
if (cla.test(i) && cla.test(i * it.x))
{
ans[it.id] = 1;
flag = 1;
break;
}
}
if (flag == 0) ans[it.id] = 0;
}
}
}
void Pare_v2()
{
for (int x = 1; x <= Maxv; ++x)
{
if (Vq[x].empty()) continue;
int now = 0;
for (int i = 1; i <= n; ++i)
{
int y = isa[i];
pre[y] = i;
if (x * y <= 100000) now = max(now, pre[x * y]);
if (y % x == 0) now = max(now, pre[y / x]);
mxp[i] = now;
}
for (auto it : Vq[x])
{
if (it.l <= mxp[it.r]) ans[it.id] = 1;
else ans[it.id] = 0;
}
memset(pre, 0, sizeof pre);
memset(mxp, 0, sizeof mxp);
}
}
char ANS[2][10] = { "yumi", "yuno" };
signed main()
{
scanf("%d %d", &n, &m);
each = 320;
cube = (n - 1) / each + 1;
for (int i = 1; i <= n; ++i) scanf("%d", &isa[i]);
for (int i = 1; i <= cube; ++i)
{
lps[i] = rps[i - 1] + 1;
rps[i] = rps[i - 1] + each;
if (i == cube) rps[i] = n;
for (int j = lps[i]; j <= rps[i]; ++j) bel[j] = i;
}
for (int i = 1, t, l, r, x; i <= m; ++i)
{
scanf("%d %d %d %d", &t, &l, &r, &x);
if (t == 4 && x <= Maxv) Vq[x].emplace_back(Special(l, r, i));
else Mq.emplace_back(Query(t, l, r, x, i));
}
sort(Mq.begin(), Mq.end(), cmp);
Pare_v1(), Pare_v2();
for (int i = 1; i <= m; ++i) puts(ANS[ans[i]]);
return 0;
}