BZOJ4810
巧妙地利用
bitset
。
QAQ
可能只是我弱没看出来。 莫队还是很容易看出来的。 然后就是统计一下每一个值出现的个数。用
cnt
数组记录。 对于操作3乘法而言，直接枚举因数，暴力判断一下就可以了。 用一个
bitsetf
记录每个值是否出现过。 那么对于操作1减法来说，就直接将
f
左移x位，然后且上原集
f
，判断是否有交就可以了。这个应该还比较好理解。相当于就是寻找是否存在差为x的两个值嘛。 然而对于操作2加法来说，求和就不能一个
bitset
解决了。 差值好求，和不好求，那么考虑将求和转为求差。那么记录一个最大值
Mx
每次求
ai+aj=x
可以转化为
ai=(Mx−aj)+x−Mx
如此，就可以维护一个倒着的，
bitsetg
，如，加入值
ai
，那么
fai=1
,
gMx−ai=1
，每次将
g
左移x−Mx与
f
求且，或者f左移
Mx−x
位与
g
<script type="math/tex" id="MathJax-Element-6966">g</script>求且就可以了。而且题目还说了同一个位子可以取两次。QAQ真和善。
【代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
#define N 100005
#define mod 1000000007
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
ll read()
{
ll x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)){
if(ch==
'-') f=-
1;ch=getchar();}
while(
isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
int n,m,block,Mx,L,R;
int a[N],cnt[N],bl[N],ans[N];
bitset<N>f,g,h;
class Query{
public:
int f,l,r,x,id;
Query(){}
Query(
int ff,
int ll,
int rr,
int xx,
int ii) {
f=ff,l=ll,r=rr,x=xx,id=ii;
}
}Q[N];
bool operator <(Query a,Query b){
return bl[a.l]<bl[b.l]||(bl[a.l]==bl[b.l]&&a.r<b.r);
}
void Add(
int x)
{
cnt[x]++;
if(cnt[x]==
1) f[x]=
1,g[Mx-x]=
1;
}
void Delete(
int x)
{
cnt[x]--;
if(!cnt[x]) f[x]=
0,g[Mx-x]=
0;
}
int Solve_Minus(
int x){
return ((f<<x)&f).count()!=
0?
1:
0;
}
int Solve_Plus(
int x){
return ((f<<(Mx-x))&g).count()!=
0?
1:
0;
}
int Solve_Multi(
int x){
for(
int i=
1;i*i<=x;i++)
if(x%i==
0) {
if(cnt[i]&&cnt[x/i])
return 1;
}
return 0;
}
void Get_Ans(
int x)
{
if(Q[x].f==
1) ans[Q[x].id]=Solve_Minus(Q[x].x);
else if(Q[x].f==
2) ans[Q[x].id]=Solve_Plus(Q[x].x);
else ans[Q[x].id]=Solve_Multi(Q[x].x);
}
int main()
{
n=read(),m=read();block=(
int)
sqrt(n);Mx=N-
1;
for(
int i=
1;i<=n;i++) a[i]=read(),bl[i]=(i-
1)/block+
1;
for(
int i=
1;i<=m;i++)
Q[i].f=read(),Q[i].l=read(),Q[i].r=read(),Q[i].x=read(),Q[i].id=i;
sort(Q+
1,Q+
1+m);
for(
int i=Q[
1].l;i<=Q[
1].r;i++) Add(a[i]);
Get_Ans(
1);
L=Q[
1].l,R=Q[
1].r;
for(
int i=
2;i<=m;i++)
{
while(L<Q[i].l) Delete(a[L++]);
while(R<Q[i].r) Add(a[++R]);
while(L>Q[i].l) Add(a[--L]);
while(R>Q[i].r) Delete(a[R--]);
Get_Ans(i);
}
for(
int i=
1;i<=m;i++)
printf(ans[i]?
"yuno\n":
"yumi\n");
return 0;
}
