小清新人渣的本愿

链接：https://www.luogu.com.cn/problem/P3674

题目描述：给定一个序列，有三种操作：

询问一个区间是否可以选出两个数它们的差为\(x\)。

询问一个区间是否可以选出两个数它们的和为\(x\)。

询问一个区间是否可以选出两个数它们的积为\(x\)。

题解：对于第三种操作，可以直接莫队，由于枚举约数是\(O(sqrt(n))\)的。

对于第一种操作，可用\(bitset\)维护每个数，查询时可用\(a\)&\((a>>x)\)。

对于第二种操作，可以维护一个反向的\(bitset\)，就和第一种操作一样了。

#include
#include
#include
#include
#include
using namespace std;
struct node
{
int op,l,r,x,num,block;
bool operator <(const node &a)const
{
if (block!=a.block)
return block return r }
};
node L[100001];
vectorp[100001];
vectord[100001];
int maxn,tong[100001],sz,a[100001],n,m,res,lpos,rpos;
bool ans[100001];
bitset<100000>S;
bitset<100000>S2;
bool cmp(node a,node b)
{
return a.l}
void movepos(int x,int d)
{
tong[a[x]]+=d;
if (tong[a[x]]==(d+1)/2)
{
S[a[x]]=(d+1)/2;
S2[maxn-a[x]]=(d+1)/2;
}
return;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;++i)
{
cin>>a[i];
maxn=max(maxn,a[i]);
}
for (int i=1;i<=m;++i)
{
cin>>L[i].op>>L[i].l>>L[i].r>>L[i].x;
L[i].num=i;
}
sz=sqrt(m);
sort(L+1,L+m+1,cmp);
for (int i=1;i<=m;++i)
L[i].block=(i-1)/sz+1;
sort(L+1,L+m+1);
lpos=1;
rpos=0;
for (int i=1;i<=m;++i)
{
while (lpos movepos(lpos++,-1);
while (lpos>L[i].l)
movepos(--lpos,1);
while (rpos movepos(++rpos,1);
while (rpos>L[i].r)
movepos(rpos--,-1);
if (L[i].op==1)
ans[L[i].num]=(S&(S>>L[i].x)).count()>=1;
if (L[i].op==2)
{
if (L[i].x>=maxn)
ans[L[i].num]=((S>>(L[i].x-maxn))&S2).count()>=1;
else
ans[L[i].num]=(S&(S2>>(maxn-L[i].x))).count()>=1;
}
if (L[i].op==3)
{
for (int j=1;j*j<=L[i].x;++j)
if (L[i].x%j==0)
ans[L[i].num]|=tong[j]&&tong[L[i].x/j];
}
}
for (int i=1;i<=m;++i)
{
if (ans[i])
cout<<"hana"< else
cout<<"bi"< }
return 0;
}