[CSP-S 2022] 策略游戏

P8818 [CSP-S 2022] 策略游戏 题面

今年到现在也没写总结，也快失去写它的欲望了，五味杂陈，想说出的理由有很多，想来还是罢了，毕竟也已经没有了意义…

这题可能是往年以来最容易的第二题了，可惜考试时钻T1失去了很多时间，T2无法完成，感觉考试时心里目标不高，导致实际结果更差。

---

分$A\ge 0,A<0,B\ge 0,B<0$ 几种情况讨论，于是需要维护
$A\ge 0$最大值，最小值
$A<0$最大值，最小值
$B\ge 0$最大值，最小值
$B<0$最大值，最小值
使用八棵线段树即可，没有什么思维深度。（当然也有六个ST表的，没有什么区别）

最后再根据5种不同情况制定相应策略即可，分别是：

• 以A（即甲）为主导： { A 有 非 负 数 ， B 无 负 数 A 有 负 数 ， B 无 非 负 数 \left\{
  A有非负数，B无负数A有负数，B无非负数" role="presentation">A有非负数，B无负数A有负数，B无非负数$$\begin{array}{c}A有非负数，B无负数\\ A有负数，B无非负数\end{array}$$
  \right. {A有非负数，B无负数A有负数，B无非负数​
• 以B（即乙）为主导： { B 有 非 负 数 ， A 无 非 负 数 B 有 负 数 ， A 无 负 数 \left\{
  B有非负数，A无非负数B有负数，A无负数" role="presentation">B有非负数，A无非负数B有负数，A无负数$$\begin{array}{c}B有非负数，A无非负数\\ B有负数，A无负数\end{array}$$
  \right. {B有非负数，A无非负数B有负数，A无负数​
• A，B非负数，负数兼备。

---

码就是了。

#include
using namespace std;
typedef long long LL;
const int N=1e5+5,BZ=-1e9-1;
int n,m,q;
struct qh{
    LL a[N],tr[N<<2];
    int bz;
    #define M (l+r>>1)
    #define ls (id<<1)
    #define rs (ls|1)
    void pushup(int bz,int id){
        if(tr[ls]==BZ&&tr[rs]==BZ) tr[id]=BZ;
        else if(tr[ls]!=BZ&&tr[rs]!=BZ) tr[id]=bz==1?max(tr[ls],tr[rs]):min(tr[ls],tr[rs]);
        else if(tr[ls]==BZ) tr[id]=tr[rs];
        else if(tr[rs]==BZ) tr[id]=tr[ls];
        return ;
    }
    void build(int id,int l,int r){
        if(l==r){tr[id]=a[l];return ;}
        build(ls,l,M);build(rs,M+1,r);
        pushup(bz,id);
    }
    LL queryn(int id,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tr[id];
        LL mn=1e10;
        if(x<=M){
            LL q=queryn(ls,l,M,x,y);
            if(q!=BZ) mn=min(mn,q);
        }
        if(M<y){
            LL q=queryn(rs,M+1,r,x,y);
            if(q!=BZ) mn=min(mn,q);
        }
        return mn;
    }
    LL queryx(int id,int l,int r,int x,int y){
        if(x<=l&&r<=y) return tr[id];
        LL mx=BZ;
        if(x<=M){
            LL q=queryx(ls,l,M,x,y);
            if(q!=BZ) mx=max(mx,q);
        }
        if(M<y){
            LL q=queryx(rs,M+1,r,x,y);
            if(q!=BZ) mx=max(mx,q);
        }
        return mx;
    }
}axz,anz,bxz,bnz,axf,anf,bxf,bnf;
inline int Rd(){
    int s=0,w=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}
int main(){
    // freopen("game4.in","r",stdin);
    // freopen("game.out","w",stdout);
    n=Rd();m=Rd();q=Rd();
    axz.bz=bxz.bz=1;axf.bz=bxf.bz=1;
    anz.bz=bnz.bz=2;anf.bz=bnf.bz=2;
    for(int i=1,x;i<=n;i++) x=Rd(),axz.a[i]=anz.a[i]=(x>=0?x:BZ), axf.a[i]=anf.a[i]=(x<0?x:BZ);
    for(int i=1,x;i<=m;i++) x=Rd(),bxz.a[i]=bnz.a[i]=(x>=0?x:BZ),bxf.a[i]=bnf.a[i]=(x<0?x:BZ);
    axz.build(1,1,n);anz.build(1,1,n);bxz.build(1,1,m);bnz.build(1,1,m);axf.build(1,1,n);anf.build(1,1,n);bxf.build(1,1,m);bnf.build(1,1,m);
    while (q--){
        int l1=Rd(),r1=Rd(),l2=Rd(),r2=Rd();
        LL Axz=axz.queryx(1,1,n,l1,r1),Axf=axf.queryx(1,1,n,l1,r1),Anz=anz.queryn(1,1,n,l1,r1),Anf=anf.queryn(1,1,n,l1,r1),Bxz=bxz.queryx(1,1,m,l2,r2),Bxf=bxf.queryx(1,1,m,l2,r2),Bnz=bnz.queryn(1,1,m,l2,r2),Bnf=bnf.queryn(1,1,m,l2,r2);
        LL A=0,B=0;
        // printf("%lld %lld %lld %lld %lld %lld %lld %lld\n",Axz,Axf,Anz,Anf,Bxz,Bxf,Bnz,Bnf);
        if(Axz!=BZ&&Bxf==BZ) A=Axz,B=Bnz;
        else if(Axf!=BZ&&Bxz==BZ) A=Anf,B=Bxf;
        else if(Bxf!=BZ&&Axf==BZ) A=Anz,B=Bnf;
        else if(Bxz!=BZ&&Axz==BZ) A=Axf,B=Bxz;
        else{
            if(Axf*Bxz>Anz*Bnf) A=Axf,B=Bxz;
            else A=Anz,B=Bnf;
        }
        printf("%lld\n",A*B);
    }
    return 0;
}
/*
start coding:10:23
stop:10:46
continue:11:19
stop:12:00
continue:15:04
finish debuging:15:11
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

71分钟一遍过，哭死