P8818 [CSP-S 2022] 策略游戏

[CSP-S 2022] 策略游戏

实际上就是先手的那个人取保底，后手的那个人取此刻的最佳值。

我一开始以为两个人都取保底，谁想到这么没意思……

那么就是线段树小应用，分别维护区间非负数和负数的最大值以及最小值，具体细节讨论一下即可。

时间复杂度 \(O((n+q)\log n)\)。

复健状态的码风比较离谱……我以后写线段树的时候会尽量封装，尽量……

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e5;

ll n,m,q;
ll a[N+5],b[N+5];

struct Sgt{
  ll maz,maf,miz,mif;
  #define maz1(p) tree1[p].maz
  #define maf1(p) tree1[p].maf
  #define miz1(p) tree1[p].miz
  #define mif1(p) tree1[p].mif
  #define maz2(p) tree2[p].maz
  #define maf2(p) tree2[p].maf
  #define miz2(p) tree2[p].miz
  #define mif2(p) tree2[p].mif
}tree1[N*4+5],tree2[N*4+5];

inline void Pushup1(ll p) {
  maz1(p)=max(maz1(p<<1),maz1(p<<1|1));
  if(maf1(p<<1)>=0) maf1(p)=maf1(p<<1|1);
  else if(maf1(p<<1|1)>=0) maf1(p)=maf1(p<<1);
  else maf1(p)=max(maf1(p<<1),maf1(p<<1|1));
  if(miz1(p<<1)<0) miz1(p)=miz1(p<<1|1);
  else if(miz1(p<<1|1)<0) miz1(p)=miz1(p<<1);
  else miz1(p)=min(miz1(p<<1),miz1(p<<1|1));
  mif1(p)=min(mif1(p<<1),mif1(p<<1|1));
}

inline void Pushup2(ll p) {
  maz2(p)=max(maz2(p<<1),maz2(p<<1|1));
  if(maf2(p<<1)>=0) maf2(p)=maf2(p<<1|1);
  else if(maf2(p<<1|1)>=0) maf2(p)=maf2(p<<1);
  else maf2(p)=max(maf2(p<<1),maf2(p<<1|1));
  if(miz2(p<<1)<0) miz2(p)=miz2(p<<1|1);
  else if(miz2(p<<1|1)<0) miz2(p)=miz2(p<<1);
  else miz2(p)=min(miz2(p<<1),miz2(p<<1|1));
  mif2(p)=min(mif2(p<<1),mif2(p<<1|1));
}

inline void Build1(ll p,ll l,ll r) {
  if(l==r) {
    if(a[l]>=0) {maz1(p)=miz1(p)=a[l];}
    else {maf1(p)=mif1(p)=a[l];maz1(p)=miz1(p)=-1;}
    return;
  }
  ll mid=(l+r)>>1;Build1(p<<1,l,mid);Build1(p<<1|1,mid+1,r);
  Pushup1(p);
}

inline void Build2(ll p,ll l,ll r) {
  if(l==r) {
    if(b[l]>=0) {maz2(p)=miz2(p)=b[l];}
    else {maf2(p)=mif2(p)=b[l];maz2(p)=miz2(p)=-1;}
    return;
  }
  ll mid=(l+r)>>1;Build2(p<<1,l,mid);Build2(p<<1|1,mid+1,r);
  Pushup2(p);
}

inline Sgt Get1(ll p,ll lp,ll rp,ll l,ll r) {
  if(lp>=l&&rp<=r) {return tree1[p];}
  ll mid=(lp+rp)>>1;
  if(l>mid) return Get1(p<<1|1,mid+1,rp,l,r);
  if(r<=mid) return Get1(p<<1,lp,mid,l,r);
  Sgt tmpl=Get1(p<<1,lp,mid,l,r),tmpr=Get1(p<<1|1,mid+1,rp,l,r),tmp;
  tmp.maz=max(tmpl.maz,tmpr.maz);
  if(tmpl.maf>=0) tmp.maf=tmpr.maf;
  else if(tmpr.maf>=0) tmp.maf=tmpl.maf;
  else tmp.maf=max(tmpl.maf,tmpr.maf);
  if(tmpl.miz<0) tmp.miz=tmpr.miz;
  else if(tmpr.miz<0) tmp.miz=tmpl.miz;
  else tmp.miz=min(tmpl.miz,tmpr.miz);
  tmp.mif=min(tmpl.mif,tmpr.mif);
  return tmp;
}

inline Sgt Get2(ll p,ll lp,ll rp,ll l,ll r) {
  if(lp>=l&&rp<=r) {return tree2[p];}
  ll mid=(lp+rp)>>1;
  if(l>mid) return Get2(p<<1|1,mid+1,rp,l,r);
  if(r<=mid) return Get2(p<<1,lp,mid,l,r);
  Sgt tmpl=Get2(p<<1,lp,mid,l,r),tmpr=Get2(p<<1|1,mid+1,rp,l,r),tmp;
  tmp.maz=max(tmpl.maz,tmpr.maz);
  if(tmpl.maf>=0) tmp.maf=tmpr.maf;
  else if(tmpr.maf>=0) tmp.maf=tmpl.maf;
  else tmp.maf=max(tmpl.maf,tmpr.maf);
  if(tmpl.miz<0) tmp.miz=tmpr.miz;
  else if(tmpr.miz<0) tmp.miz=tmpl.miz;
  else tmp.miz=min(tmpl.miz,tmpr.miz);
  tmp.mif=min(tmpl.mif,tmpr.mif);
  return tmp;
}

int main() {
  
  n=read();m=read();q=read();
  for(ll i=1;i<=n;i++) {a[i]=read();}
  for(ll i=1;i<=m;i++) {b[i]=read();}
  Build1(1,1,n);Build2(1,1,m);
  
  while(q--) {
    ll l1,r1,l2,r2;
    l1=read();r1=read();l2=read();r2=read();
    Sgt tmpa=Get1(1,1,n,l1,r1);
    ll maza=tmpa.maz,mafa=tmpa.maf,miza=tmpa.miz,mifa=tmpa.mif;
    Sgt tmpb=Get2(1,1,m,l2,r2);
    ll mazb=tmpb.maz,mafb=tmpb.maf,mizb=tmpb.miz,mifb=tmpb.mif;
    
//    printf("Testa: %lld %lld %lld %lld\n",maza,mafa,miza,mifa);
//    printf("Testb: %lld %lld %lld %lld\n",mazb,mafb,mizb,mifb);
    
    ll choice_a=0,choice_b=0;
    if(mifb>=0) {
      if(maza>=0) choice_a=maza;
      else choice_a=mafa;
    }
    else {
      if(mazb<0) {
        if(mifa<0) choice_a=mifa;
        else choice_a=miza;
      }
      else {
        if(miza<0) choice_a=mafa;
        else if(mafa>=0) choice_a=miza;
        else if(mifb*miza>mazb*mafa) choice_a=miza;
        else choice_a=mafa;
      }
    }
    
    if(choice_a>=0) {
      if(mifb<0) choice_b=mifb;
      else choice_b=mizb;
    }
    else {
      if(mazb>=0) choice_b=mazb;
      else choice_b=mafb;
    }
    writeln(choice_a*choice_b);
  }
  
  return 0;
}