P3674 小清新人渣的本愿 莫队+bitset

时间：2022-08-26 05:47:14

ennmm...bitset能过系列。

莫队+bitset \(\mathcal{O}(m\sqrt n + \frac{nm}{w})\)

维护一个正向的 bitset <N> mem ，再维护一个反向的 bitset <N> mem1，即 mem1[N-x]=mem[x];

对于 \(-\) 直接 mem&mem<<x 就是相差 \(x\) 的两个点 与 一下

对于 \(+\) 直接 mem&mem1<<(N-x) 因为原来 mem[i] 代表 i , mem1[i] 代表 N-i,所以没有位移时对应位置 与 一下就是是否存在两个数加起来 \(= N\)

对于 \(\times\) 暴力枚举约数即可。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<bitset>

#include<vector>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;

	do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;

} const int N=100005;

int n,m,B,mx,a[N],c[N],pos[N];

bool ans[N];

struct node { int op,l,r,x,id;

	inline bool operator < (const node& that) const

		{return pos[l]==pos[that.l]?(pos[l]&1)?r<that.r:r>that.r:l<that.l;}

}q[N];

bitset <N> mem,mem1;

inline void add(int x) {if(++c[x]==1) mem[x]=1,mem1[N-x]=1;}

inline void sub(int x) {if(--c[x]==0) mem[x]=0,mem1[N-x]=0;}

inline bool cadd(int x) {return (mem&(mem1>>N-x)).any();}

inline bool csub(int x) {return (mem&(mem<<x)).any();}

inline bool cmul(int x) {

	for(R i=1;i*i<=x;++i) if(x%i==0&&mem[i]&&mem[x/i])

		return true; return false;

}

inline void main() {

	n=g(),m=g();

	for(R i=1;i<=n;++i) a[i]=g(),mx=max(mx,a[i]);

	for(R i=1,op,LL,RR,x;i<=m;++i)

		op=g(),LL=g(),RR=g(),x=g(),q[i]=(node){op,LL,RR,x,i};

	B=sqrt(n); for(R i=1;i<=m;++i) pos[i]=(i-1)/B+1;

	sort(q+1,q+m+1);

	for(R i=1,l=1,r=0,op,LL,RR,x,id;i<=m;++i) {

		op=q[i].op,LL=q[i].l,RR=q[i].r,x=q[i].x,id=q[i].id;

		while(l<LL) sub(a[l++]); while(l>LL) add(a[--l]);

		while(r<RR) add(a[++r]); while(r>RR) sub(a[r--]);

		if(op==1) ans[id]=csub(x);

		if(op==2) ans[id]=cadd(x);

		if(op==3) ans[id]=cmul(x);

	} for(R i=1;i<=m;++i) puts(ans[i]?"hana":"bi");

}

} signed main() {Luitaryi::main(); return 0;}

2019.11.22

相关文章