BZOJ 4810 [Ynoi2017]由乃的玉米田

题目大意

给你一个长度为$n$的序列$a$，$m$次询问一个区间是否可以选出两个数使得他们的和/差/积为$x$.

---

首先这道题看起来很没头绪，数据还不是强制在线的……考虑莫队。

对于积的询问，可以考虑直接枚举那个较小的因子。

对于差的询问，可以考虑使用维护桶，查询的时候进行一次平移看看有没有重合即可。

对于和的询问，$x+y=a \to (100000-x)-y=100000-a$ 得到的$x$和$y$可以放回去$x=100000-x,y=y$

使用方法：

• 定义：bitset<"type"> a;
• 修改：a[x]=true;
• 查询：a[x]==true 查询编号为$x$的元素是否为 true
• 特殊：a.any() 查询是否存在元素为 true | a.all() 查询是否所有元素都为 true | a.none() 查询是否所有元素都为 false

#include <cmath>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
int n,m,lim,v[100010],cnt[100010],ans[100010];
struct request{int opt,l,r,x,id;}q[100010];
bool cmp(const request &x,const request &y){return x.l/lim==y.l/lim?x.r<y.r:x.l/lim<y.l/lim;}
bitset<100010>a,b;
void movel(int x,int y)
{
	int i;
	if(x<y)
		for(i=x;i<y;++i)
		{
			--cnt[v[i]];
			if(cnt[v[i]]==0) a[v[i]]=b[100000-v[i]]=false;
		}
	if(x>y)
		for(i=x-1;i>=y;--i)
		{
			if(cnt[v[i]]==0) a[v[i]]=b[100000-v[i]]=true;
			++cnt[v[i]];
		}
}
void mover(int x,int y)
{
	int i;
	if(x<y)
		for(i=x+1;i<=y;++i)
		{
			if(cnt[v[i]]==0) a[v[i]]=b[100000-v[i]]=true;
			++cnt[v[i]];
		}
	if(x>y)
		for(i=x;i>y;--i)
		{
			--cnt[v[i]];
			if(cnt[v[i]]==0) a[v[i]]=b[100000-v[i]]=false;
		}
}
int main()
{
	int i,j;
	scanf("%d%d",&n,&m),lim=sqrt(n);
	for(i=1;i<=n;++i) scanf("%d",v+i);
	for(i=1;i<=m;++i) scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	for(i=1;i<=m;++i)
	{
		movel(q[i-1].l,q[i].l),mover(q[i-1].r,q[i].r);
		if(q[i].opt==1) ans[q[i].id]=(a&(a>>q[i].x)).any();
		if(q[i].opt==2) ans[q[i].id]=(a&(b>>(100000-q[i].x))).any();
		if(q[i].opt==3)
			for(j=1;j*j<=q[i].x;++j)
				if(q[i].x%j==0&&cnt[j]&&cnt[q[i].x/j])
					{ans[q[i].id]=true;break;}
	}
	for(i=1;i<=m;++i) puts(ans[i]?"yuno":"yumi");
	return 0;
}