首页 > 代码库 > BZOJ 4810 莫队+bitset
BZOJ 4810 莫队+bitset
思路:
看完这道题根本没有思路啊....
然后我就膜拜了一波题解...
这神tm乱搞思路
维护两个bitset
第一个bitset代表当前区间哪些数出现过
第二个bitset是 maxp-p出现过
差为x的时候 就用第一个bitset与一下它右移x就好了
和为x的时候 就第一个bitset与一下第二个bitset右移maxp-x
乘积为x的时候 就枚举约数,, 暴力判断一下
复杂度是O(nsqrt(n)+n^2/32)的
//By SiriusRen#include <cmath>#include <bitset>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=100050,M=100000;int n,m,a[N],Block,block[N],cnt[N],ans[N];bitset<N>f,g;struct Node{int op,l,r,x,id;}node[N];bool cmp(Node a,Node b){ if(block[a.l]==block[b.l])return a.r<b.r; return a.l<b.l;}int main(){ scanf("%d%d",&n,&m),Block=sqrt(n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),block[i]=(i-1)/Block+1; for(int i=1;i<=m;i++)scanf("%d%d%d%d",&node[i].op,&node[i].l,&node[i].r,&node[i].x),node[i].id=i; sort(node+1,node+1+m,cmp); for(int i=1,l=1,r=0;i<=m;i++){ for(;r<node[i].r;r++)cnt[a[r+1]]++,f.set(a[r+1]),g.set(M-a[r+1]); for(;l>node[i].l;l--)cnt[a[l-1]]++,f.set(a[l-1]),g.set(M-a[l-1]); for(;l<node[i].l;l++){cnt[a[l]]--;if(!cnt[a[l]])f.reset(a[l]),g.reset(M-a[l]);} for(;r>node[i].r;r--){cnt[a[r]]--;if(!cnt[a[r]])f.reset(a[r]),g.reset(M-a[r]);} if(node[i].op==1){if((f&(f>>node[i].x)).any())ans[node[i].id]=1;} else if(node[i].op==2){if((f&(g>>(M-node[i].x))).any())ans[node[i].id]=1;} else{for(int j=1;j*j<=node[i].x;j++)if(node[i].x%j==0) if(f[j]&&f[node[i].x/j]){ans[node[i].id]=1;break;} } }for(int i=1;i<=m;i++)puts(ans[i]?"yuno":"yumi");}
BZOJ 4810 莫队+bitset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。