你想得太简单了
by 1234567_scp @ 2023-08-24 10:20:38
@[The_Wandering_Earth](/user/809165)
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, q;
const int N=100005;
ll a[N], b[N], mxb[N][30], mnb[N][30];
ll mxna[N][30], mnpa[N][30], mxpa[N][30], mnna[N][30];//mxna最大负数， mnpa最小非负数
void init() {
int inf =0x7fffffff;
for(int i = 1; i <= n; i++) {
mxpa[i][0] = a[i];
mnpa[i][0] = a[i]>=0? a[i]: inf;
mxna[i][0] = a[i]<=0? a[i]:-inf;
mnna[i][0] = a[i];
}
for(int i = 1; i <= m; i++)
mnb[i][0] = mxb[i][0] = b[i];
for(int j = 1; (1<<j) <= n; j++)
for(int i = 1; i+(1<<j)-1 <= n; i++) {
mxpa[i][j] = max(mxpa[i][j-1], mxpa[i+(1<<(j-1))][j-1]);
mnpa[i][j] = min(mnpa[i][j-1], mnpa[i+(1<<(j-1))][j-1]);
mxna[i][j] = max(mxna[i][j-1], mxna[i+(1<<(j-1))][j-1]);
mnna[i][j] = min(mnna[i][j-1], mnna[i+(1<<(j-1))][j-1]);
}
for(int j = 1; (1<<j) <= m; j++)
for(int i = 1; i+(1<<j)-1 <= m; i++) {
mxb[i][j] = max(mxb[i][j-1], mxb[i+(1<<(j-1))][j-1]);
mnb[i][j] = min(mnb[i][j-1], mnb[i+(1<<(j-1))][j-1]);
}
}
void query(int l1, int r1, int l2, int r2) {
int k1 = log2(r1-l1+1), k2 = log2(r2-l2+1);
ll ans;
ll maxb=max(mxb[l2][k2], mxb[r2-(1<<k2)+1][k2]);
ll minb=min(mnb[l2][k2], mnb[r2-(1<<k2)+1][k2]);
ll maxpa=max(mxpa[l1][k1], mxpa[r1-(1<<k1)+1][k1]);
ll minpa=min(mnpa[l1][k1], mnpa[r1-(1<<k1)+1][k1]);
ll maxna=max(mxna[l1][k1], mxna[r1-(1<<k1)+1][k1]);
ll minna=min(mnna[l1][k1], mnna[r1-(1<<k1)+1][k1]);
if (minb>=0)
ans=maxpa>=0? maxpa*minb: maxna*maxb;
else if (maxb<=0)
ans=minna<=0? minna*maxb: minpa*minb;
else {
if (maxpa<0)
ans=maxna*maxb;
else if (minna>0)
ans=minpa*minb;
else
ans=max(minpa*minb, maxna*maxb);
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i++)
scanf("%lld", a+i);
for(int i = 1; i <= m; i++)
scanf("%lld", b+i);
init();
for(int i = 1; i <= q; i++) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
query(l1, r1, l2, r2);
}
return 0;
}
by 1234567_scp @ 2023-08-24 11:02:16