luogu P3674 小清新人渣的本愿(莫队+bitset)
发布时间:2020-12-14 04:27:16 所属栏目:大数据 来源:网络整理
导读:这题是莫队维护bitset。 然而我并不会bitset 以前讲过认为不考就没学 我真的太菜了。 首先维护一个权值的bitset——s。 操作3比较简单,我们可以 (sqrt{x}) 枚举约数然后用bitset判断就行了。 操作1就是求是否存在 [exists{a,b},a-b=x] 移一下项 [a=x
这题是莫队维护bitset。 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<bitset> using namespace std; const int N=100101; int n,m,a[N],block[N],cnt[N]; string ans[N]; struct ques{ int l,r,type,id,x; }qu[N]; bool cmp(ques a,ques b){ if(block[a.l]==block[b.l])return a.r<b.r; else return block[a.l]<block[b.l]; } bitset<N> x,y; int read(){ int sum=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return sum*f; } int main(){ n=read();m=read(); int Block=sqrt(n); for(int i=1;i<=n;i++)a[i]=read(),block[i]=(i-1)/Block+1; for(int i=1;i<=m;i++)qu[i].type=read(),qu[i].l=read(),qu[i].r=read(),qu[i].x=read(),qu[i].id=i; sort(qu+1,qu+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ while(r<qu[i].r){ r++; cnt[a[r]]++; if(cnt[a[r]]==1)x[a[r]]=1,y[n-a[r]]=1; } while(l>qu[i].l){ l--; cnt[a[l]]++; if(cnt[a[l]]==1)x[a[l]]=1,y[n-a[l]]=1; } while(r>qu[i].r){ if(cnt[a[r]]==1)x[a[r]]=0,y[n-a[r]]=0; cnt[a[r]]--; r--; } while(l<qu[i].l){ if(cnt[a[l]]==1)x[a[l]]=0,y[n-a[l]]=0; cnt[a[l]]--; l++; } if(qu[i].type==1){ if((x&(x<<qu[i].x)).any())ans[qu[i].id]="hana"; else ans[qu[i].id]="bi"; } else if(qu[i].type==2){ if(qu[i].x-n>=0){ if(((y<<(qu[i].x-n))&x).any())ans[qu[i].id]="hana"; else ans[qu[i].id]="bi"; } else{ if(((x<<(n-qu[i].x))&y).any())ans[qu[i].id]="hana"; else ans[qu[i].id]="bi"; } } else{ for(int j=1;j<=sqrt(qu[i].x);j++) if(qu[i].x%j==0&&x[j]&&x[qu[i].x/j])ans[qu[i].id]="hana"; if(ans[qu[i].id]!="hana")ans[qu[i].id]="bi"; } } for(int i=1;i<=m;i++)cout<<ans[i]<<endl; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |