@[olkieler](/user/466525)
a,b 两棵线段树其实是一样的
为什么你的 b 没搞负数的最值
by xingke233 @ 2022-11-19 10:30:53
@[xingke233](/user/533452)
为什么是一样的？
b 只需维护最大值与最小值啊。
by Texas_the_Omertosa @ 2022-11-19 10:36:44
@[xingke233](/user/533452) 两棵线段树分别维护两个数组的信息。
by Texas_the_Omertosa @ 2022-11-19 10:37:21
@[olkieler](/user/466525)
a,b 都要记录4个最值
by xingke233 @ 2022-11-19 10:39:03
@[olkieler](/user/466525)
我写的分类讨论是要用到的
by xingke233 @ 2022-11-19 10:39:49
@[olkieler](/user/466525)
build 函数改了一下
分类讨论改了
```
#include <bits/stdc++.h>
#define int long long
#define N 100005
#define M 100005
#define mod 1000000007
#define ios ios::sync_with_stdio(0);cin.tie(0)
#define test cout << "ASDF\n"
#define inf 1e18
#define linf LLONG_MAX
#define pint pair<int, int>
#define mp make_pair
using namespace std;
struct anode
{
int l;
int r;
int maxx;
int minn;
int fmax;
int zmin;
};
int a[N];
int b[M];
inline void print(int x){
char F[400];int cnt=0;
if(x==0){putchar('0');putchar('\n');return ;}
if(x<0){putchar('-');x=-x;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt) putchar(F[cnt--]+'0');
putchar('\n');return ;
}
struct ST{
anode atree[N << 2];
inline int lson(int x)
{
return x << 1;
}
inline int rson(int x)
{
return x << 1 | 1;
}
inline void apushup(int rk)
{
atree[rk].maxx = max(atree[lson(rk)].maxx, atree[rson(rk)].maxx);
atree[rk].minn = min(atree[lson(rk)].minn, atree[rson(rk)].minn);
atree[rk].fmax = max(atree[lson(rk)].fmax, atree[rson(rk)].fmax);
atree[rk].zmin = min(atree[lson(rk)].zmin, atree[rson(rk)].zmin);
}
inline void abuild(int rk, int l, int r,int k)
{
atree[rk].l = l;
atree[rk].r = r;
atree[rk].minn=atree[rk].zmin=1e18;
atree[rk].fmax=atree[rk].maxx=-1e18;
if (l == r)
{
if(k){
if(a[l]>=0) atree[rk].minn=atree[rk].maxx=a[l];
else atree[rk].zmin=atree[rk].fmax=a[l];
}else{
if(b[l]>=0) atree[rk].minn=atree[rk].maxx=b[l];
else atree[rk].zmin=atree[rk].fmax=b[l];
}
return ;
}
int mid = l + r >> 1;
abuild(lson(rk), l, mid,k);
abuild(rson(rk), mid + 1, r,k);
apushup(rk);
}
inline anode aquery(int rk, int l, int r)
{
if (l <= atree[rk].l && r >= atree[rk].r)
{
return atree[rk];
}
int mid = atree[rk].l + atree[rk].r >> 1;
if (r <= mid)
{
return aquery(lson(rk), l, r);
}
if (l > mid)
{
return aquery(rson(rk), l, r);
}
anode ltree = aquery(lson(rk), l, r), rtree = aquery(rson(rk), l, r), ls;
ls.maxx = max(ltree.maxx, rtree.maxx);
ls.minn = min(ltree.minn, rtree.minn);
ls.fmax = max(ltree.fmax, rtree.fmax);
ls.zmin = min(ltree.zmin, rtree.zmin);
return ls;
}
} t1,t2;
inline void query(int l1, int r1, int l2, int r2)
{
anode x0 = t1.aquery(1, l1, r1);
anode x1 = t2.aquery(1, l2, r2);
if(x1.zmin==1e18){
if(x0.minn==1e18){
print(x0.fmax*x1.maxx);
}else{
print(x0.maxx*x1.minn);
}
}else{
if(x1.minn==1e18){
if(x0.minn==1e18){
print(x0.zmin*x1.fmax);
}else{
if(x0.zmin==1e18){
print(x0.minn*x1.zmin);
}else{
print(x0.zmin*x1.fmax);
}
}
}else{
if(x0.minn==1e18){
print(x0.fmax*x1.maxx);
}else{
if(x0.zmin==1e18){
print(x0.minn*x1.zmin);
}else{
print(max(x0.minn*x1.zmin,x0.fmax*x1.maxx));
}
}
}
}
return ;
}
signed main()
{
ios;
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
}
for (int i = 1; i <= m; i ++)
{
cin >> b[i];
}
t1.abuild(1, 1, n,1);
t2.abuild(1, 1, m,0);
for (int i = 1; i <= q; i ++)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
query(l1, r1, l2, r2);
}
return 0;
}
```
by xingke233 @ 2022-11-19 10:43:14
@[xingke233](/user/533452) 我的分类讨论是看题解的，大佬您的是什么样的？
by Texas_the_Omertosa @ 2022-11-19 10:54:43
@[olkieler](/user/466525)
我是自己瞎打的
by xingke233 @ 2022-11-19 10:56:08
@[olkieler](/user/466525)
把自己想到的所有情况打上去，主要是
存在和不存在，存在几个最值
by xingke233 @ 2022-11-19 10:57:00
@[xingke233](/user/533452) thx，已关。
by Texas_the_Omertosa @ 2022-11-19 11:04:52