题解 P3674 【小清新人渣的本愿】
zcysky
2017-06-17 10:44:46
加减维护一个bitset就好了
这个套路很简单，百度下bitset你就会了
实在不行你就简单理解为状压
但是乘可能不好bitset
所以直接大力枚举约数
反正是O(sqrt(n))个
不会出事的
```cpp
#include<bits/stdc++.h>
#define N 100000
#define M 20000005
using namespace std;
struct Query{int k,l,r,x,id;}q[N+5];
int m,n,l,r,s;
int a[N+5],c[N+5],ans[N+5],rt[N+5];
bitset<N+5> now1,now2;
char DR[M+10],*P=DR;
inline bool operator<(Query x,Query y){
return rt[x.l]==rt[y.l]?rt[x.l]&1?x.r<y.r:x.r>y.r:rt[x.l]<rt[y.l];
}
struct FastIO{
static const int S=1310720;
int wpos;char wbuf[S];
FastIO():wpos(0) {}
inline int xchar(){
static char buf[S];
static int len=0,pos=0;
if(pos==len)pos=0,len=fread(buf,1,S,stdin);
if(pos==len)return -1;
return buf[pos++];
}
inline int read(){
int c=xchar(),x=0;
while(c<=32&&~c)c=xchar();
if(c==-1)return -1;
for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
return x;
}
}io;
inline void init(){
n=io.read();m=io.read();s=(int)sqrt(n);
for(register int i=1;i<=n;++i)a[i]=io.read();
for(register int i=1;i<=n;++i)rt[i]=(i-1)/s+1;
for(register int i=1;i<=m;++i){
q[i].k=io.read();q[i].l=io.read();q[i].r=io.read();
q[i].x=io.read();q[i].id=i;
}
sort(q+1,q+m+1);l=1;r=0;
}
inline void add(int x){if(c[x]++==0)now1[x]=1,now2[N-x]=1;}
inline void del(int x){if(--c[x]==0)now1[x]=0,now2[N-x]=0;}
int main(){
init();
for(int i=1;i<=m;i++){
for(;q[i].l<l;)add(a[--l]);
for(;q[i].l>l;)del(a[l++]);
for(;q[i].r<r;)del(a[r--]);
for(;q[i].r>r;)add(a[++r]);int k=q[i].k,x=q[i].x;
if(k==1){if((now1&(now1<<x)).any())ans[q[i].id]=1;}
else if(k==2){if((now1&(now2>>(N-x))).any())ans[q[i].id]=1;}
else{
for(int j=1;j*j<=x;j++)
if(!(x%j))if(now1[j]&&now1[x/j]){ans[q[i].id]=1;break;}
}
}
for (int i=1;i<=m;i++)if(ans[i])puts("hana");else puts("bi");
return 0;
}
```