数学建模社区-数学中国

标题: 2019第十届蓝桥杯B组决赛题解第九题 [打印本页]
作者: 杨利霞    时间: 2019-6-28 16:17
标题: 2019第十届蓝桥杯B组决赛题解第九题
2019第十届蓝桥杯B组决赛题解第九题
- z+ U8 p/ O5 |, h# X
/ o( U+ Z. I' ?

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)4 Q3 A" S! `& ~2 o: K. k
每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
8 [) i. D. Y1 w7 c" Y$ _查询的时候返回含有8个值得list，并不断merge

代码:

3 v. ?9 X. ]0 R- o+ a1 G
#include<bits/stdc++.h>
4 r/ q% T% ?5 f; Y' x#define mem(a,b) memset(a,b,sizeof(a))
6 P+ C5 X; D" h9 Zusing namespace std;
* t( T" {- C  qtypedef long long ll;6 C6 r" o7 [2 L( L4 h
const int inf = 0x3f3f3f3f;
' D$ W8 L& |. d- u7 X5 Tconst int maxn = 1e5+55555;  E8 [( s; e5 j* y9 a( C7 U+ s
const ll mod = 998244353;
, W$ x8 e2 {! z, @' I- \% dconst double eps = 1e-7;0 X% E; B; G: @7 h0 v% U

8 A: A  Y9 {9 G8 xstruct tree {
3 {% H! N5 p$ V9 J: ^    int l,r;
: J- `) J; `: C    int p[10];
1 f- ]4 }8 S8 j4 Y6 m1 ?* E) v! f} t[maxn<<2];5 h5 @* R8 Y: T2 M- N3 R
- E( V/ x) h5 W" b* J7 O8 e
int l,n;
) j! f& j4 |% f; v0 L1 r: w4 t# ~' h1 d' B9 J; c
void build(int i,int l,int r) {
. k6 S) S) Y$ y$ i: h; w    t.l = l;
2 ]; d+ H. ?3 ^    t.r = r;
$ n$ U$ h- C) L" @- X5 X" h+ S    mem(t.p,0);1 T$ ?5 L; J# a2 \# Z9 o# H, G
2 k& U: B2 J/ B# |7 a/ q3 o
    if(l == r) return ;
: l+ r9 e) i& l' X    int mid = (l+r)>>1;, h/ [0 P- ]; V9 ?- Z2 o
    build(i<<1,l,mid);
' R$ S, Z8 a, c, S1 f4 D    build(i<<1|1,mid+1,r);
5 I# q& g8 P/ g$ c! A# L2 r; h    return ;
2 A' p/ Y$ O" o( S}
! R: C! J$ C/ Z3 z7 j7 K# P4 d4 P; a; p6 n; S7 n( |9 F
void update(int i) {5 Q% ]6 A: S& T# K
    int cnt1 = 0,cnt2 = 0;" |& D- G* B$ @/ [% S2 }
    for(int j = 0;j< 8;j++) {7 C2 Y1 q$ z% I  O  }+ K5 I7 z
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
7 [* j1 N) r" J; h# L+ a' t& a# q7 f            t.p[j] = t[i<<1].p[cnt1];
1 ?0 o5 p* l% h* \# n" J/ C            cnt1++;) [& D% |  M5 J) n$ p) P
        } else {, q( v4 Y2 t$ {5 z; y8 t
            t.p[j] = t[i<<1|1].p[cnt2];+ Q& ^1 R8 ^/ T3 I( H! R
            cnt2++;8 ]1 J3 J7 m# Q/ d$ a/ E
        }4 _/ v- M. n1 T( e  ]- z7 G
    }
- h& {8 C9 w* }5 G$ m/ B: b+ `% g    return ;
# y1 a  v/ E  K3 l) `: G}
4 V+ P( d' j+ K" V! A& z# N9 c$ K$ v' h) e
void modify(int i,int pos,int val) {
3 B3 ~! j4 ]& t9 R    if(t.l> pos || t.r< pos) return ;
8 e& l0 B, r" x% m% k+ ?    if(t.l == t.r) {
3 i( A3 K8 ^; t) M3 \        t.p[0] = val;
5 v  I) \7 `2 t( |; e% U9 N4 y! w# v' V        return ;
' Y' P. D1 o- U( i7 s. H    }' z) J* |8 t2 Y
    modify(i<<1,pos,val);* O7 W6 F$ X& K4 m8 ?1 n% \
    modify(i<<1|1,pos,val);1 P( C+ Z( U0 x( c! b1 L- w
    update(i);
8 m( z- D  H+ D3 I4 K3 ?    return ;
& A5 `1 N" H4 t! `) ]5 G- r' {" }}+ f: T# w' @4 W8 S; i4 D
& Y/ ?0 o  }, O$ f+ z0 o
vector<int> merge(vector<int> ans1,vector<int> ans2) {
& c3 E* A2 b( q# J    vector<int> ans;& f, }9 f" F. Y% T1 \2 I
    int cnt1 = 0,cnt2 = 0;# E5 s5 q! q6 J' O- N+ z, L" v: u
    for(int j = 0;j< 8;j++) {
1 ]4 U( U+ T: ?7 m4 V" H        if(ans1[cnt1]> ans2[cnt2]) {2 V& o+ p# W0 |9 D" x0 x5 \' B
            ans.push_back(ans1[cnt1]);. V# o! V6 R* G% J
            cnt1++;
+ x+ w7 u/ F5 n9 u* ^- H        } else {0 x( M5 ^& v; a9 W! i
            ans.push_back(ans2[cnt2]);
# v* n- [! m! ~/ G# z7 z5 s$ f            cnt2++;. S7 u( [- T& y- f
        }/ V0 u8 o" M- ]  B* [) U0 X
    }" H+ N4 a! i8 F. o" e# m
    return ans;  ]" I5 r* b, i8 g' ?* h
}# W( n7 n; w4 \9 \% v( p# }4 m6 c
+ M2 l6 m% r) v; j5 K4 p
vector<int> query(int i,int l,int r) {8 S# ^2 l) H# Z9 @2 q5 ]9 a
    vector<int> ans;
" e* R8 z: h( [* g1 t- l' R    if(t.l> r||t.r< l) {
/ h. I$ O2 l3 d' Y        for(int j = 0;j< 8;j++) ans.push_back(0);8 L3 y3 a0 x7 y5 h0 k/ F6 Q9 O
        return ans;
7 U- M- |* A; u# S' B6 Z    }
" @, {: x  ?3 c% T( F  ~; i5 J1 T* H! R  |& C' \* A( ]
    if(t.l>= l&&t.r<= r) {
& S, {' ]" _+ l; l        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
* V) {2 u% q# a0 l        return ans;2 [* q( V* C  A9 Z; k4 R
    }% \# X( c# I0 R9 \; v  L: n
! R5 D1 l  p% z
    return merge(query(i<<1,l,r),query(i<<1|1,l,r));% _0 k+ P$ A! I( B  Q
}+ P& Q) |2 D/ f% T9 d  j

% p' ^* Y* a* j2 }- O3 S1 [: c$ cint main() {! Z0 X& Z. |4 ~8 q
    cin>>l>>n;
) u, }, q5 n0 h1 k" E- _; k1 s, i  ?, N
    build(1,1,l);/ z9 u9 [  X. B7 O
    char c;
# p" Q- E; f8 A! s& K    int x,y;$ V" I7 m% H( W" F4 e
    while(n--) {5 C: n# j+ m8 `2 F
        scanf(" %c %d %d",&c,&x,&y);
9 h- u% d% u' W0 N3 D8 [  X* m        if(c == 'C') {4 i8 U0 R; M6 b, c# Q4 V
            modify(1,x,y);. f# p) J: j- N* P( P
        } else {3 P; L, [9 H. s4 r/ Q) u
            if(y-x+1< 8) {
/ j/ o! o1 U' B2 ?. x                printf("0\n");
) V$ M/ O# s) W- V& Z* @- i- j; B! e                continue;
: n$ m/ y0 {: f1 F$ @5 t            }7 F* O" n, b; |( @/ N+ f! [- t) A; g4 p5 |
            vector<int> ans = query(1,x,y);1 x) b  _1 r. u3 o3 K* T% l# a
            printf("%d\n",ans[7]);, I1 E* N* |7 I: _. ^, U6 Y* J! _
        }* r/ b. x6 v8 U4 q, Z% h
    }' V; h. o1 d3 A8 h5 t
# m1 A* Y' P; A$ s
    return 0;
2 f% S  q, b' a) W( B( Y+ v, r0 S}( V, Z$ u, _& ~+ ]+ d: l! D
/ j7 b2 w8 p* S$ j' E( Y/ p2 X4 a1 s
---------------------
5 `% _: ~; O2 j- j3 n: x3 }! ~作者：nka_kun
9 v- C* g7 D# [* n" ~% q来源：CSDN
$ |) M. Y$ M! y/ k- l  x. u. I$ F( ^

0 @4 l$ m( n, F5 E! D
! g5 G* Q7 \8 E% ?. c



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5