【莫队+bitset】BZOJ4810 [Ynoi2017]由乃的玉米田

题面在这里

​

直接莫队……用bitset维护出现过哪些值 \[ a-b=x\Leftrightarrow a=b+x \\ a+b=x\Leftrightarrow a=-(b-x) \]

对于操作1，bitset左移x位后对自己取并

对于操作2，需要同时维护一个所有值的相反数的bitset，同1

对于操作3，直接爆枚因子即可

时间复杂度\(O(n\sqrt n)\)

​

示例程序：

#include<cstdio>
#include<bitset>
#include<cmath>
#include<algorithm>
using namespace std;
inline char nc(){
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int red(){
	int res=0,f=1;char ch=nc();
	while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
	while ('0'<=ch&&ch<='9') res=res*10+ch-48,ch=nc();
	return res*f;
}

const int maxn=100005;
int n,q,a[maxn],h[maxn];
struct Query{
	int t,l,r,x,id;
	bool operator<(const Query&b)const{
		if (h[l]==h[b.l]) return r<b.r;
		return l<b.l;
	}
}Q[maxn];
void blocker(){
	int k=sqrt(n);
	for (int i=1;i<=n;i++) h[i]=i/k;
}
bitset<maxn*2> A,B;
int cnt[maxn*2];
void add(int x){
	if (!cnt[x]) A[x+100000]=1;
	if (!cnt[x]) B[100000-x]=1;
	cnt[x]++;
}
void dec(int x){
	cnt[x]--;
	if (!cnt[x]) A[x+100000]=0;
	if (!cnt[x]) B[100000-x]=0;
}
bool ans[maxn];
int main(){
	n=red(),q=red();
	for (int i=1;i<=n;i++) a[i]=red();
	blocker();
	for (int i=1;i<=q;i++) Q[i].t=red(),Q[i].l=red(),Q[i].r=red(),Q[i].x=red(),Q[i].id=i;
	sort(Q+1,Q+1+q);
	int L=1,R=1; add(a[1]);
	for (int i=1;i<=q;i++){
		while (Q[i].l<L) add(a[--L]);
		while (R<Q[i].r) add(a[++R]);
		while (L<Q[i].l) dec(a[L++]);
		while (Q[i].r<R) dec(a[R--]);
		if (Q[i].t==1){
			ans[Q[i].id]=(A&(A<<Q[i].x)).any();
		}else
		if (Q[i].t==2){
			ans[Q[i].id]=(A&(B<<Q[i].x)).any();
		}else{
			for (int d=1,td=sqrt(Q[i].x);d<=td;d++)
			 if (Q[i].x%d==0&&cnt[Q[i].x/d]&&cnt[d]) {ans[Q[i].id]=1;break;}
		}
	}
	for (int i=1;i<=q;i++) puts(ans[i]?"yuno":"yumi");
	return 0;
}