mxqz 莫队
查看原帖
mxqz 莫队
358739
BFSDFS123楼主2023/2/19 11:50

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;
}
2023/2/19 11:50
加载中...