数学建模社区-数学中国

标题: 2019第十届蓝桥杯B组决赛题解第九题 [打印本页]

---

作者: 杨利霞    时间: 2019-6-28 16:17
标题: 2019第十届蓝桥杯B组决赛题解第九题
2019第十届蓝桥杯B组决赛题解第九题
0 j4 [2 [" f& M# C0 T9 D

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
. h. ]0 ]( i  D; ]$ ?0 P3 a: G9 |每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
# t5 J+ J- w1 Q" d1 @& {' D查询的时候返回含有8个值得list，并不断merge

代码:

# Q: d. A% S8 T6 u2 z2 P+ r, \& C#include<bits/stdc++.h>
$ o. J% x/ ^: B3 m$ e5 V- q" O#define mem(a,b) memset(a,b,sizeof(a))
  }" r" x! [+ V0 w7 O- s1 H; Qusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
8 r0 A4 i" [; U( Rconst int maxn = 1e5+55555;
% _: U3 s: w" _( ?0 G4 I  Oconst ll mod = 998244353;
const double eps = 1e-7;

# u! h5 U+ m0 I' L- V' xstruct tree {
% X+ z  R- l! E+ _0 A    int l,r;
    int p[10];
8 ~1 @7 [8 i6 g% ]# l! `+ d} t[maxn<<2];

$ o- G/ a/ p3 \% Nint l,n;

void build(int i,int l,int r) {
    t.l = l;
    t.r = r;
    mem(t.p,0);

/ D" \4 `  ]( |2 Q; h$ C5 a' D    if(l == r) return ;
    int mid = (l+r)>>1;
8 T$ o" T/ Z0 X3 ?7 j8 e    build(i<<1,l,mid);
  j8 M( Z% a6 \$ f    build(i<<1|1,mid+1,r);
. p6 b* b- R8 u2 c/ e  n' x    return ;
}
+ v3 Q, Z5 u" u/ v0 M
void update(int i) {
& C  P( W- X, C, I4 y# s$ D4 r; W    int cnt1 = 0,cnt2 = 0;
2 G$ k/ }0 h2 F* u    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
  }9 C, R- N  r0 e; r( c2 ]6 D            t.p[j] = t[i<<1].p[cnt1];
! U6 Q! O8 Z  w4 n1 q' ^            cnt1++;
& F+ J3 v+ ^) P9 B        } else {
; X! V% f* _9 v            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
# p& B& ~" Y+ R% |% j: D: o+ V8 j        }
3 j: r8 g$ g0 v+ }    }
# j/ C7 Z  A* W: v& s1 L    return ;
}
0 Q4 c) M6 \" a$ S
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
* t6 `( l: u$ G) M        t.p[0] = val;
1 e6 c0 ^% |1 I% k7 N        return ;
    }
! z- g, R. N8 c; q6 j    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
    return ;
! k0 j$ V( \" x# f( L7 V}
$ W/ Y0 e/ i  m! V
vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
6 K0 S. D: @: T  [    for(int j = 0;j< 8;j++) {
+ j2 o) z- A/ C" A/ h+ W        if(ans1[cnt1]> ans2[cnt2]) {
. U" N( U6 z4 ]& P6 q  C            ans.push_back(ans1[cnt1]);
            cnt1++;
4 [7 g& n+ m' L! U  j1 C        } else {
) q% H1 `. s6 t. l9 T            ans.push_back(ans2[cnt2]);
. d, M, K2 d4 Z. E8 I# P            cnt2++;
2 z% v; Z1 i4 U& b1 X: B3 f& W        }
    }
    return ans;
7 y, a% r) _' @9 e- J" F4 J. W}

9 g7 w5 Y1 t1 f1 ]# \vector<int> query(int i,int l,int r) {
% k* `2 m1 X* A    vector<int> ans;
! L& [& r" I/ Y+ s# ?2 R    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
& H2 q- z8 z% c  t( S# H) v        return ans;
4 b/ K  {- Y* u: M  o; G3 @    }
& m) J1 d1 x8 j2 s$ A+ Y& H+ X
/ R. ~: c2 L& k2 u4 i4 b    if(t.l>= l&&t.r<= r) {
6 X4 _4 d& N  z  T; ?& K/ a        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
3 O* j$ j7 N2 P* p: V& [    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
% B- y0 ]* O8 X7 O
int main() {
    cin>>l>>n;
0 `, E! S" C* d
4 D' a, O, D1 A( o) G$ a# J    build(1,1,l);
8 ?" A2 x2 N$ m- P& m$ N0 b/ o    char c;
, Y' q6 |& ]! M  y" k, o    int x,y;
    while(n--) {
7 |0 e( N+ j% W& j. T        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
            modify(1,x,y);
% ^+ `' A% l+ D1 I. @! O        } else {
            if(y-x+1< 8) {
5 k5 `* p2 b! V2 b* Z                printf("0\n");
' v' M1 G, |% W! q) ~                continue;
8 m1 @' J& N8 `            }
            vector<int> ans = query(1,x,y);
; ~* b' ~& d& n. U7 j            printf("%d\n",ans[7]);
        }
7 d  `6 v; h7 e! _% K! y+ ?0 Z/ m3 G: L    }
+ M0 G" @4 X. S" ~& x5 E
    return 0;
$ `8 R/ E3 L6 n$ X2 n! p! c7 _}

---------------------
作者：nka_kun
0 Y8 y. e2 Y% o; }来源：CSDN

; K2 \; ?9 j% O( z# @* g5 r

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5