自己上网学一下bitset就好
很简单的
by Shadows @ 2017-03-30 15:13:16
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const int N=100005, M=200005;
inline ll read(){
char c=getchar();ll x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, Q, a[N], op, l, r, x;
int block, m, pos[N];
struct meow{
int l, r, x, type, qid;
bool operator <(const meow &a) const {return pos[l]==pos[a.l] ? r<a.r : pos[l]<pos[a.l];}
}q[N];
int ans[N];
struct Meow{
bitset<M> a, b, c;
int cou[N];
inline void add(int v) {
cou[v]++;
if(cou[v]==1) a[v]=1, b[v+N]=1, c[-v+N]=1;
}
inline void del(int v) {
cou[v]--;
if(cou[v]==0) a[v]=0, b[v+N]=0, c[-v+N]=0;
}
int Que(int type, int x) { //printf("Que %d %d\n",type,x);
int ans=0;
if(type==1) {
if( (a & (a<<x)).any() ) ans=1;
}else if(type==2) {
if( (b & (c<<x)).any() ) ans=1;
}else {
int m=sqrt(x);
for(int i=1; i<=m; i++) if(x%i == 0)
if(cou[i] && cou[x/i]) {ans=1; break;}
}
return ans;
}
}A;
void modui(){
int l=1, r=0;
for(int i=1; i<=Q; i++){
while(r<q[i].r) r++, A.add(a[r]);
while(r>q[i].r) A.del(a[r]), r--;
while(l<q[i].l) A.del(a[l]), l++;
while(l>q[i].l) l--, A.add(a[l]);
ans[q[i].qid]= A.Que(q[i].type, q[i].x);
}
}
int main()
{
n=read(); Q=read();
block=sqrt(n); m=(n-1)/block+1;
for(int i=1; i<=n; i++) a[i]=read(), pos[i]=(i-1)/block+1;
for(int i=1; i<=Q; i++)
op=read(), l=read(), r=read(), x=read(), q[i]=(meow){l, r, x, op, i};
sort(q+1, q+1+Q);
modui();
for(int i=1; i<=Q; i++) puts(ans[i] ? "hana" : "bi");
}
我代码很丑,这时网上的题解代码
```
by lxd150039 @ 2017-04-16 11:11:16
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ri(x) scanf("%d",&x)
const int N=400024;
int M=400;
struct line{int op,l,r,s,pos,xh;}pr[N];
bool cmp(line i,line j){if(i.pos==j.pos) return i.r<j.r; return i.pos<j.pos;}
int a[N],vis[N]; bool ans[N];
bitset<200024> VIS,V;
inline void js(int p,int r){
int i,l=pr[p].l,x=pr[p].s,op=pr[p].op;
for(i=l;i<=r;++i){
++vis[a[i]];
if(op==1){if(a[i]+x<N&&vis[a[i]+x]||a[i]-x>=0&&vis[a[i]-x]){ans[pr[p].xh]=1; break;}}
else if(op==2){if(x-a[i]>=0&&vis[x-a[i]]){ans[pr[p].xh]=1; break;}}
else if(op==3){if(a[i]&&x%a[i]==0&&vis[x/a[i]]){ans[pr[p].xh]=1; break;}}
}
if(i>r) --i; while(i>=l) --vis[a[i]],--i;
}
inline void add(int l,int p){
int i,r=pr[p].r,x=pr[p].s,op=pr[p].op;
for(i=l;i<=r;++i){
VIS[a[i]+100001]=V[-a[i]+100001]=1; ++vis[a[i]];
if(op==1){if(a[i]+x<N&&vis[a[i]+x]||a[i]-x>=0&&vis[a[i]-x]){ans[pr[p].xh]=1; break;}}
else if(op==2){if(x-a[i]>=0&&vis[x-a[i]]){ans[pr[p].xh]=1; break;}}
else if(op==3){if(a[i]&&x%a[i]==0&&vis[x/a[i]]){ans[pr[p].xh]=1; break;}}
}
for(++i;i<=r;++i){VIS[a[i]+100001]=V[-a[i]+100001]=1; ++vis[a[i]];}
}
void work(int n,int m){
int rf=-1,i,j,q,st,x;
for(i=1;i<=m;++i){
if(pr[i].pos!=rf){rf=pr[i].pos; V=VIS=0; memset(vis,0,sizeof(vis)); st=q=min(n,(rf+1)*M);}
x=pr[i].s;
if(pr[i].op==3){
for(j=1;j*j<=x;++j)
if(x%j==0&&vis[x/j]&&vis[j]){ans[pr[i].xh]=1; break;}
}
else
if(pr[i].op==1){
if((V&(V<<x)).any()) ans[pr[i].xh]=1;
}
else
if(pr[i].op==2){
if((VIS&(V<<x)).any()) ans[pr[i].xh]=1;
}
if(pr[i].r>q){add(q+1,i); q=pr[i].r;}
if(!ans[pr[i].xh]) js(i,min(pr[i].r,st));
}
}
int main(){
int i,n,m;
ri(n); ri(m);
//if(n<=4000) M=4000;
for(i=1;i<=n;++i) ri(a[i]);
for(i=1;i<=m;++i){ri(pr[i].op); ri(pr[i].l); ri(pr[i].r); if(pr[i].l>pr[i].r) swap(pr[i].l,pr[i].r); ri(pr[i].s); pr[i].xh=i; pr[i].pos=pr[i].l/M;}
sort(pr+1,pr+m+1,cmp);
work(n,m);
for(i=1;i<=m;++i)
if(ans[i]) puts("hana");
else puts("bi");
return 0;
}
```
by 神姬2016 @ 2017-05-31 21:27:36
#本题AC代码
我给你了,快给我红包
by 1jia1 @ 2017-08-26 16:22:16
一群财迷
by 我不是小明 @ 2018-07-03 10:44:42
hehe
by lionrenard @ 2019-09-10 18:38:07
![](//图.tk/e)
by SpeMars @ 2022-07-06 07:22:08