題面
洛谷,自己去看去,太長了
題解
很顯然的莫隊。
但是怎麼查詢那幾個詢問。
對于詢問乘積,顯然可以暴力枚舉因數(反正加起來也是 O(nn√) 的
對于加減????暴力顯然 GG
是以我們來用 bitset 玄學優化一下。。。
然後就能 AC 了
時間複雜度?
大概是 O(n2/64) 吧。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
#define ll long long
#define RG register
#define MAX 111111
inline int read()
{
RG int x=,t=;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-,ch=getchar();
while(ch<='9'&&ch>='0')x=x*+ch-,ch=getchar();
return x*t;
}
const int MN=;
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.lb<b.lb;return a.r<b.r;}
int num[MAX],a[MAX],n,m,blk;
bool ans[MAX],vis[MAX];
void add(int x){if(!num[x]++)S1[x]=S2[MN-x]=;}
void del(int x){if(!--num[x])S1[x]=S2[MN-x]=;}
int main()
{
n=read();m=read();blk=sqrt(n);
for(int i=;i<=n;++i)a[i]=read();
for(int i=;i<=m;++i)
{
int opt=read(),l=read(),r=read(),x=read();
q[i]=(query){i,opt,l,r,x,l/blk};
}
sort(&q[],&q[m+]);
int L=,R=;
for(int i=;i<=m;++i)
{
while(L>q[i].l)add(a[--L]);
while(R<q[i].r)add(a[++R]);
while(L<q[i].l)del(a[L++]);
while(R>q[i].r)del(a[R--]);
if(q[i].opt==)ans[q[i].id]=(S1&(S1>>q[i].x)).any();
if(q[i].opt==)ans[q[i].id]=(S1&(S2>>(MN-q[i].x))).any();
if(q[i].opt==)
for(int k=;k*k<=q[i].x;++k)
if(q[i].x%k==)
if(S1[k]&S1[q[i].x/k]){ans[q[i].id]=true;break;}
}
for(int i=;i<=m;++i)ans[i]?puts("hana"):puts("bi");
return ;
}