小清新人渣的本愿-526互联

这道题还挺神仙的。

Link

首先就可以考虑莫队，这道题好像有且仅有这一个莫队解法。

首先观察到这道题的数据范围

\[n,m\leq 10^5 ,C\leq 10^5. \]

思考了很久也没想到神奇的莫队技巧，所以考虑卡常数。

构造一个 \(Bitset,\) 然后处理每一个书是否出现。\(Bitset\) 的复杂度为 \(\frac{n}{w},\) 然后就很好处理加减法了。

直接判断存在的点 \(i+C\) 是否存在，若存在 \(Yes\) ，否则 \(No.\)

乘法枚举 \(C\) 的因数判断一下就好了 \(.\)

代码的话处理一下常数问题就好，总复杂度为 \(\Theta (\frac{nm}{w}),\) \(w\) 视电脑编译器而论，通常为 \(32\ 或 \ 64.\)

稍微快读快写拉好数组大小是没有问题的， \(Bitset\) 开 \(2 \times {10^5},\) 注意处理未定义行为。

代码并不复杂

由乃 \(OI\) 题目 \(+1\)

// Qx's data
#include <bits/stdc++.h>
#define ll long long
#define gc getchar()
const int N=2e5+10;
std::bitset<N> mark,mark2;
std::bitset<N> ret;
int a[N],c[N];
int curl,curr;
int n,m,opt,l,r;
bool is1,is2,is3;
int k;
struct query{
	int l,r,c,opt,rk;
}ask[N];
bool cmp(query u,query v){
	if(u.l/k != v.l/k) return u.l/k < v.l/k;
	if(u.l&1) return u.r<v.r;
	else return u.r>v.r;
}
namespace IO{
	void read(int &res){
		res=0;
		char ch=0;
		while(!isdigit(ch)) ch=gc;
		while(isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=gc;
		return;
	}
}
inline void Put(std::string s){
	for(char chr:s)
		putchar(chr);
	putchar('\n');
}
inline void add(int pos){
	if(!c[a[pos]])mark[a[pos]]=mark2[N-a[pos]]=true;
	c[a[pos]]++;
}

inline void del(int pos){
	--c[a[pos]];
	if(!c[a[pos]]){
		mark[a[pos]]=mark2[N-a[pos]]=false;
	}
}

namespace Queue{
	inline void check(int i){
		if(ask[i].opt==2){
			ret[ask[i].rk]=(mark&(mark2>>(N-ask[i].c))).any();
		}else if(ask[i].opt==3){
			for(register int p=1;p<=sqrt(ask[i].c);++p){
				if(!(ask[i].c%p)){
					if(mark[p] && mark[ask[i].c/p]){
						ret[ask[i].rk]=true;
						break ;
					}
				}
			}
		}else{
			ret[ask[i].rk]=(mark&(mark<<ask[i].c)).any();
		}
	}
	inline void Input(void){
		IO::read(n),IO::read(m);
		k=pow(n,0.6);
		for(register int i=1;i<=n;++i)
			IO::read(a[i]);
		for(register int i=1;i<=m;++i){
			IO::read(ask[i].opt),IO::read(ask[i].l),IO::read(ask[i].r),IO::read(ask[i].c);
			ask[i].rk=i;
		}
		std::stable_sort(ask+1,ask+m+1,cmp);
	}
	inline void Work(void){
		for(register int i=curl=ask[1].l;i<=(curr=ask[1].r);++i){
			add(i);
		}
		check(1);
		for(register int i=2;i<=m;++i){
			while(curl<ask[i].l)del(curl++);
			while(curl>ask[i].l)add(--curl);
			while(curr<ask[i].r)add(++curr);
			while(curr>ask[i].r)del(curr--);
			check(i);
		}
	} 
	inline void Output(void){
		for(register int i=1;i<=m;++i)
			Put(ret[i]?"hana":"bi");
	}
}
int main(){
	Queue::Input();
	Queue::Work();
	Queue::Output();
}