CSP-S 2022 T2 策略游戏题解

T2 比 T1 简单？
可以发现，讨论的情况数不是很多。可以直接用线段树查询然后暴力讨论就好了。

（写的好丑）

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
#define int long long

template <class T>
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

int a[N], b[N]; 
int n , m, Q; 

struct Segment_tree{
  struct node{
    int minn; 
    int maxn; 
    bool zero; 

    int minzheng, maxfu; 

  } t[N << 2]; 

  #define lson (o<<1)
  #define rson (o<<1|1)

  inline void pushup(int o){
    t[o].minn = min(t[lson].minn, t[rson].minn);
    t[o].maxn = max(t[lson].maxn, t[rson].maxn); 
    t[o].minzheng = min(t[lson].minzheng, t[rson].minzheng); 
    t[o].maxfu = max(t[lson].maxfu, t[rson].maxfu); 
    t[o].zero = t[lson].zero | t[rson].zero; 
    return ; 
  }

  inline void build(int o, int l, int r, int* a){
    if(l == r){
      t[o].maxn = t[o].minn = a[l];
      t[o].zero = (a[l] == 0); 
      if(a[l] > 0) t[o].minzheng = a[l];
      else t[o].minzheng = 1e9 + 100; 
      if(a[l] < 0) t[o].maxfu = a[l];
      else t[o].maxfu = -1e9 - 100; 
      return ; 
    }
    int mid = l + r >> 1;
    build(lson, l, mid, a);
    build(rson, mid + 1, r, a);
    pushup(o);
    return ; 
  }

  int query_min(int o, int l, int r, int in, int end){
    if(l > end || r < in) return 1e9 + 100; 
    if(l >= in && r <= end) return t[o].minn;
    int mid = l + r >> 1;
    return min(query_min(lson, l, mid, in, end), query_min(rson, mid + 1, r, in, end)); 
  }

  int query_max(int o, int l, int r, int in, int end){
    if(l > end || r < in) return -(1e9 + 100); 
    if(l >= in && r <= end) return t[o].maxn; 
    int mid = l + r >> 1;
    return max(query_max(lson, l, mid, in, end), query_max(rson, mid + 1, r, in, end)); 
  }

  int query_zero(int o, int l, int r, int in, int end){
    if(l > end || r < in) return 0; 
    if(l >= in && r <= end) return t[o].zero; 
    int mid = l + r >> 1; 
    return query_zero(lson, l, mid, in, end) | query_zero(rson, mid + 1, r, in, end); 
  }

  int query_minzheng(int o, int l, int r, int in, int end){
    if(l > end || r < in) return 1e9 + 100;
    if(l >= in && r <= end) return t[o].minzheng; 
    int mid = l + r >> 1;
    return min(query_minzheng(lson, l, mid, in, end), query_minzheng(rson, mid + 1, r, in, end)); 
  }

  int query_maxfu(int o, int l, int r, int in, int end){
    if(l > end || r < in) return -1e9 - 100;
    if(l >= in && r <= end) return t[o].maxfu; 
    int mid = l + r >> 1;
    return max(query_maxfu(lson, l, mid, in, end), query_maxfu(rson, mid + 1, r, in, end)); 
  }

} tree1, tree2; 

signed main(){
  // freopen("hh.txt", "r", stdin); 
  // freopen("out.txt", "w", stdout); 
  read(n), read(m), read(Q);
  for(int i = 1; i <= n; i++) read(a[i]);
  for(int i = 1; i <= m; i++) read(b[i]); 

  tree1.build(1, 1, n, a); 
  tree2.build(1, 1, m, b); 

  while(Q--){
    int l1, l2, r1, r2;
    read(l1), read(r1), read(l2), read(r2); 
    int amx = tree1.query_max(1, 1, n, l1, r1); 
    int ami = tree1.query_min(1, 1, n, l1, r1); 
    int bmi = tree2.query_min(1, 1, m, l2, r2); 
    int bmx = tree2.query_max(1, 1, m, l2, r2); 
    bool aze = tree1.query_zero(1, 1, n, l1, r1); 
    bool bze = tree2.query_zero(1, 1, m, l2, r2); 
    ll ans; 
    // 
    if(bmi >= 0){  // B全正
      if(amx <= 0) ans = amx * bmx;
      else ans = amx * bmi; 
    }
    else if(bmx <= 0){
      if(ami <= 0) ans = ami * bmx; 
      else ans = ami * bmi; 
    }
    else{ // B 有正有负
      if(ami >= 0) ans = ami * bmi; 
      else if(amx <= 0) ans = amx * bmx; 
      else{
        int amiz = tree1.query_minzheng(1, 1, n, l1, r1); 
        int amaxf = tree1.query_maxfu(1, 1, n, l1, r1); 
        if(aze) ans = 0;
        else{
          ll sum1 = amiz * bmi; 
          ll sum2 = amaxf * bmx; 
          ans = max(sum1, sum2); 
        }
      }
    }
    cout << ans << endl; 
  }

  return 0;
}