莫队 $+$ $bitset$.

我们可以用 $bitset$ 维护当前 $l,r$ 区间数的出现的状态,莫对依旧按照套路搞,然后来考虑怎么回答每一个询问。

对于操做 $1$ ,要求回答我们从当前区间能否找出 $a,b$ 使得其差为 $x$。

很显然,$a-b=x$ 等价于 $a=b+x$。

我们维护的是数的出现的状态,于是可以将当前的 $bitset$ 左移 $x$ 位,也就是让所有数都加上 $x$,然后与原 $bitset$ 做与运算,看看是否有一个 $a$ 出现,如果与的结果非 $0$ ,那么显然是有的,否则没有。

第二个操作有些不好办,我们再开一个 $bitset$ 集,对于一个出现过的数 $i$,在第二个 $bitset$ 集中记为 $N-i$。然后再来看操作要求,这次是让 $a+b=x$。

那么可以得到:$$a=x-b$$

于是设一个数 $z$ ,表示 $N-a$ 。

然后:$$z=N-x+b$$

移项得:$$z-b=N-x$$

于是我们将第二个 $bitset$ 右移 $N-x$ 为,显然第二个 $bitset$ 集上的第 $i$ 位代表的就是第一个 $bitset$ 上的 $x-i$ 位。

然后,将两个 $bitset$ 与一下,看看是否同时存在 $a$ 和 $x-a$ 即可。

最后对于第三个操作,貌似 bitset 也不太好搞,那么直接暴力枚举因子就好了,复杂度 $O(\sqrt{n})$,放心不会炸。具体怎么暴力枚举呢?在 $1 – \sqrt{x}$ 的范围类枚举一个 $j$ ,如果 $x$ % $j==0$ 并且同时存在 $j$ 和 $x/j$,显然就有答案了。

Code:

#include<cmath>
#include<bitset>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>

#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const int N=1e5+2;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

std::bitset<N> now1,now2; 
int n,m,l,r,s,a[N],c[N],Be[N],ans[N];
struct MO{int opt,l,r,x,id;}q[N];

inline bool cmp(MO a,MO b)
{return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;} 

inline void input(){
    IN(n),IN(m);s=sqrt(n);
    for(int i=1;i<=n;++i)IN(a[i]),Be[i]=(i-1)/s+1;
    for(int i=1;i<=m;++i)
       IN(q[i].opt),IN(q[i].l),IN(q[i].r),IN(q[i].x),q[i].id=i;
    std::sort(q+1,q+1+m,cmp);
    l=1,r=0;now1.reset(),now2.reset();
}

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(){
    input();
    for(int i=1;i<=m;++i){
        while(l<q[i].l)Del(a[l++]);
        while(l>q[i].l)Add(a[--l]);
        while(r>q[i].r)Del(a[r--]);
        while(r<q[i].r)Add(a[++r]);
        if(q[i].opt==1){
            if((now1&(now1<<q[i].x)).any())ans[q[i].id]=true;
        }else if(q[i].opt==2){
            if((now1&(now2>>(N-q[i].x))).any())ans[q[i].id]=true;
        }else if(q[i].opt==3){
            for(int j=1;j*j<=q[i].x;++j)
               if(!(q[i].x%j)&&now1[j]&&now1[q[i].x/j])
               {ans[q[i].id]=true;break;}
        }
    }
    for(int i=1;i<=m;++i)
       if(ans[i])printf("hana\n");
       else printf("bi\n"); 
    return 0;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注