社区讨论

求助大佬,30pts代码求调

P3674小清新人渣的本愿参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8it8nu
此快照首次捕获于
2023/10/27 19:19
2 年前
此快照最后确认于
2023/10/27 19:19
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int pos[N],a[N],n,m,p,cnt[N];
bool ans[N];
struct queries {
	int op,l,r,x,id;
	queries() {
		op=l=r=x=id=0;
	}
	queries(int O,int L,int R,int X,int I) {
		op=O,l=L,r=R,x=X,id=I;
	}
	bool operator < (queries x) const {
		if(pos[l]==pos[x.l])	return r<x.r;
		return l<x.l;
	}
} que[N];
bitset<N> pre,suf;
void add(int x) {
	++cnt[a[x]];
	pre.set(a[x]);
	suf.set(n-a[x]);
}
void sub(int x) {
	--cnt[a[x]];
	if(!cnt[a[x]]) {
		pre[a[x]]=0;
		suf[n-a[x]]=0;
	}
}
int main() {
	scanf("%d %d",&n,&m);
	p=sqrt(n);
	for(int i=1; i<=n; ++i)	scanf("%d",&a[i]),pos[i]=(i-1)/p+1;
	for(int i=1; i<=m; ++i) {
		int o,l,r,x,id=i;
		scanf("%d %d %d %d",&o,&l,&r,&x);
		que[i]=queries(o,l,r,x,id);
	}
	sort(que+1,que+1+m);
	for(int i=1,l=1,r=0; i<=m; ++i) {
		while(l>que[i].l)	add(--l);
		while(l<que[i].l)	sub(l++);
		while(r<que[i].r)	add(++r);
		while(r>que[i].r)	sub(r--);
		if(que[i].op==1 && (pre&(pre<<que[i].x)).any())	ans[que[i].id]=true;
		if(que[i].op==2 && (pre&(suf>>(n-que[i].x))).any())	ans[que[i].id]=true;
		if(que[i].op==3) {
			for(int j=1; j*j<=que[i].x; ++j) {
				if(que[i].x%j==0 && pre[j] && pre[que[i].x/j]) {
					ans[que[i].id]=true;
					break;
				}
			}
		}
	}
	for(int i=1; i<=m; ++i)	puts(ans[i]?"hana":"bi");
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...