[关闭]
@ysner 2018-04-12T15:02:10.000000Z 字数 1939 阅读 2014

Luogu3674小清新人渣的本愿

莫队 bitset


题面

给你一个序列a,长度为n,有m次操作,每次询问一个区间

知识迁移

的原理是将一大堆值为的数压成一个数。
通过等操作,我们可以快速访问数组右移位后的状态(即只剩右数个值。
数组可以当作一个数来看待并进行>>,<<,&,^等操作(详见高斯消元总结)。
还有一些函数。

解析

这题显然只能用莫队搞啊。
操作三枚枚因数就成,稳稳的。
操作一二好像会到?很耸?
发现我们询问时只要问存在性,即只有两种状态,于是可以优化一波,)强行卡过此题。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cstdlib>
  7. #include<algorithm>
  8. #include<bitset>
  9. #define ll long long
  10. #define re register
  11. #define il inline
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=1e5+10000;
  16. bitset<N>S1,S2;
  17. bool ans[N];
  18. int n,m,blk,num[N],a[N];
  19. struct Que
  20. {
  21. int id,op,l,r,x,bl;
  22. bool operator < (const Que &o){return (bl<o.bl)||(bl==o.bl&&r<o.r);}
  23. }q[N];
  24. il int gi()
  25. {
  26. re int x=0,t=1;
  27. re char ch=getchar();
  28. while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  29. if(ch=='-') t=-1,ch=getchar();
  30. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  31. return x*t;
  32. }
  33. il void add(re int x){if(!num[x]++) S1[x]=S2[100000-x]=1;}
  34. il void del(re int x){if(!--num[x]) S1[x]=S2[100000-x]=0;}
  35. int main()
  36. {
  37. n=gi();m=gi();blk=sqrt(n);
  38. fp(i,1,n) a[i]=gi();
  39. fp(i,1,m)
  40. {
  41. re int op=gi(),l=gi(),r=gi(),x=gi();
  42. q[i]=(Que){i,op,l,r,x,l/blk};
  43. }
  44. sort(q+1,q+1+m);
  45. re int L=1,R=0;
  46. fp(i,1,m)
  47. {
  48. while(L>q[i].l) add(a[--L]);
  49. while(R<q[i].r) add(a[++R]);
  50. while(L<q[i].l) del(a[L++]);
  51. while(R>q[i].r) del(a[R--]);
  52. if(q[i].op==1) ans[q[i].id]=(S1&(S1>>q[i].x)).any();
  53. if(q[i].op==2) ans[q[i].id]=(S1&(S2>>(100000-q[i].x))).any();
  54. if(q[i].op==3)
  55. fp(k,1,sqrt(q[i].x))
  56. if(q[i].x%k==0)
  57. if(S1[k]&S1[q[i].x/k]) {ans[q[i].id]=1;break;}
  58. }
  59. fp(i,1,m) ans[i]?puts("hana"):puts("bi");
  60. return 0;
  61. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注