P3674 小清新人渣的本愿

博主的 BiBi 时间

看到这道题完全无从下手，翻了翻题解。。。属实 NB

( ext{Description})

传送门

( ext{Solution})

先考虑每一个操作。

• 操作一：我们要查找 (a-b=x)。其实就是查找是否存在 (a,a-x)。讲一下为什么要选择这两个数来查找，你会发现要求转化为在 ([l,r]) 是否有两个数的距离是 (x)，我们用 ( ext{bitset}) 的下标维护某个值是否存在，那么就可以直接用 (bit>>x & bit) 来判断。
• 操作二：我们要查找 (a+b=x)。这个不太好搞，因为 (a,b) 之间没有 ‘-’，就无法表示距离。这里有个小技巧：再开一个 ( ext{bitset})，第 (pos) 位为 (1) 表示 (N-pos) 这个值出现了。这样有什么好处？我们原先在 (bit) 里查找 (a=x-b)，现在在 (abit) 里查找 (N-a=N-(x-b)=b+(N-x))。至此，我们只需要将 (bit<<(N-x) & abit) 就行了。
• 操作三：枚举约数判断即可，这是 (mathcal{O(sqrt n)})。

总时间复杂度 (mathcal O(n*m/64)) 就艹过去了。

( ext{Code})

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
	T x=0; int f=1; char s;
	while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
	while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return x*f;
}
template <class T> inline void write(const T x) {
	if(x<0) return (void) (putchar('-'),write(-x));
	if(x>9) write(x/10);
	putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T Gcd(const T x,const T y) {return y?Gcd(y,x%y):x;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

#include <cmath>
#include <bitset>
#include <algorithm>
using namespace std;

const int N=1e5;

int n,m,bl,be[N+5],a[N+5],c[N+5];
bool ans[N+5];
struct node {int op,l,r,x,id;} q[N+5];
bitset <N+5> x,y;

bool cmp(node a,node b) {return (be[a.l]^be[b.l])?be[a.l]<be[b.l]:((be[a.l]&1)?a.r<b.r:a.r>b.r);}

void add(int num) {
	if(c[num]++==0) x[num]=y[N-num]=1;
}

void del(int num) {
	if(--c[num]==0) x[num]=y[N-num]=0;
}

int main() {
	n=read(9),m=read(9); bl=sqrt(n);
	rep(i,1,n) a[i]=read(9),be[i]=(i-1)/bl+1;
	rep(i,1,m) q[i].op=read(9),q[i].l=read(9),q[i].r=read(9),q[i].x=read(9),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	rep(i,1,m) {
		while(l>q[i].l) add(a[--l]);
		while(r<q[i].r) add(a[++r]);
		while(l<q[i].l) del(a[l++]);
		while(r>q[i].r) del(a[r--]);
		if(q[i].op==1) {
			if((x>>q[i].x&x).any()) ans[q[i].id]=1;
		}
		else if(q[i].op==2) {
			if((y>>N-q[i].x&x).any()) ans[q[i].id]=1;
		}
		else {
			for(int j=1;j*j<=q[i].x;++j)
				if(q[i].x%j==0&&x[j]&&x[q[i].x/j]) {
					ans[q[i].id]=1;
					break;
				}
		}
	}
	rep(i,1,n) puts(ans[i]?"hana":"bi");
	return 0;
}