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=,M=;

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=;i<=n;i++)scanf("%d",&a[i]),block[i]=(i-)/Block+;

    for(int i=;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+,node++m,cmp);

    for(int i=,l=,r=;i<=m;i++){

        for(;r<node[i].r;r++)cnt[a[r+]]++,f.set(a[r+]),g.set(M-a[r+]);

        for(;l>node[i].l;l--)cnt[a[l-]]++,f.set(a[l-]),g.set(M-a[l-]);

        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==){if((f&(f>>node[i].x)).any())ans[node[i].id]=;}

        else if(node[i].op==){if((f&(g>>(M-node[i].x))).any())ans[node[i].id]=;}

        else{for(int j=;j*j<=node[i].x;j++)if(node[i].x%j==)

                if(f[j]&&f[node[i].x/j]){ans[node[i].id]=;break;}

        }

    }for(int i=;i<=m;i++)puts(ans[i]?"yuno":"yumi");

}