darkbzoj ac 洛谷21pt 求助
查看原帖
darkbzoj ac 洛谷21pt 求助
170882
rrrrr楼主2021/3/27 14:49
#include<bits/stdc++.h>
using namespace std;
int mv,cpt,pr[100500],an[100500],ans[100500],n,m,v[100500],w[100050],bl[100050],bk,mn=100000,cnt;
struct abc
{
	int k,l,r,x,i;
}u[100050],t[100500];
bitset<100050> a,b;
bool cmp(abc a,abc b)
{
	if(bl[a.l]==bl[b.l])return a.r<b.r;
	return a.l<b.l;
}
bool cmb(abc a,abc b)
{
	return a.x<b.x;
}
void up(int x,int k)
{
	w[v[x]]+=k;
	if(k==-1&&w[v[x]]==0)
	a[v[x]]=b[mn-v[x]]=0;
	if(k==1&&w[v[x]]>0)
	a[v[x]]=b[mn-v[x]]=1;
}
inline int read()
{
    int x=0;bool f=0;char c=getchar();
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar()) x=(x*10)+(c^48);
    if(f)x=-x;return x;
}
int main()
{
//	freopen("4.in","r",stdin);
	n=read(),mv=m=read();bk=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		v[i]=read();
		bl[i]=i/bk+1;
	}
	for(int i=1;i<=m;i++)
	{
		int k=read(),l=read(),r=read(),x=read();
		if((k==4)&&(x*x<=n)&&x!=0)
		t[++cpt]=(abc){k,l,r,x,i};
		else u[++cnt]=(abc){k,l,r,x,i};
	}
	m=cnt;
	sort(u+1,u+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l<u[i].l)up(l++,-1);
		while(l>u[i].l)up(--l,1);
		while(r<u[i].r)up(++r,1);
		while(r>u[i].r)up(r--,-1);
		if(u[i].k==1)
		{
			if((a&(a<<u[i].x)).any())
			ans[u[i].i]=1;
		}
		if(u[i].k==2)
		{
			if((a&(b>>mn-u[i].x)).any())
			ans[u[i].i]=1;
		}
		if(u[i].k==3)
		{
			for(int j=1;j*j<=u[i].x;j++)
			{
				if(u[i].x%j==0)
				if(a[j]&&a[u[i].x/j])
				ans[u[i].i]=1;
			}
			if(u[i].x==0)
			if(a[0])ans[u[i].i]=1;
		}
		if(u[i].k==4)
		{
			if(u[i].x==0)
			{
				if(a[0]&&a.count()>1)
				ans[u[i].i]=1;
			}
			else 
			for(int j=1;j*u[i].x<=100000;j++)
			{
				if(a[j]&&a[j*u[i].x])ans[u[i].i]=1;
			}
		}
	}
	sort(t+1,t+cpt+1,cmb);
	int tl=1;
	for(int i=1;i<=bk;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i*v[j]<=100000)
			pr[i*v[j]]=j;
		}
		for(int j=1;j<=n;j++)
		{
			an[j]=max(pr[v[j]],an[j-1]);
		}
		while(t[tl].x<i&&tl<cpt)tl++;
		while(t[tl].x==i&&tl<cpt)
		{
			if(an[t[tl].r]>=t[tl].l)
			ans[t[tl].i]=1;
			tl++;
		}
		if(tl==cpt)break;
		memset(pr,0,sizeof(pr));
		memset(an,0,sizeof(an));
	}
	for(int i=1;i<=mv;i++)
	{
		if(ans[i])cout<<"yuno\n";
		else cout<<"yumi\n";
	}
}
2021/3/27 14:49
加载中...