萌新刚学数据结构求助
查看原帖
萌新刚学数据结构求助
85142
socoolly楼主2021/1/21 19:33

Rt, 全RE了

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	register int x=0,f=0;
	register char ch=getchar();
	while(ch<'0' || ch>'9')
		f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9')
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int n,m;
const int maxn=1e5+7;
int a[maxn];
typedef long long ll;
struct sequences
{
	int l,r;
	int id,cse;
	int x;
};
sequences s[maxn];
int plas[maxn],mins[maxn],tims[maxn],divs[maxn];
int resp,resm,rest,resd;
int belong[maxn];
bool cmp(sequences i, sequences j)
{
	return belong[i.l]==belong[j.l]?i.r<j.r:belong[i.l]<belong[j.l];
}
int l=1,r; 
int add(int x)
{
	for(int i=l;i<=x;i++)
	{
		int pl=a[i]+a[x],mi=abs(a[i]-a[x]),ti=a[i]*a[x];
		int di;
		if(min(a[i],a[x])==0)
			di=-1;
		else
			di=max(a[i],a[x])%min(a[i],a[x])==0?max(a[i],a[x])/min(a[i],a[x]):-1;
		if(pl<maxn)
			plas[pl]++;
		mins[mi]++;
		if(ti<maxn)
			tims[ti]++;
		if(di!=-1)
			divs[di]++;
	}
}
int sub(int x)
{
	for(int i=l;i<=x;i++)
	{
		int pl=a[i]+a[x],mi=abs(a[i]-a[x]),ti=a[i]*a[x];
		int di;
		if(min(a[i],a[x])==0)
			di=-1;
		else
			di=max(a[i],a[x])%min(a[i],a[x])==0?max(a[i],a[x])/min(a[i],a[x]):-1;
		if(pl<maxn)
			plas[pl]--;
		mins[mi]--;	
		if(ti<maxn)	
			tims[ti]--;
		if(di!=-1)
			divs[di]--;
	}
}
bool ans[maxn];
int main()
{
	n=read(),m=read();
	int len=sqrt(n);
	int bn=ceil((double)n/len);
	for(int i=1;i<=bn;i++)
		for(int j=(i-1)*len+1;j<=i*len;j++)
			belong[j]=i;
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
		s[i].cse=read(),s[i].l=read(),s[i].r=read(),s[i].x=read(),s[i].id=i;
	sort(s+1,s+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		while(l<s[i].l) sub(l++);
		while(l>s[i].l) add(--l);
		while(r<s[i].r) add(++r);
		while(r>s[i].r) sub(r--);
		switch(s[i].cse)
		{
			case 1:
				ans[s[i].id]=mins[s[i].x];
				break;
			case 2:
				ans[s[i].id]=plas[s[i].x];
				break;
			case 3:
				ans[s[i].id]=tims[s[i].x];
				break;
			case 4:
				ans[s[i].id]=divs[s[i].x];
				break;
		}
	}
	for(int i=1;i<=m;i++)
		puts(ans[i]?"yuno":"yumi");
}
2021/1/21 19:33
加载中...