RT
一个在infoj上25pts的假算法ccf给我100
tg B game
code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=3e5+5,inf=LONG_LONG_MAX;
ll n,m,q;
ll a[MAXN],b[MAXN];
ll max_a1[MAXN][25],min_a1[MAXN][25],max_b1[MAXN][25],min_b1[MAXN][25];
ll max_a2[MAXN][25],min_a2[MAXN][25],max_b2[MAXN][25],min_b2[MAXN][25];
ll sum_a[MAXN];
ll l1,r1,l2,r2;
ll get_max_a1(ll l,ll r){
	ll len=r-l+1;
	ll ans=-inf;
	while(len){
		ans=max(ans,max_a1[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_min_a1(ll l,ll r){
	ll len=r-l+1;
	ll ans=inf;
	while(len){
		ans=min(ans,min_a1[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_max_b1(ll l,ll r){
	ll len=r-l+1;
	ll ans=-inf;
	while(len){
		ans=max(ans,max_b1[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_min_b1(ll l,ll r){
	ll len=r-l+1;
	ll ans=inf;
	while(len){
		ans=min(ans,min_b1[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}

ll get_max_a2(ll l,ll r){
	ll len=r-l+1;
	ll ans=-inf;
	while(len){
		ans=max(ans,max_a2[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_min_a2(ll l,ll r){
	ll len=r-l+1;
	ll ans=inf;
	while(len){
		ans=min(ans,min_a2[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_max_b2(ll l,ll r){
	ll len=r-l+1;
	ll ans=-inf;
	while(len){
		ans=max(ans,max_b2[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
ll get_min_b2(ll l,ll r){
	ll len=r-l+1;
	ll ans=inf;
	while(len){
		ans=min(ans,min_b2[l][(ll)log2(len)]);
		l+=1ll<<(ll)log2(len);
		len=len-(1ll<<(ll)log2(len));
	}
	return ans;
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	for(int i=1;i<=n;i++)max_a1[i][0]=max(a[i],0ll),min_a1[i][0]=(a[i]<=0?inf:a[i]),sum_a[i]=sum_a[i-1]+(a[i]==0);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			max_a1[i][j]=max(max_a1[i][j-1],max_a1[min(i+(1ll<<(j-1)),n)][j-1]);
			min_a1[i][j]=min(min_a1[i][j-1],min_a1[min(i+(1ll<<(j-1)),n)][j-1]);
		}
	}
	for(int i=1;i<=m;i++)max_b1[i][0]=max(b[i],0ll),min_b1[i][0]=(b[i]<=0?inf:b[i]);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=m;i++){
			max_b1[i][j]=max(max_b1[i][j-1],max_b1[min(i+(1ll<<(j-1)),m)][j-1]);
			min_b1[i][j]=min(min_b1[i][j-1],min_b1[min(i+(1ll<<(j-1)),m)][j-1]);
		}
	}

	for(int i=1;i<=n;i++)max_a2[i][0]=(a[i]>=0?-inf:a[i]),min_a2[i][0]=(a[i]>=0?inf:a[i]);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			max_a2[i][j]=max(max_a2[i][j-1],max_a2[min(i+(1ll<<(j-1)),n)][j-1]);
			min_a2[i][j]=min(min_a2[i][j-1],min_a2[min(i+(1ll<<(j-1)),n)][j-1]);
		}
	}
	for(int i=1;i<=m;i++)max_b2[i][0]=(b[i]>=0?-inf:b[i]),min_b2[i][0]=(b[i]>=0?inf:b[i]);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=m;i++){
			max_b2[i][j]=max(max_b2[i][j-1],max_b2[min(i+(1ll<<(j-1)),m)][j-1]);
			min_b2[i][j]=min(min_b2[i][j-1],min_b2[min(i+(1ll<<(j-1)),m)][j-1]);
		}
	}
	// for(int i=1;i<=m;i++){
	// 	for(int j=0;j<=3;j++){
	// 		cout<<min_b1[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	// cout<<"------------"<<endl;
	for(int i=1;i<=q;i++){
		cin>>l1>>r1>>l2>>r2;
		ll MAXA1=get_max_a1(l1,r1),MINA1=get_min_a1(l1,r1),MAXB1=get_max_b1(l2,r2),MINB1=get_min_b1(l2,r2);
		ll MAXA2=get_max_a2(l1,r1),MINA2=get_min_a2(l1,r1),MAXB2=get_max_b2(l2,r2),MINB2=get_min_b2(l2,r2);
		// cout<<MAXA1<<" "<<MINA1<<" "<<MAXB1<<" "<<MINB1<<endl;
		// cout<<MAXA2<<" "<<MINA2<<" "<<MAXB2<<" "<<MINB2<<endl;
		ll ans=-inf;
		if(MAXA1>0){//A有正数
			if(MINB2<0)ans=max(ans,MINA1*MINB2);
			else if(MAXB1>0)ans=max(ans,MAXA1*MINB1);
			else ans=max(ans,0ll);
		}
		if(MINA2<0){//A有负数
			if(MAXB1>0)ans=max(ans,MAXA2*MAXB1);
			else if(MINB2<0)ans=max(ans,MINA2*MAXB2);
			else ans=max(ans,0ll);
		}
		if(sum_a[r1]-sum_a[l1-1])ans=max(ans,0ll);
		cout<<ans<<endl;
	}
	return 0;
}

这很难卡吗？几个0不就卡掉了