P3674 加强版（
多了一个商。
利用 bitset，可以直接枚举 \(i\) 判断 \(x\) 与 \(ix\) 是否同时存在。
但是当 \(x\) 较小时出现了问题。考虑根号分治。
\(x\) 较小的时候考虑扫描线：对于所有 \(x\) 相同的询问，从左往右扫描序列，并维护当前所有商为 \(x\) 的数对中靠左的那个的最大值。
然后直接回答即可。
常数极小，良心不卡常。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using namespace std;
const int N = 1e5;
const int BLK = 233;
const int LIM = 233;
int n,m;
int block,lim,pos[N + 5],a[N + 5];
int ans[N + 5],cnt[N + 5];
bitset<N + 5> cur[2];
struct s_query
{
int op,l,r,x,id;
inline bool operator<(const s_query &a) const
{
return pos[l] < pos[a.l] || (pos[l] == pos[a.l] && r < a.r);
}
} qry[N + 5];
vector<int> vec[LIM + 5],w[N + 5];
int las[N + 5];
int main()
{
scanf("%d%d",&n,&m),block = BLK,lim = LIM;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d%d",&qry[i].op,&qry[i].l,&qry[i].r,&qry[i].x),qry[i].id = i;
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
while(r < qry[i].r)
{
++r;
if(!cnt[a[r]]++)
cur[0][a[r]] = 1,cur[1][N - a[r]] = 1;
}
while(r > qry[i].r)
{
if(!--cnt[a[r]])
cur[0][a[r]] = 0,cur[1][N - a[r]] = 0;
--r;
}
while(l < qry[i].l)
{
if(!--cnt[a[l]])
cur[0][a[l]] = 0,cur[1][N - a[l]] = 0;
++l;
}
while(l > qry[i].l)
{
--l;
if(!cnt[a[l]]++)
cur[0][a[l]] = 1,cur[1][N - a[l]] = 1;
}
if(qry[i].op == 1)
ans[qry[i].id] = (cur[0] & (cur[0] << qry[i].x)).any();
else if(qry[i].op == 2)
ans[qry[i].id] = (cur[0] & (cur[1] >> N - qry[i].x)).any();
else if(qry[i].op == 3)
for(register int j = 1;j * j <= qry[i].x && !ans[qry[i].id];++j)
!(qry[i].x % j) && (ans[qry[i].id] = cur[0][j] & cur[0][qry[i].x / j]);
else if(qry[i].x > lim)
for(register int j = 1;j * qry[i].x <= N && !ans[qry[i].id];++j)
ans[qry[i].id] = cur[0][j] & cur[0][j * qry[i].x];
else
vec[qry[i].x].push_back(i);
}
for(register int v = 0;v <= lim;++v)
{
for(register int i = 1;i <= n;++i)
w[i].clear(),las[i] = 0;
for(register int i : vec[v])
w[qry[i].r].push_back(i);
for(register int i = 1,cur = 0;i <= n;++i)
{
las[a[i]] = i,
a[i] * v <= N && (cur = max(cur,las[a[i] * v])),
v && !(a[i] % v) && (cur = max(cur,las[a[i] / v]));
for(register int j : w[i])
ans[qry[j].id] = cur >= qry[j].l;
}
}
for(register int i = 1;i <= m;++i)
puts(ans[i] ? "yuno" : "yumi");
}