首页 > 其他分享 >航电第三场(单峰数列)

航电第三场(单峰数列)

时间:2024-07-27 12:06:37浏览次数:15  
标签:pre suf sub 航电 单峰 mou add && 第三场

单峰数列

  • 题意对于一个整数数列,如果其先严格递增,然后在某一点后严格递减,我们称这个数列为单峰数列(严格递增和严格递减的部分均要是非空)。
    给定长度为 n 的整数数列 \(a_1,a_2,…,a_n\),请你支持 q 次操作:
  1. 1 l r x:将 \(a_l,a_{l+1},…,a_r\) 的每个数加 x。
  2. 2 l r:判断 \(a_l,a_{l+1},…,a_r\) 的元素是否全都相同。
  3. 3 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否严格升序排序。当 \(l=r\) 时,认为符合严格升序排序。
  4. 4 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否严格降序排序。当 \(l=r\) 时,认为符合严格降序排序。
  5. 5 l r:判断 \(a_l,a_{l+1},…,a_r\) 是否为单峰数列。保证 \(r−l+1≥3\)。
  • \(n (3≤n≤10^5), a1,a2,…,an (0≤ai≤10^9), q (1≤q≤2×10^5), −10^9≤x≤10^9\)

赛时前面开的比较慢,这题就稍微有点急,没鼠标和习惯问题(还是练习太少了,每次写完线段树的题目都没仔细想),导致赛时没debug出来,但是思路一眼时对的:

对于这种区间信息合并和整个区间有关的,不是某个值的信息维护,一般考虑每个区间的 \(pre, suf\), 和一些关键性质,区间加法应该学过线段树的都会,这里不详细讲了。这题的关键性质就是每个区间其他信息的关系,记相同为same,上升为add, 下降是sub,单峰为mou,合并时这样维护(记父亲区间为c,左右儿子是a, b:


对于 same, 父亲如果要是 same,则左右一定也是 same 且相接的地方是相等的,即 c.same = a.same && b.same && a.suf == b.pre


对于 add,父亲如果要是 add,则左右一定也是 add 且相接的地方是递增的,即 c.add = a.add && b.add && a.suf < b.pre


对于 sub,父亲如果要是 sub,则左右一定也是 sub 且相接的地方是递减的,即 c.sub = a.sub && b.sub && a.suf > b.pre


特别的对于 mou,我们定义小于3的区间 mou = 0, 这里单峰有三种情况
1.左增右减,相接的地方无论在哪都会是单峰

2.左边单峰,右边一定是递减的,否则会有一个新的峰

3.右边单峰, 左边一定是上升的,否则会有一个新的峰



剩下的合并就是左右的 pre 和 suf 了,c.pre = a.pre, c.suf = b.suf

Info merge(const Info& a, const Info& b) {
    Info c;

    if(a.same && b.same && a.suf == b.pre) c.same = 1;
    else c.same = 0;


    if(a.add && b.add && a.suf < b.pre) c.add = 1;
    else c.add = 0;

    if(a.sub && b.sub && a.suf > b.pre) c.sub = 1;
    else c.sub = 0;

    c.len = a.len + b.len;

    if(c.len >= 3) {
        if((a.add && b.sub) ||
           (a.add && b.mou && a.suf < b.pre) || 
           (a.mou && b.sub && a.suf > b.pre) ) 
                c.mou = 1;
        if(a.len == 1) c.mou = a.suf < b.pre && (b.mou || b.sub);
        if(b.len == 1) c.mou = a.suf > b.pre && (a.mou || a.add);
    }
    else c.mou = 0;
    c.pre = a.pre, c.suf = b.suf;
    
    return c;
}

注意查询时的的信息返回也是一大坑点, 访问到空区间时的相关参数赋值(死了一个小时多没想出来,赛后多亏仙佬指点),这里不要用普通的那样查询,按整个区间块返回合并,题解也是这样,避免了大量空区间的参数定义,详情看代码。注意操作一有区间操作,别忘了下传 lazy标记。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<ll,ll>;
using PIII = pair<ll, pair<ll,ll>>;
#define endl "\n"
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) (x) & (-x)
#define point(x) setiosflags(ios::fixed)<<setprecision(x)
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
struct Info {//一定要初始化
    int pre, suf;//区间最前面一个,最后一个,
    int len = 1;
    int lazy;
    int add, sub, mou;//是否是递增,递减,单峰
    int same;//是否是相同
    Info (int x) {
        pre = suf = x;
        lazy = 0;
        add = sub = same = 1;
        mou = 0; 
    }
    Info () {
        pre = -1e18, suf = -1e18;
        lazy = 0;
        add = sub = same = 1;
        mou = 0; 
    }
};
Info merge(const Info& a, const Info& b) {
    Info c;

    if(a.same && b.same && a.suf == b.pre) c.same = 1;
    else c.same = 0;


    if(a.add && b.add && a.suf < b.pre) c.add = 1;
    else c.add = 0;

    if(a.sub && b.sub && a.suf > b.pre) c.sub = 1;
    else c.sub = 0;

    c.len = a.len + b.len;

    if(c.len >= 3) {
        if((a.add && b.sub) ||
           (a.add && b.mou && a.suf < b.pre) || 
           (a.mou && b.sub && a.suf > b.pre) ) 
                c.mou = 1;
        if(a.len == 1) c.mou = a.suf < b.pre && (b.mou || b.sub);
        if(b.len == 1) c.mou = a.suf > b.pre && (a.mou || a.add);
    }
    else c.mou = 0;
    c.pre = a.pre, c.suf = b.suf;
    
    return c;
}
struct segtree {
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    int n;
    segtree(int n) {init(n);};
    vector<Info> info;
    vector<int> a;
    void init(int n) {
        this->n = n;
        info.resize(n << 2);
        a.resize(n << 1);
    }
    void push_up(int u) {
        info[u] = merge(info[ls], info[rs]);
    }
    void build(int u, int l, int r)
    {
        if(l == r)
        {
            info[u] = Info();//填值
            return ;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
    void settag(int u, int k) {//处理数据
        info[u].pre += k;
        info[u].suf += k;
        info[u].lazy += k;
     }
    void push_down(int u)
    {
        if(info[u].lazy)
        {
            settag(ls, info[u].lazy);
            settag(rs, info[u].lazy);
            info[u].lazy = 0;
        }
    }
    void update(int u, int l, int r, int pos, int k) {
        if(l == r) {
            info[u] = Info(k);
            return;
        }
        push_down(u);
        int mid = l + r >> 1;
        if(pos <= mid) update(ls, l, mid, pos, k);
        else update(rs, mid + 1, r, pos, k);
        push_up(u);

    };
    void update(int u, int l, int r, int x, int y, int k) {
        if(x <= l && r <= y) {
            settag(u, k);
            return;
        }
        push_down(u);
        int mid = l + r >> 1;
        if(x <= mid) update(ls, l, mid, x, y, k);
        if(mid < y) update(rs, mid + 1, r, x, y, k);
        push_up(u);
    }
    void update(int pos, int v) {
        update(1, 1, n, pos, v);
    }
    void update(int x, int y, int k) {
        update(1, 1, n, x, y, k);
    }
    Info query(int u, int l, int r, int x, int y) {
        if (x <= l && r <= y) return info[u];
        push_down(u);
        int mid = l + r >> 1;
        if (y <= mid) return query(ls, l, mid, x, y);
        else if (mid < x) return query(rs, mid + 1, r, x, y);
        else return merge(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
    }
    Info query(int l, int r) {
        return query(1, 1, n, l, r);
    }

};
void solve(){
    int n; cin >> n; 
    segtree tr(n);
    for(int i = 1; i <= n; i ++) {
        int x; cin >> x;
        tr.update(i, x);
    }
    int m; cin >> m;
    while(m --) {
        int op, l, r; cin >> op >> l >> r;
        ll x; 
        if(op == 1) {
            cin >> x;
            tr.update(l, r, x);
        } 
        else if(op == 2) {
            auto t = tr.query(l, r);
            cout << t.same << endl;
        } 
        else if(op == 3) {
            auto t = tr.query(l, r);
            cout << t.add << endl;
        } 
        else if(op == 4) {
            auto t = tr.query(l, r);
            cout << t.sub << endl;
        } 
        else if(op == 5) {
            auto t = tr.query(l, r);
            cout << t.mou << endl;
        }
    }
}
signed main()
{
    IOS;
    int T = 1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

标签:pre,suf,sub,航电,单峰,mou,add,&&,第三场
From: https://www.cnblogs.com/ZouYua/p/18326802

相关文章

  • 2024杭电第三场
    打了个爽!今天打得很稳,基本没有罚时,相当优雅的一场1001 考虑递推,发现答案和因子有关,再加上森林里只有一棵树的情况(i个节点构成的树的种数为f[i-1])#include<bits/stdc++.h>usingnamespacestd;constintN=1e6,mod=998244353;inlineintadd(intx,inty){return(x+=......
  • 题解:牛客多校第三场 A
    ABridgingtheGap2时间限制:C/C++1秒,其他语言2秒空间限制:C/C++1048576K,其他语言2097152KSpecialJudge,64bitIOFormat:%lld题目描述Agroupof\(n\)walkersarrivesatariverbankatnight.Theywanttocrosstheriverusingaboat,whichisinitiallyont......
  • 题解:2024牛客多校第三场 B
    BCrashTestheader时间限制:C/C++2秒,其他语言4秒空间限制:C/C++1048576K,其他语言2097152K64bitIOFormat:%lld题目描述Afterfiveyears,themosthigh-profileeventinmotorracing,Formula1,returnstoChina.TheChineseGrandPrixwasrecentlyheldatthe......
  • 2024牛客多校第三场
    磨合上升期,爽!B队友做的#include<bits/stdc++.h>usingnamespacestd;#defineintlonglonginlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');for(;ch>=&#......
  • 航电多校 2024 笔记
    01写点赛时不会的。难绷场,可能因为是01所以比较水,就只有最后一个能放省选模拟T1,以及一堆原神题。T5hdu7434博弈小马给出了一个可重小写字符集合 \(S\)。Alice初始时有空串 \(A\),Bob初始时有空串 \(B\)。两人轮流等概率取出集合 \(S\) 中的一个字符 \(c\),将它拼接......
  • 2024码蹄杯职高省赛第三场初赛全题解
    其实吧对于码蹄杯省赛的话,第三场是一千五百多人,百分之25的获奖率,然后前四百名左右就可以获奖,根据排行来看大概是六题左右,其中大概就四题要点脑子,其余的基本上属于语法题,也就是13题中如果语法没问题的话,九题是很轻松的,因为都是青铜白银题,语法没问题的话就OK的,然后就是一个P序列,......
  • 二分【2】快速幂 单峰序列
    目录快速幂递归写法(a^b%m)迭代写法  单峰序列快速幂a^nn为奇数,转化为a*a^(n-1)n为偶数,转化为计算b=a^(n/2),在计算b^2a^b%m)递归写法(a^b%m)#include<iostream>#include<vector>#include<cmath>#include<string>#include<cstring>#include<algorithm>u......
  • 民航电子数据库:表主键为自增,insert时报错:[E16005] 字段xxx不能取空值
    目录一、场景二、报错信息三、排查四、原因五、解决一、场景1、对接民航电子数据库2、表的主键为自增主键,使用mybatis封装好的insert方法新增记录时报错二、报错信息###Errorupdatingdatabase.Cause:java.sql.SQLException:[E16005]字段ID不能取空值......
  • 判断ip地址是否合法(美团2024届秋招笔试第三场编程真题)
    核心思想大模拟-。-,还是不够细心,面向样例编程,一路错过去的。写得太丑了凑合看吧。代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){finallongMOD=(long)(1e9+7);Scannerscanner=newScanner(Syste......
  • 小美的游戏(美团2024届秋招笔试第三场编程真题)
    核心思想贪心,每次选最大的两个~代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){finallongMOD=(long)(1e9+7);Scannerscanner=newScanner(System.in);intn=scanner.nextInt();......