51pts TLE+RE 求助
查看原帖
51pts TLE+RE 求助
536745
WaTleZero_pt楼主2025/1/8 21:26

看不出来哪里有问题qwq

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int n,m,a[N+5];
int cnt[N+5];
bitset<N+5> L,R,tmp;
struct Query{
	int id,op,l,r,x;
}q[N+5];
int bklen;
bool cmp(Query a,Query b){
	return a.l/bklen==b.l/bklen?a.r<b.r:a.l<b.l;
}
bool ans[N+5];
void add(int x){
	if(!cnt[x]) L[x]=1,R[N-x]=1;
	cnt[x]++;
}
void del(int x){
	cnt[x]--;
	if(!cnt[x]) L[x]=0,R[N-x]=0;
}
vector<int> nq[N+5];
void mo(){
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(r<q[i].r) add(a[++r]);
		while(l>q[i].l) add(a[--l]);
		while(r>q[i].r) del(a[r--]);
		while(l<q[i].l) del(a[l++]);
		if(q[i].op==2){
			tmp=L&(R>>(N-q[i].x));
			ans[q[i].id]=tmp.any();
		}else if(q[i].op==1){
			tmp=L&(L<<q[i].x);
			ans[q[i].id]=tmp.any();
		}else if(q[i].op==3){
			for(int j=1;j*j<=q[i].x;j++)
				if(q[i].x%j==0&&cnt[j]&&cnt[q[i].x/j])
					ans[q[i].id]=1;
		}else if(q[i].op==4){
			if(q[i].x>=316){
				for(int j=1;j*q[i].x<=N;i++)
					ans[q[i].id]|=cnt[j]&&cnt[j*q[i].x];
			}else nq[q[i].r].push_back(i);
		}
	}
}
int val[N+5];
void op4(){
	for(int T=1;T<=315;T++){
		memset(val,0,sizeof(val));
		int mx=0;
		for(int i=1;i<=n;i++){
			if(a[i]%T==0) mx=max(mx,val[a[i]/T]);
			if(a[i]*T<=N) mx=max(mx,val[a[i]*T]);
			val[a[i]]=i;
			if(T==1) mx=i;
			for(int j:nq[i]){
				if(q[j].x==T&&mx>=q[j].l)
					ans[q[j].id]=1;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	bklen=n/sqrt(m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&q[i].op,&q[i].l,&q[i].r,&q[i].x);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	mo(); op4();
	for(int i=1;i<=m;i++)
		printf(ans[i]?"yuno\n":"yumi\n");
	return 0;
}
2025/1/8 21:26
加载中...