题解
其实这题要不是当时在学莫队，真的没想过会用莫队解决（粗略估计一下复杂度会炸）
用bitset维护的这个想法很赞，不看题解想不出来
大概就是下面这样的一个思路
首先对于操作1，第一个bitset维护的是当前位出现与否，比如bitset[3]==1说明当前区间内，3出现过
如果说让bitset里面所有的数-x或者+x后，还有和原bitset有相同的元素的话，那么就说明有这样的数
然后对于操作2，有一个前提就是这里询问的x也是在维护的bitset的范围内
于是呢我们可以维护另一个bitset，这个bitset存的反的bitset，什么意思呢，就是如果bitset[x]==1那么说明区间内存在N-x这个数，N就是bitset维护的最大的数。
如果说让第二个bitset里的数全部+x-N后，还有和第一个bitset有相同的元素的话，那么就说明有这样的数
其实第二个bitset很巧妙，它真正要存的东西其实是相反数（请仔细理解下这是为什么），a+b=x那么a=x-b其中a由第一个bitset维护，x-b由第二个bitset维护（请仔细理解这里，这是这道题的难点）
至于操作3，枚举x的约数，O(\sqrt{N})
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<bits/stdc++.h> using namespace std; const int MAXN=100000; int n,m; bitset<MAXN+5>s1; bitset<MAXN+5>s2; int c[MAXN+5],sum[MAXN+5]; int ans[MAXN+5]; int block; struct node{ int l,r,op,id,num; }q[MAXN+5]; bool cmp(node a,node b){ return (a.r/block==b.r/block)?a.l<b.l:a.r<b.r; } inline void add(int x){ sum[c[x]]++; if(sum[c[x]]==1){//如果不写"==1"的话会被卡一个点，没搞懂为什么orz s1[c[x]]=1; s2[MAXN-c[x]]=1; } } inline void del(int x){ sum[c[x]]--; if(sum[c[x]]==0){ s1[c[x]]=0; s2[MAXN-c[x]]=0; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); } block=sqrt(n); for(int i=1;i<=m;i++){ q[i].id=i; scanf("%d%d%d%d",&q[i].op,&q[i].l,&q[i].r,&q[i].num); } sort(q+1,q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ int ql=q[i].l,qr=q[i].r; while(l<ql){ del(l); l++; } while(l>ql){ l--; add(l); } while(r<qr){ r++; add(r); } while(r>qr){ del(r); r--; } if(q[i].op==1){ if(((s1<<q[i].num)&s1).any()){ ans[q[i].id]=1; } } else if(q[i].op==2){ if((s1&(s2>>(MAXN-q[i].num))).any()){ ans[q[i].id]=1; } } else { for(int j=1;j*j<=q[i].num;j++) if(!(q[i].num%j))if(s1[j]&&s1[q[i].num/j]){ans[q[i].id]=1;break;} } } for(int i=1;i<=m;i++){ if(ans[i])printf("hana\n"); else printf("bi\n"); } return 0; } |