ST表RE爆零求助
查看原帖
ST表RE爆零求助
550995
OberNotFound楼主2022/10/30 17:23

主要的报错信息是Segmentation fault - invalid memory reference Code:

#include <bits/stdc++.h>
using namespace std;
int closer_to_0(int x,int y)
{
	return ((abs(x)<=abs(y))?x:y);
}
int n,m,q,amax[100005][33],amin[100005][33],bmax[100005][33],bmin[100005][33],apct0[100005][33],anct0[100005][33];
int A[100005],B[100005],Log[100005];
vector <int> a0;
void init(void)
{
	for(int i=2;i<=n;++i)
	{
		Log[i]=Log[i>>1]+1;
	}
	for(int i=1;i<=n;++i)
	{
		amax[i][0]=amin[i][0]=A[i];
		if(A[i]>=0)
		{
			apct0[i][0]=A[i];
		}
		else
		{
			apct0[i][0]=INT_MAX;
		}
		if(A[i]<=0)
		{
			anct0[i][0]=A[i];
		}
		else
		{
			anct0[i][0]=-INT_MAX;
		}
		bmax[i][0]=bmin[i][0]=B[i];
	}
	for(int j=1;j<Log[n];++j)
	{
		for(int i=1;i+(1<<(j))<=n+1;++i)
		{
			amax[i][j]=max(amax[i][j-1],amax[i+(1<<(j-1))][j-1]);
			amin[i][j]=min(amin[i][j-1],amin[i+(1<<(j-1))][j-1]);
			bmax[i][j]=max(bmax[i][j-1],bmax[i+(1<<(j-1))][j-1]);
			bmin[i][j]=min(bmin[i][j-1],bmin[i+(1<<(j-1))][j-1]);
			apct0[i][j]=closer_to_0(apct0[i][j-1],apct0[i+(1<<(j-1))][j-1]);
			anct0[i][j]=closer_to_0(anct0[i][j-1],anct0[i+(1<<(j-1))][j-1]);
		}
	}
}
inline int query_amax(int l,int r)
{
	int len=r-l+1;assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return max(amax[l][Log[len]-1],amax[r-(1<<(Log[len]-1))][Log[len]-1]);
}
inline int query_amin(int l,int r)
{
	int len=r-l+1;assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return min(amin[l][Log[len]-1],amin[r-(1<<(Log[len]-1))][Log[len]-1]);
}
inline int query_bmax(int l,int r)
{
	int len=r-l+1;
	assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return max(bmax[l][Log[len]-1],bmax[r-(1<<(Log[len]-1))][Log[len]-1]);
}
inline int query_bmin(int l,int r)
{
	int len=r-l+1;assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return min(bmin[l][Log[len]-1],bmin[r-(1<<(Log[len]-1))][Log[len]-1]);
}
inline int query_apct0(int l,int r)
{
	int len=r-l+1;assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return closer_to_0(apct0[l][Log[len]-1],apct0[r-(1<<(Log[len]-1))][Log[len]-1]);
}
inline int query_anct0(int l,int r)
{
	int len=r-l+1;assert(l>-1&&r>-1&&Log[len]-1>-1);
	assert(l<100005&&r-(1<<(Log[len]-1))<100005&&Log[len]-1<33);
	return closer_to_0(anct0[l][Log[len]-1],anct0[r-(1<<(Log[len]-1))][Log[len]-1]);
}
signed main()
{
	// freopen("game3.in","r",stdin);
	// freopen("game.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",A+i);
		if(A[i]==0)
		{
			a0.emplace_back(i);
		}
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d",B+i);
		
	}
	init();
	while(q--)
	{
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		bool ahave0=0;
		int qamax=query_amax(l1,r1),
		qamin=query_amin(l1,r1),
		qbmax=query_bmax(l2,r2),
		qbmin=query_bmin(l2,r2),
		qapct0=query_apct0(l1,r1),
		qanct0=query_anct0(l1,r1);
		if(*lower_bound(a0.begin(),a0.end(),l1)<=r1)
		{
			ahave0=1;
		}
		if(qbmin>0)
		{
			printf("%d\n",qbmin*qamax);

		}
		else if(qbmax<0)
		{
			printf("%d\n",qbmax*qamin);

		}
		else if(qbmin==0&&qbmax==0||ahave0)
		{
			printf("0\n");

		}
		else
		{
			int p1=qapct0,q1=qbmin,p2=qanct0,q2=qbmax;
			printf("%d\n",max(p1*q1,p2*q2));

		}
	}
}


2022/10/30 17:23
加载中...