rt 代码如下:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
// 这题要开long long!!!!
const int maxn = 1e5 + 10;
struct node{
ll l, r, znum, fnum, pnum, sz; // 正数个数 负数个数 0个数
ll zmax = 0, zmin = INT_MAX, fmax = INT_MIN, fmin = 0; //最大正数 最小正数 最大负数 最小负数
}tree1[maxn*4], tree2[maxn*4];
ll n, m, q, a[maxn], b[maxn];
ll l1, r1, l2, r2;
void push_up1(ll x){
tree1[x].znum = tree1[x*2].znum + tree1[x*2+1].znum;
tree1[x].fnum = tree1[x*2].fnum + tree1[x*2+1].fnum;
tree1[x].pnum = tree1[x*2].pnum + tree1[x*2+1].pnum;
tree1[x].zmax = max(tree1[x*2].zmax, tree1[x*2+1].zmax);
tree1[x].zmin = min(tree1[x*2].zmin, tree1[x*2+1].zmin);
tree1[x].fmax = max(tree1[x*2].fmax, tree1[x*2+1].fmax);
tree1[x].fmin = min(tree1[x*2].fmin, tree1[x*2+1].fmin);
}
void push_up2(ll x){
tree2[x].znum = tree2[x*2].znum + tree2[x*2+1].znum;
tree2[x].fnum = tree2[x*2].fnum + tree2[x*2+1].fnum;
tree2[x].pnum = tree2[x*2].pnum + tree2[x*2+1].pnum;
tree2[x].zmax = max(tree2[x*2].zmax, tree2[x*2+1].zmax);
tree2[x].zmin = min(tree2[x*2].zmin, tree2[x*2+1].zmin);
tree2[x].fmax = max(tree2[x*2].fmax, tree2[x*2+1].fmax);
tree2[x].fmin = min(tree2[x*2].fmin, tree2[x*2+1].fmin);
}
void build1(ll i, ll l, ll r){
tree1[i].l = l, tree1[i].r = r, tree1[i].sz = tree1[i].r - tree1[i].l + 1;
if(l == r){
if(a[l] > 0) tree1[i].znum++, tree1[i].zmax = tree1[i].zmin = a[l];
else if(a[l] == 0) tree1[i].pnum++;
else tree1[i].fnum++, tree1[i].fmax = tree1[i].fmin = a[l];
return;
}
ll mid = (l + r) >> 1;
build1(i * 2, l, mid);
build1(i * 2 + 1, mid + 1, r);
push_up1(i);
}
void build2(ll i, ll l, ll r){
tree2[i].l = l, tree2[i].r = r, tree2[i].sz = tree2[i].r - tree2[i].l + 1;
if(l == r){
if(b[l] > 0) tree2[i].znum++, tree2[i].zmax = tree2[i].zmin = b[l];
else if(b[l] == 0) tree2[i].pnum++;
else tree2[i].fnum++, tree2[i].fmax = tree2[i].fmin = b[l];
return;
}
ll mid = (l + r) >> 1;
build2(i * 2, l, mid);
build2(i * 2 + 1, mid + 1, r);
push_up2(i);
}
node query1(ll i, ll x, ll y){
node pp;
pp.znum = pp.fnum = pp.pnum = 0;
pp.zmax = 0, pp.zmin = INT_MAX, pp.fmax = INT_MIN, pp.fmin = 0;
ll l = tree1[i].l, r = tree1[i].r;
if(l == r) return tree1[i];
if(l > y || r < x) return pp;
if(x <= l && r <= y) return tree1[i];
ll mid = (l + r) >> 1;
if(mid >= x){
node tt = query1(i * 2, x, y);
pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
}
if(mid < y){
node tt = query1(i * 2 + 1, x, y);
pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
}
return pp;
}
node query2(ll i, ll x, ll y){
node pp;
pp.znum = pp.fnum = pp.pnum = 0;
pp.zmax = 0, pp.zmin = INT_MAX, pp.fmax = INT_MIN, pp.fmin = 0;
ll l = tree2[i].l, r = tree2[i].r;
if(l == r) return tree2[i];
if(l > y || r < x) return pp;
if(x <= l && r <= y) return tree2[i];
ll mid = (l + r) >> 1;
if(mid >= x){
node tt = query2(i * 2, x, y);
pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
}
if(mid < y){
node tt = query2(i * 2 + 1, x, y);
pp.znum += tt.znum, pp.fnum += tt.fnum, pp.pnum += tt.pnum;
pp.zmax = max(pp.zmax, tt.zmax), pp.zmin = min(pp.zmin, tt.zmin);
pp.fmax = max(pp.fmax, tt.fmax), pp.fmin = min(pp.fmin, tt.fmin);
}
return pp;
}
ll solve(ll xx1, ll yy1, ll xx2, ll yy2){
node t1 = query1(1, xx1, yy1);
t1.l = xx1, t1.r = yy1; t1.sz = yy1 - xx1 + 1;
node t2 = query2(1, xx2, yy2);
t2.l = xx2, t2.r = yy2; t2.sz = yy2 - xx2 + 1;
if(t2.znum == t2.sz){
if(t1.znum == t1.sz) return t1.zmax * t2.zmin;
if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
if(t1.pnum == t1.sz) return 0;
if(!t1.fnum) return t1.zmax * t2.zmin;
if(!t1.znum) return 0;
if(!t1.pnum) return t1.zmax * t2.zmin;
return t1.zmax * t2.zmin;
}
if(t2.fnum == t2.sz){
if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
if(t1.fnum == t1.sz) return t1.fmin * t2.fmax;
if(t1.pnum == t1.sz) return 0;
if(!t1.fnum) return 0;
if(!t1.znum) return t1.fmin * t2.fmax;
if(!t1.pnum) return t1.fmin * t2.fmax;
return t1.fmin * t2.fmax;
}
if(t2.pnum == t2.sz){
return 0;
}
if(!t2.fnum){
if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
return 0;
}
if(!t2.znum){
if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
return 0;
}
if(t1.znum == t1.sz) return t1.zmin * t2.fmin;
if(t1.fnum == t1.sz) return t1.fmax * t2.zmax;
if(!t1.pnum) return max(t1.zmin * t2.fmin, t1.fmax * t2.zmax);
return 0;
}
int main(){
ios::sync_with_stdio(0);
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
cin >> n >> m >> q;
for(ll i = 1; i <= n; i++) cin >> a[i];
for(ll i = 1; i <= m; i++) cin >> b[i];
build1(1, 1, n);
build2(1, 1, m);
while(q--){
cin >> l1 >> r1 >> l2 >> r2;
cout << solve(l1, r1, l2, r2) << endl;
}
return 0;
}