@[lsj2009](/user/468657) 请问一下,你们是在哪里看到题的呢???
by 李卓衡001 @ 2022-10-29 21:11:39
@[李卓衡001](/user/416160) 去比赛,报名自测赛
by CarroT5656 @ 2022-10-29 21:13:04
额,其实你可以先把正解打出来再对拍. 正解是两颗线段树维护 A 和 B 的最大正值, 最小 $\ge 0$ 的值, 最大 $\le 0$ 的值, 最小负值. 然后将 A 中的每个值和 B 中每个均进行相乘取 min&max 即可.
by Fish_Clever @ 2022-10-29 21:13:39
@[lsj2009](/user/468657)
我的考场代码:
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int r()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=x*10+(ch^48),ch=getchar();
return x*f;
}
const int N=1e5+5;
int n,m,q,L,Q,j,a[N],b[N],l1,r1,l2,r2,Lx,Ln,absLn,Qx,Qn,Lmx[N][21],Lmn[N][21],Qmx[N][21],Qmn[N][21],absLmn[N][21],lg[N];
int F(int x,int y)
{
if(abs(x)<=abs(y))
return x;
return y;
}
signed main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
n=r(),m=r(),q=r();
lg[1]=0;
for(int i=2,t=max(n,m);i<=t;++i)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;++i)
absLmn[i][0]=Lmx[i][0]=Lmn[i][0]=a[i]=r();
for(int i=1;i<=m;++i)
Qmx[i][0]=Qmn[i][0]=b[i]=r();
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
Lmx[i][j]=max(Lmx[i][j-1],Lmx[i+(1<<j-1)][j-1]),
Lmn[i][j]=min(Lmn[i][j-1],Lmn[i+(1<<j-1)][j-1]);
absLmn[i][j]=F(absLmn[i][j-1],absLmn[i+(1<<j-1)][j-1]);
}
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<j)-1<=m;++i)
Qmx[i][j]=max(Qmx[i][j-1],Qmx[i+(1<<j-1)][j-1]),
Qmn[i][j]=min(Qmn[i][j-1],Qmn[i+(1<<j-1)][j-1]);
while(q--)
{
l1=r(),r1=r(),l2=r(),r2=r();
j=lg[r1-l1+1];
Lx=max(Lmx[l1][j],Lmx[r1-(1<<j)+1][j]);
Ln=min(Lmn[l1][j],Lmn[r1-(1<<j)+1][j]);
absLn=F(absLmn[l1][j],absLmn[r1-(1<<j)+1][j]);
j=lg[r2-l2+1];
Qx=max(Qmx[l2][j],Qmx[r2-(1<<j)+1][j]);
Qn=min(Qmn[l2][j],Qmn[r2-(1<<j)+1][j]);
if(Ln>=0&&Qn>=0||Lx>=0&&Ln<=0&&Qn>=0)
L=Lx,Q=Qn;
else if(Ln>=0&&Qx<=0||Lx>=0&&Ln<=0&&Qx<=0||Ln>=0&&Qx>=0&&Qn<=0)
L=Ln,Q=Qn;
else if(Lx<=0&&Qn>=0||Lx<=0&&Qx>=0&&Qn<=0)
L=Lx,Q=Qx;
else if(Lx<=0&&Qx<=0)
L=Ln,Q=Qx;
else if(Lx>=0&&Ln<=0&&Qx>=0&&Qn<=0)//这里写错了,挂了35分
{
L=absLn;
if(L<=0)
Q=Qx;
else
Q=Qn;
}
printf("%lld\n",L*Q);
}
return 0;
}
```
65pts,本来想打正解的,结果只过了特殊性质TAT
by Wither_Zilla @ 2022-10-29 21:13:48
@[Wither_Zilla](/user/203557) %%%好强
by lsj2009 @ 2022-10-29 21:16:35
@[lsj2009](/user/468657) 您更强,我T1民间才10ptsTAT
by Wither_Zilla @ 2022-10-29 21:28:16
@[zhuang1201](/user/607102) ok,谢谢!!!
by 李卓衡001 @ 2022-10-29 21:48:06