您的位置:首页 > 博客中心 > 互联网 >

【洛谷3674】小清新人渣的本愿(莫队,bitset)

时间:2022-05-05 01:28

【洛谷3674】小清新人渣的本愿(莫队,bitset)

题面

题解

很显然的莫队。
但是怎么查询那几个询问。
对于询问乘积,显然可以暴力枚举因数(反正加起来也是\(O(n\sqrt{n})\)的
对于加减????暴力显然\(GG\)
所以我们来用\(bitset\)玄学优化一下。。。
然后就能\(AC\)了
时间复杂度?
大概是\(O(n^2/64)\)吧。。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MAX 111111
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
const int MN=100000;
bitset<100005> S1,S2;
struct query{int id,opt,l,r,x,lb;}q[MAX];
bool operator<(query a,query b){if(a.lb!=b.lb)return a.lbq[i].l)add(a[--L]);
        while(Rq[i].r)del(a[R--]);
        if(q[i].opt==1)ans[q[i].id]=(S1&(S1>>q[i].x)).any();
        if(q[i].opt==2)ans[q[i].id]=(S1&(S2>>(MN-q[i].x))).any();
        if(q[i].opt==3)
            for(int k=1;k*k<=q[i].x;++k)
                if(q[i].x%k==0)
                    if(S1[k]&S1[q[i].x/k]){ans[q[i].id]=true;break;}
    }
    for(int i=1;i<=m;++i)ans[i]?puts("hana"):puts("bi");
    return 0;
}

热门排行

今日推荐

热门手游