QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2259|回复: 0
打印 上一主题 下一主题

2019第十届蓝桥杯B组决赛题解第九题

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2019-6-28 16:17 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    2019第十届蓝桥杯B组决赛题解第九题5 Y- [8 X: @  o+ w7 _- B

    5 k. R3 {5 U( C, R2 M* g- ~

    题意: 两种操作,C x y,将x位置的数修改为y,Q x y,查询[x,y]之间的第8大值,y-x+1<= 8的话输出0

    思路: 区间第8大值,线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)( l+ N6 L4 h6 F6 L
    每个节点存储它管辖的这个区间的前8大值,修改的时候暴力merge,单次修改复杂度log(n)*8
    3 @! H. I( n2 r3 d  `- j查询的时候返回含有8个值得list,并不断merge

    代码:


    . ~7 ]' t1 n+ y5 [  K#include<bits/stdc++.h>; h8 I! V+ d; f9 W3 z1 N  F" }. V  q5 X
    #define mem(a,b) memset(a,b,sizeof(a))
    0 n+ S& n' i& w0 y; gusing namespace std;
    ! O" R- K+ u  _" A" M  Vtypedef long long ll;
    8 D# W8 ]; i7 A. ~, Z4 r- ^. cconst int inf = 0x3f3f3f3f;9 ]3 `. p5 V$ b" S! A
    const int maxn = 1e5+55555;
    ; g% \3 q! {+ n! O* i6 Iconst ll mod = 998244353;- j& n3 N" T# `/ i
    const double eps = 1e-7;
    , j1 _/ z3 f3 U& {$ ^0 }
    ( _4 s6 T0 X. x- `8 ?2 f( estruct tree {4 p  ~; b! ?! C: s+ u( X% l
        int l,r;( U4 L/ `0 r% C) r5 J7 P
        int p[10];
    # _! O6 S* a1 h} t[maxn<<2];% U4 s% V) O: U2 \

    ) O3 X- b  ^5 [" l) Y! hint l,n;1 H7 G" v+ K& _  ?  F9 G

    . V( p4 o. w) Q- a- Y/ \0 F* Yvoid build(int i,int l,int r) {
    $ ?& |& d7 Y$ h! P1 K    t.l = l;' }  p' _4 F2 A+ P8 |
        t.r = r;* \2 z) j* U0 L; a% ], z- |7 S% h
        mem(t.p,0);
    7 G, J, a; X) d9 j3 I
    4 x/ D" u( B0 n% C; Q    if(l == r) return ;
    , b3 {& |$ e# o( f. u9 K. _    int mid = (l+r)>>1;
    ' `. ^1 [( Y) T" U9 r    build(i<<1,l,mid);
    ; M; Z7 K; [1 Q7 @    build(i<<1|1,mid+1,r);2 Y/ v( t! y( F6 P, j2 g
        return ;
    7 w; c/ q9 t1 B}
    4 |6 o8 h& b  G; ]  \) \, V
    . C% y1 d1 F( e8 ^; \! r/ qvoid update(int i) {7 X& e- R4 u6 k* P. O" _
        int cnt1 = 0,cnt2 = 0;, U" m9 o* Z, L6 I
        for(int j = 0;j< 8;j++) {1 U5 Y  _  p7 `9 n( Q! w) y
            if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {4 d1 x# Q. w, h" ]
                t.p[j] = t[i<<1].p[cnt1];+ o: P! D) \7 x- n
                cnt1++;
    : G: q( A& q4 M* k        } else {2 r- m7 G! L1 K) k2 ]
                t.p[j] = t[i<<1|1].p[cnt2];
    " i% N3 ^9 B2 F  Q            cnt2++;! P( v! B3 s' i* I" L, k3 r8 O1 F' I& H
            }
    , l3 ?; S- \1 }) g2 t    }4 U$ I5 R  p7 `2 W& A1 s& {' z
        return ;6 E' b$ u+ o  U+ `3 b
    }
      u9 H# u5 x, K1 A- H% ~' N% c$ l% z9 l& `  |1 J
    void modify(int i,int pos,int val) {
    ( Z% [& l+ E* P0 W" g    if(t.l> pos || t.r< pos) return ;
    - T# n* X2 h" ?7 L! n: c    if(t.l == t.r) {; O5 z( U" S6 X/ p& v  G" _
            t.p[0] = val;5 `' n+ O$ m% _0 _& F
            return ;
    + {2 ?1 W. ?4 [: d5 n5 `    }
    : r% J! ^) F. H    modify(i<<1,pos,val);
    ( v" _$ @8 @8 r. P2 h/ D. b, Z: u    modify(i<<1|1,pos,val);$ X7 W0 ]+ f1 ]% ^
        update(i);
    4 w4 R$ R8 V; F# h7 N    return ;
    8 V" }) z/ \! r}9 ?& E5 A& _% ]  w; O( z* H

    $ C5 n. y, d- Q# Z* Q9 ivector<int> merge(vector<int> ans1,vector<int> ans2) {
    + ^; t: J& I- \    vector<int> ans;. l6 c! ~9 j" s1 v5 F! u9 J- e
        int cnt1 = 0,cnt2 = 0;
    & k- y$ X4 O$ N. X' B# x6 ^1 q    for(int j = 0;j< 8;j++) {& `( l/ {4 ?4 o
            if(ans1[cnt1]> ans2[cnt2]) {; V; ^/ y2 w) H0 [
                ans.push_back(ans1[cnt1]);
      {- H: K# Q0 r" b% x            cnt1++;) Q% V2 W1 b1 c# ?! u* L5 H) }) K
            } else {
    & t  L  N# s2 \* y3 {            ans.push_back(ans2[cnt2]);
    5 m; \/ k3 `# {" @' [. B# [            cnt2++;
    1 I: b& p! n9 I2 C# Z& ?        }- l' @# ~3 p  _! O% `
        }3 a1 A0 I" k' ~# H
        return ans;& ?; u' F  f3 p3 Y$ O# ?$ @2 _
    }
    . [- o: T# s. x, }' ?: e* Z1 d& `
    5 r% _2 f) O7 d' `vector<int> query(int i,int l,int r) {/ d0 @/ g, t  V8 d/ S
        vector<int> ans;
    - m& y) ~" Y' g" e- D% \' A" i$ a- Q' i    if(t.l> r||t.r< l) {
    - V" V. z3 X4 g! f! G  g        for(int j = 0;j< 8;j++) ans.push_back(0);/ b4 A: Y1 {5 j7 N- t
            return ans;) S! K* [' Q. \6 r
        }0 p* b. M2 i8 d/ F
      l% h+ M" {8 l. h
        if(t.l>= l&&t.r<= r) {8 Q( b3 {0 o/ j7 P0 S
            for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);1 @) _6 O% V# Z$ U
            return ans;4 x3 `% |4 E) [1 }, C
        }
    & a/ V- H! ?+ m+ t: k0 v- J! f- y$ g' i4 f- G6 B; Y- O8 i
        return merge(query(i<<1,l,r),query(i<<1|1,l,r));
    * ^/ T4 W# ^# ~8 i5 C; R}
    5 `6 [0 {2 c$ C
    0 z2 o6 c$ Q/ N, oint main() {
    6 Z) Y* v, V5 Z; K6 `    cin>>l>>n;. M0 b; j$ r* ], O1 ^' F& J
    3 ~. _1 R7 c" m; m- ]: V
        build(1,1,l);
    5 H* L5 ~' j7 ^4 a( r/ q: c# M    char c;" k1 K  M$ u& O" z
        int x,y;
    2 w7 j9 S8 l) A5 I$ _9 ?" R  A    while(n--) {; v1 E* y; U' U6 C/ m0 z8 {
            scanf(" %c %d %d",&c,&x,&y);! d0 a5 z2 _% ^+ u0 i* g
            if(c == 'C') {
    1 U" e1 _" e$ a- @            modify(1,x,y);
    # q" t4 K+ D7 q, n( O        } else {
    * y4 ^' w- v' H8 `            if(y-x+1< 8) {+ ]1 E8 @6 N1 y# h8 m3 f- d
                    printf("0\n");
    8 p- ~  E. F; A1 x                continue;
    - Y1 p: ]+ e0 u' D! W            }4 R6 q1 c! |- ]
                vector<int> ans = query(1,x,y);& _1 p9 N( Z8 q8 z; N: E- h
                printf("%d\n",ans[7]);
    4 B0 J; g0 ]# Q        }0 x8 g& k0 m1 w# W# \# u$ N
        }
    / U  X+ T& [% m; g( O+ ^+ r) x% W! b! O' S' v
        return 0;
    ( O/ u* d8 ]+ a/ P) |; z( P}
    3 Q1 K3 b8 Z5 W: P3 ^: t' \+ z( n3 L% ]: [3 d, e- D
    --------------------- 8 j1 _2 C0 y3 U
    作者:nka_kun * |: m, g  @: F
    来源:CSDN
    ( {% D8 Y5 m1 J; M
    7 [& v) X0 k5 p) |$ z' L" L3 L
    1 C( s& I4 D! \- m) V8 U5 l( J0 g- C. h
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-5-28 16:54 , Processed in 0.414495 second(s), 51 queries .

    回顶部