BZOJ4810: [Ynoi2017]由乃的玉米田【bitset+莫队】

4810: [Ynoi2017]由乃的玉米田

【题目描述】

传送门

【题解】

bitset巧妙的用法。
我们用bitset s存下每一位,对于A-B=x(A,B \in s)的情况,只需要判断s\&(s>>x)是否为1就可以了。

那么加法怎么办,我们知道A+B=A-(-B),那么就可以设fs表示-s,第i为表示是否有-(MAXN-i),然后只要判断s\&(fs>>(MAXN-x))就可以了。

对于乘法,那么直接枚举约数就可以了。

当然对于每个区间这么维护肯定不行,所以用莫队就好了。

复杂度O(m*(\sqrt{n}+\frac{m}{32}))

代码如下

#include<cmath>
#include<cstdio>
#include<bitset>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=100000;
int n,m,Ans[MAXN+5],K,a[MAXN+5],hsh[MAXN+5];
struct xcw{
    int typ,L,R,x,id;
    bool operator <(const xcw b)const{return (L/K<b.L/K||(L/K==b.L/K&&R<b.R));}
}W[MAXN+5];
bitset<MAXN+5> s,fs;
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
void Add(int x){hsh[a[x]]++;if(hsh[a[x]]==1) s[a[x]]=1,fs[MAXN-a[x]]=1;}
void Del(int x){hsh[a[x]]--;if(!hsh[a[x]]) s[a[x]]=0,fs[MAXN-a[x]]=0;}
int main(){
    n=read(),m=read();K=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) W[i]=(xcw){read(),read(),read(),read(),i};
    sort(W+1,W+1+m);
    for(int i=1,L=1,R=0;i<=m;i++){
        while(L<W[i].L) Del(L++);
        while(L>W[i].L) Add(--L);
        while(R<W[i].R) Add(++R);
        while(R>W[i].R) Del(R--);
        if(W[i].typ==1) Ans[W[i].id]=(s&(s>>W[i].x)).any();else
        if(W[i].typ==2) Ans[W[i].id]=(s&(fs>>(MAXN-W[i].x))).any();else{
            int x=sqrt(W[i].x);
            for(int j=1;j<=x;j++)
            if(W[i].x%j==0) Ans[W[i].id]|=s[W[i].x/j]&&s[j];
        }
    }
    for(int i=1;i<=m;i++) printf(Ans[i]?"yuno\n":"yumi\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部