首页 > 其他分享 >P8818 [CSP-S 2022] 策略游戏 题解

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

时间:2022-11-01 14:46:58浏览次数:52  
标签:return int 题解 P8818 最小值 2022 text inline 正数

思路

题意:求一个特定矩形中每一行的最小值的最大值。

考虑分类讨论。

注意,由于 \(0\) 也需要考虑,所以下文中的正数和负数都包括了 \(0\)。

  1. \(\text{a}\) 全部都是正的。

    由于 \(\text{a}\) 全部都是正的。

    那么无论小L选择什么,小Q总是会选择 \(\text{b}\) 序列中最小值。

    所以小L只需要从最大值(小Q选的是正数)和最小值(小Q选的是负数)中选一个就可以了。

  2. \(\text{a}\) 全部都是负的。

    与第一点类似。

    由于 \(\text{a}\) 全部都是负的。

    那么无论小L选择什么,小Q总是会选择 \(\text{b}\) 序列中最大值。

    所以小L只需要从最大值(小Q选的是负数)和最小值(小Q选的是正数)中选一个就可以了。

  3. \(\text{b}\) 全部都是正的

    由于我们已经考虑了上面两点,所以现在 \(\text{a}\) 序列必然是既有正数又有负数。

    那么小L一定会选择最大值,小Q也一定会选择最小值。

  4. \(\text{b}\) 全部都是负的

    和上面类似,其实就是反过来

    那么小L一定会选择最小值,小Q也一定会选择最大值。

  5. 没有特殊限制

    考虑到两个序列都是既有正数又有负数。

    那么就可以发现如果小L选择的是一个负数,那么小Q就会选择最大值;如果小L选择的是一个正数,那么小Q就会选择最小值。

    所以小L一定会选择最接近零的正数和负数,也就是正数最小值和负数最大值。

考虑一下上面需要求的东西。

\(\text{a}\) 序列最大最小值,\(\text{b}\) 序列最大最小值,\(\text{a}\) 序列正数最小值和 \(\text{a}\) 序列负数最大值。

这个开四颗线段树就可以了。

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

代码也比较好写。

Code

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

const int N = 100010;

int n , m , q , a[N] , b[N];
int s[N] , sum1[N] , sum2[N] , sum3[N] , sum4[N];

struct Node
{
    int l , r , minn , maxx;
};

struct Tree
{
    Node t[N * 4];
    inline void push_up(int p)
    {
        t[p].minn = min(t[p * 2].minn , t[p * 2 + 1].minn);
        t[p].maxx = max(t[p * 2].maxx , t[p * 2 + 1].maxx);
    }
    inline void build(int p , int l , int r)
    {
        t[p].l = l , t[p].r = r;
        if(l == r) return t[p].minn = t[p].maxx = s[l] , void();
        int mid = (l + r) / 2;
        build(p * 2 , l , mid);
        build(p * 2 + 1 , mid + 1 , r);
        push_up(p);
    }
    inline int ask1(int p , int l , int r)
    {
        if(l <= t[p].l && t[p].r <= r)
            return t[p].minn;
        int mid = (t[p].l + t[p].r) / 2 , ans = 1e9;
        if(l <= mid) ans = min(ans , ask1(p * 2 , l , r));
        if(r >  mid) ans = min(ans , ask1(p * 2 + 1 , l , r));
        return ans;
    }
    inline int ask2(int p , int l , int r)
    {
        if(l <= t[p].l && t[p].r <= r)
            return t[p].maxx;
        int mid = (t[p].l + t[p].r) / 2 , ans = -1e9;
        if(l <= mid) ans = max(ans , ask2(p * 2 , l , r));
        if(r >  mid) ans = max(ans , ask2(p * 2 + 1 , l , r));
        return ans;
    }
}t1 , t2 , t3 , t4;

//t1:a全
//t2:b全
//t3:a正
//t4:a负

inline int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

inline bool ask1(int l , int r) { return (sum1[r] - sum1[l - 1]) == (r - l + 1); }
inline bool ask2(int l , int r) { return (sum2[r] - sum2[l - 1]) == (r - l + 1); }
inline bool ask3(int l , int r) { return (sum3[r] - sum3[l - 1]) == (r - l + 1); }
inline bool ask4(int l , int r) { return (sum4[r] - sum4[l - 1]) == (r - l + 1); }

signed main()
{
    n = read() , m = read() , q = read();
    for(int i = 1;i <= n;i++)
        a[i] = read();
    for(int i = 1;i <= m;i++)
        b[i] = read();
    for(int i = 1;i <= n;i++)
        s[i] = a[i] , sum1[i] = sum1[i - 1] + (a[i] <= 0) , sum3[i] = sum3[i - 1] + (a[i] >= 0);
    t1.build(1 , 1 , n);
    for(int i = 1;i <= m;i++)
        s[i] = b[i] , sum2[i] = sum2[i - 1] + (b[i] <= 0) , sum4[i] = sum4[i - 1] + (b[i] >= 0);
    t2.build(1 , 1 , m);
    for(int i = 1;i <= n;i++) s[i] = (a[i] >= 0 ? a[i] : 1e9); t3.build(1 , 1 , n);
    for(int i = 1;i <= n;i++) s[i] = (a[i] < 0 ? a[i] : -1e9); t4.build(1 , 1 , n);
    for(int i = 1;i <= q;i++)
    {
        int l1 = read() , r1 = read() , l2 = read() , r2 = read();
        if(l1 > r1) swap(l1 , r2); if(l2 > r2) swap(l2 , r2);
        if(ask1(l1 , r1))
            cout << max(t1.ask2(1 , l1 , r1) * t2.ask2(1 , l2 , r2) , t1.ask1(1 , l1 , r1) * t2.ask2(1 , l2 , r2)) << endl;
        else if(ask3(l1 , r1))
            cout << max(t1.ask2(1 , l1 , r1) * t2.ask1(1 , l2 , r2) , t1.ask1(1 , l1 , r1) * t2.ask1(1 , l2 , r2)) << endl;
        else if(ask2(l2 , r2))
            cout << t1.ask1(1 , l1 , r1) * t2.ask2(1 , l2 , r2) << endl;
        else if(ask4(l2 , r2))
            cout << t1.ask2(1 , l1 , r1) * t2.ask1(1 , l2 , r2) << endl;
        else
            cout << max(t3.ask1(1 , l1 , r1) * t2.ask1(1 , l2 , r2) , t4.ask2(1 , l1 , r1) * t2.ask2(1 , l2 , r2)) << endl;
    }
    return 0;
}

标签:return,int,题解,P8818,最小值,2022,text,inline,正数
From: https://www.cnblogs.com/mfeitveer/p/16847619.html

相关文章

  • 20221031&20221101 Keras
    周末长安杯加上组网实验信安数基上机计网翻转课堂核酸S12半决赛,小摆几天......
  • 2022-11-01
    棕榈:2D:下跌  2H:上涨  20F:上涨第一波 总结:2D下跌,2H上涨第二波,20F上涨第一波。做空等2F第二波结束等20F上涨第二波顶背驰 ......
  • CSP-S 2022 游寄+缇解
    游寄怎样更多流水账?摘要只是因为考前等车在《百年孤独》,所以找点东西魔怔(草Day-1纯纯文化课生,文化课了一个月。呃呃,周五周六有羟基补课。家长说周五上语英,逃跑计划......
  • 2022 China Collegiate Programming Contest (CCPC) Guilin Site
    比赛链接2022ChinaCollegiateProgrammingContest(CCPC)GuilinSiteC.ArrayConcatenation给定一个长度为\(n\)的数组\(b_i\),有两种操作变换:\(b^{\prime}=\l......
  • idea2022设置debug的时候热更新
    之前的项目在配置中可以选选择更新的时候更新类和资源,2022版位置变了,需要自己添加这个功能之后在debug模式的时候改了代码,点击编译之后就热更新了(只对java代码有效,xml......
  • CSP2022游记
    第一次几乎完全没有准备的比赛也是倒数第二场比赛Day-1上了一天文化课,晚上还有强基班。强基班上完之后来机房写了几个板子就开始颓废了基本上就抱着摆烂的心态不过......
  • 当前SAT主要关键技术及其相关文献2022-11-1
    摘录自:TasniemNasserAl-Yahya, MohamedElBachirMenai, HassanMathkour:Boosting the Performance of CDCL-Based SAT Solvers by Exploiting Backbon......
  • CSP-S 2022 又寄
    太蠢了,寄掉了初赛竟然是线上举办……AWTY(\(47\))和Lucas(\(49\))寄掉了,只能给€€£打钱了。upd.打了钱还是进不去,只能加\(5\)分……DAY-inf复习了一......
  • CSP-S 2022 T4 题解
    简述题意给一颗\(n\)个点的树,每个点有点权\(v_i\)。有\(q\)次询问,每次给出\((u,v)\),从\(u\)开始,每步只能走不超过\(k\)条边,走一步的代价是终点的点权,\(v_u\)也......
  • 2022祥云杯 - HashRun安全团队wp
    2022祥云杯-HashRun安全团队wpHaveFun@T4x0r注册一个\(admin\)账号发现页面会提示已经注册,其实本来想的是注入,但是发现注册功能活的,感觉二次注入可能也不是很大,注册......