luogu P3674 小清新人渣的本愿

时间：2022-02-15 14:30:49

传送门

毒瘤lxl

本质是莫队,关键是怎么处理询问

这里需要开两个bitset(记为\(b1,b2\)),分别存\(x\)和\(n-x\)是否出现

对于询问1,即\(x-y=z\),由于\(y=x-z\),所以要求\(x\)和\(x-z\)同时存在,相当于\(b1\&(b1<<z)\)是否有1,没有就是不存在这种情况

对于询问2,即\(x+y=z\),这里记\(w=n-y\),原式变为\(x+n-w=z\),即\(x-w=z-n\),和情况1类似,相当于要知道\(b1\&(b2>>(n-z))\)是否有1

询问3的话,\(O(\sqrt{n})\)大力枚举约数,判断是否存在即可

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

using namespace std;

const int N=100000+10;

il int rd()

{

  int x=0,w=1;char ch=0;

  while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

  while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

  return x*w;

}

int n,m,q,sz,mm[N],a[N],b[N];

bitset<N> b1,b2;

bool an[N];

struct qu

{

  int o,l,r,x,id;

  bool operator < (const qu &bb) const {return mm[l]!=mm[bb.l]?mm[l]<mm[bb.l]:mm[r]<mm[bb.r];}

}qq[N];

int main()

{

  n=rd(),q=rd();

  sz=(int)sqrt(n);

  for(int i=1;i<=n;++i) a[i]=rd(),mm[i]=i/sz;

  for(int i=1;i<=q;++i) qq[i].o=rd(),qq[i].l=rd(),qq[i].r=rd(),qq[i].x=rd(),qq[i].id=i;

  sort(qq+1,qq+q+1);

  for(int i=1,l=1,r=0;i<=q;++i)

    {

      while(r<qq[i].r)

        {

          ++r;

          ++b[a[r]];

          if(b[a[r]]==1) b1[a[r]]=b2[n-a[r]]=1;

        }

      while(r>qq[i].r)

        {

          --b[a[r]];

          if(b[a[r]]==0) b1[a[r]]=b2[n-a[r]]=0;

          --r;

        }

      while(l<qq[i].l)

        {

          --b[a[l]];

          if(b[a[l]]==0) b1[a[l]]=b2[n-a[l]]=0;

          ++l;

        }

      while(l>qq[i].l)

        {

          --l;

          ++b[a[l]];

          if(b[a[l]]==1) b1[a[l]]=b2[n-a[l]]=1;

        }

      int x=qq[i].x;

      if(qq[i].o==1) an[qq[i].id]=(b1&(b1<<x)).any();

      else if(qq[i].o==2) an[qq[i].id]=(b1&(b2>>(n-x))).any();

      else

        {

          for(int j=1;j*j<=x&&!an[qq[i].id];++j)

            if(x%j==0) an[qq[i].id]=(b[j]>0&&b[x/j]>0);

        }

    }

  for(int i=1;i<=q;i++) printf("%s\n",an[i]?"hana":"bi");

  return 0;

}

相关文章