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

杨利霞

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

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
+ }# |! X$ w$ S+ [- ?) d查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
+ M' m" ]. ?& {2 ?9 M#define mem(a,b) memset(a,b,sizeof(a))
2 C& a2 T0 I* R/ E+ ^2 L& F  nusing namespace std;
, s# e! M: x* R) c( a$ Htypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
) \& n! p& C) |: ^0 Z! X- econst double eps = 1e-7;

1 d/ v  Y. U' s# W! @; d* e. i2 mstruct tree {
    int l,r;
' J  @. e! g7 q+ I# Z0 m2 q    int p[10];
} t[maxn<<2];
, R  A7 X0 K% m, I/ D
int l,n;

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

$ x; b5 b/ ]8 ~# x3 J    if(l == r) return ;
    int mid = (l+r)>>1;
+ U! {) j6 g4 V, H1 U    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
}
- W  q( V9 P; @) F
6 Y, a2 F0 f6 A/ Jvoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
4 m) |6 Q+ g9 y: z    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
4 ?4 R8 M' f- G- O            cnt1++;
9 e$ u6 K0 E% [% Z" |1 ^* A  g) M        } else {
! y) j% Z' |2 Z. T4 ^            t.p[j] = t[i<<1|1].p[cnt2];
* c( |& T% i" m$ e            cnt2++;
        }
! M( y0 g% w' o) N    }
0 |6 ~; W& K: z/ T! ~3 N- E    return ;
, i9 V0 d9 `7 e4 x( F% M+ F5 S}
/ c* H: c/ t  H# r4 e
void modify(int i,int pos,int val) {
" m5 I  |* }9 \+ c  b    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
- V! F5 N) d! V        t.p[0] = val;
        return ;
1 s" M8 \+ a2 H, P+ ?& O    }
. p! q( ?$ L- J# ]# Q- e6 |6 k    modify(i<<1,pos,val);
. T" o' t. V% S3 M* g  Z5 F    modify(i<<1|1,pos,val);
. u! z' o& x/ B    update(i);
    return ;
  f: }: e* e1 ^$ P4 v3 t0 u- z}
- S8 F1 n% u% n6 C
) r6 K1 A. B- ]9 A0 H* {( xvector<int> merge(vector<int> ans1,vector<int> ans2) {
* c4 R" H3 a+ l  C; M6 Z. O8 a( k    vector<int> ans;
, G. H' S3 r/ v" W0 f9 g, z    int cnt1 = 0,cnt2 = 0;
- d$ h- u4 a/ X, m' X7 g    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
) a5 e4 [4 j/ x3 g            ans.push_back(ans1[cnt1]);
& Y! ]6 Q. P7 m8 |7 {; x* I8 q            cnt1++;
- r) {) U% E/ _  n" n9 Q  B! P0 r        } else {
2 Q+ K1 |) Y/ a1 V; m3 t            ans.push_back(ans2[cnt2]);
! O! \" M4 \# D% n& k: r3 X+ y            cnt2++;
" J( {/ e+ p- d6 r* S7 ?        }
/ l, c% e- M; Y3 ?, _- t0 [5 C    }
* |9 `3 [# J0 [! D/ P+ k" z+ H    return ans;
* T( O/ z; k) T# Z}

5 s( s- W' B, d& Bvector<int> query(int i,int l,int r) {
# K- C* L  u# F0 @    vector<int> ans;
# `6 c( @# B' ^    if(t.l> r||t.r< l) {
7 g! f! T) [: z. f& ~        for(int j = 0;j< 8;j++) ans.push_back(0);
9 i5 G: f* d" ?8 _% t! I1 \        return ans;
    }

! J# f3 i; |+ @" Z    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
( ]: v  M# f6 R3 t! U        return ans;
& V9 i- g" Q7 e/ b% O8 v+ c; g, e    }
. B. s3 f2 |5 y, Z' A& z
' w' ~  Y5 O5 e$ ^3 I    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
  q9 B: _! u: ?5 f1 E- [1 O! @
int main() {
% b% m/ O1 _2 H( X3 v4 M    cin>>l>>n;

    build(1,1,l);
    char c;
3 ?8 M$ O+ [% N& m' }& M    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
7 O. ]& {0 ^  _        if(c == 'C') {
            modify(1,x,y);
% u5 P4 T$ N2 X5 |) A        } else {
            if(y-x+1< 8) {
                printf("0\n");
                continue;
- n: a/ M; n' a% h+ N) m            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
( N+ R8 X2 U- B9 u+ e        }
; t; {9 B* _4 G$ K" N: @# L    }

" U1 _6 J& L6 D1 j0 e& n% _. o' I  w    return 0;
}

0 J! \5 |" t" w! k---------------------
( H6 d3 F+ h7 ~作者：nka_kun
/ @/ l- j: Y; h& _来源：CSDN



5 J8 Y6 X- Q* Y: u