RT,一直是 51 分,明显是除法写挂了。
但是自己手造了几组数据,拿着题解代码对拍了好几组,都没有出现问题
求大佬看看
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eps 1e-8
const int inf=0x3f3f3f3f;
const int Maxn=1e5+10;
bitset<Maxn> s1,s2;
int Ar[Maxn];
int n,m;
int tong[Maxn];
const int Max=1e5;
const int lim=sqrt(Max);
struct Queris{
int opt;
int l,r;
int x;
int id;
}q[Maxn];
int belong[Maxn],block;
bool cmp(Queris a,Queris b)
{
if(belong[a.l]==belong[b.l])
{
if(belong[a.l]&1)
{
return a.r<b.r;
}
return a.r>b.r;
}
return belong[a.l]<belong[b.l];
}
void add(int pos)
{
// cout<<"pos="<<pos<<endl;
if(tong[Ar[pos]]==0)
{
// cout<<"s1["<<Ar[pos]<<"]"<<"=1,s2["<<Max-Ar[pos]<<"]=1"<<endl;
s1[Ar[pos]]=s2[Max-Ar[pos]]=1;
}
tong[Ar[pos]]++;
}
void del(int pos)
{
// cout<<"pos="<<pos<<endl;
tong[Ar[pos]]--;
if(tong[Ar[pos]]==0)
{
// cout<<"s1["<<Ar[pos]<<"]"<<"=0,s2["<<Max-Ar[pos]<<"]=0"<<endl;
s1[Ar[pos]]=s2[Max-Ar[pos]]=0;
}
}
int ans[Maxn];
vector<Queris> vc[lim+10];
int pos[Maxn],cnt[Maxn];
void work()
{
for(int i=1;i<=lim;i++)
{
if(vc[i].size()==0)
{
continue;
}
memset(pos,0,sizeof(pos));
memset(cnt,0,sizeof(cnt));
int maxx=0;
for(int j=1;j<=n;j++)
{
pos[Ar[j]]=j;
if(Ar[j]%i==0)
{
maxx=max(maxx,pos[Ar[j]/i]);
}
if(Ar[j]*i<=Max)
{
maxx=max(maxx,pos[Ar[j]*i]);
}
cnt[j]=maxx;
}
for(auto now:vc[i])
{
if(now.l>cnt[now.r])
{
ans[now.id]=false;
}else{
ans[now.id]=true;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
block=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&Ar[i]);
belong[i]=(i-1)/block+1;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x);
q[i].id=i;
if(q[i].opt==4 && q[i].x<=lim)
{
vc[q[i].x].push_back(q[i]);
}
}
work();
sort(q+1,q+1+m,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
// cout<<"id="<<q[i].id<<",["<<q[i].l<<","<<q[i].r<<"],opt="<<q[i].opt<<":"<<q[i].x<<"\n";
int x=q[i].x;
if(q[i].opt==4 && x<=lim)
{
continue;
}
while(q[i].l<l)
{
add(--l);
}
while(q[i].r>r)
{
add(++r);
}
while(q[i].l>l)
{
del(l++);
}
while(q[i].r<r)
{
del(r--);
}
// cout<<(s1)<<"\n"<<(s2)<<endl;
if(q[i].opt==1) // 差操作
{
if((s1&(s1<<q[i].x)).any()==true)
{
ans[q[i].id]=1;
}else{
ans[q[i].id]=0;
}
}else if(q[i].opt==2){ // 加操作
if(((s1&(s2>>(Max-q[i].x))).any())==true)
{
ans[q[i].id]=1;
}else{
ans[q[i].id]=0;
}
}else if(q[i].opt==3){ // 乘操作
ans[q[i].id]=0;
for(int j=1;j*j<=q[i].x;j++)
{
if(q[i].x%j==0)
{
if(tong[q[i].x/j]>=1 && tong[j]>=1)
{
ans[q[i].id]=1;
}
}
}
}else{
// cout<<"jer"<<endl;
for(int j=1;j<=Max;j++)
{
if(j*x>Max)
{
break;
}
if(tong[j]==1 && tong[j*x]==1)
{
ans[q[i].id]=1;
break;
}
}
}
}
for(int i=1;i<=m;i++)
{
puts(ans[i]?"yuno":"yumi");
}
return 0;
}