@[404Not_Found](/user/280473) 巧了,但我挂更惨,只有10pts
by LiWenX @ 2022-10-29 21:10:03
没有判 $l = r$ (悲)
by Daniel2020 @ 2022-10-29 21:12:31
悲
by hukk @ 2022-10-29 21:14:49
@[Daniel2020](/user/308379) 为什么要判呢?您是什么做法?
by 麦克斯韦の妖 @ 2022-10-29 21:17:24
@[麦克斯韦の妖](/user/255077)
维护 6 棵线段树。
所有性质 2 的点都没过(悲)
by Daniel2020 @ 2022-10-29 21:20:32
爆了 ~~~~
by pzdoeg @ 2022-10-29 21:23:12
@[Daniel2020](/user/308379)
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<algorithm>
#include<set>
#include<ctime>
#define ls o<<1
#define rs o<<1|1
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int INF=1e9+50;
const ll inf=1e18+50;
int n,m,q;
int a[N],b[N];
struct Node{
int maxx,minn;
}tr[N*4][4];
void pushup(int o,int op)
{
tr[o][op].maxx=max(tr[ls][op].maxx,tr[rs][op].maxx);
tr[o][op].minn=min(tr[ls][op].minn,tr[rs][op].minn);
}
void build(int o,int l,int r,int op)
{
if(l==r)
{
if(op==1)
{
if(a[l]>0)
{
tr[o][op].maxx=tr[o][op].minn=a[l];
}
else
{
tr[o][op].maxx=-INF;
tr[o][op].minn=INF;
}
}
else if(op==2)
{
if(a[l]<=0)
{
tr[o][op].maxx=tr[o][op].minn=a[l];
}
else
{
tr[o][op].maxx=-INF;
tr[o][op].minn=INF;
}
}
else
{
tr[o][op].maxx=tr[o][op].minn=b[l];
}
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid,op);
build(rs,mid+1,r,op);
pushup(o,op);
}
int queryI(int o,int l,int r,int L,int R,int op) // query Max
{
if(l>R || r<L) return -INF;
if(l>=L && r<=R)
{
return tr[o][op].maxx;
}
int mid=(l+r)>>1;
return max(queryI(ls,l,mid,L,R,op),queryI(rs,mid+1,r,L,R,op));
}
int queryII(int o,int l,int r,int L,int R,int op) // query Min
{
if(l>R || r<L) return INF;
if(l>=L && r<=R)
{
return tr[o][op].minn;
}
int mid=(l+r)>>1;
return min(queryII(ls,l,mid,L,R,op),queryII(rs,mid+1,r,L,R,op));
}
int main()
{
freopen("game.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]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
}
build(1,1,n,1);
build(1,1,n,2);
build(1,1,m,3);
ll ans=-inf;
for(int i=1;i<=q;i++)
{
int l1,l2,r1,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
ll maxb=queryI(1,1,m,l2,r2,3);
ll minb=queryII(1,1,m,l2,r2,3);
ll maxa1=queryI(1,1,n,l1,r1,1);
ll mina1=queryII(1,1,n,l1,r1,1);
ll maxa2=queryI(1,1,n,l1,r1,2);
ll mina2=queryII(1,1,n,l1,r1,2);
if(maxb>0 && maxa2!=-INF) ans=max(ans,maxa2*maxb);
else if(mina2!=INF) ans=max(ans,mina2*maxb);
if(minb>0 && maxa1!=-INF) ans=max(ans,minb*maxa1);
else if(mina1!=INF) ans=max(ans,minb*mina1);
printf("%lld\n",ans);
ans=-inf;
}
return 0;
}
```
同 6 棵线段树,但我 AC 啊(?
by 麦克斯韦の妖 @ 2022-10-29 21:24:22