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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
- L1 k' {7 O7 j/ F6 G0 n8 y
0 I  J9 H* p: s/ b# _

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

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

代码:

; [0 i0 n2 M2 u  F4 B, u#include<bits/stdc++.h>
; h: g0 t$ s6 g9 f  y#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
7 @) ]4 [) j% z, g' y' {typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
( \3 R# W5 L" n9 jconst double eps = 1e-7;
! \" ?% p6 U3 s. n! P- ~1 k
: L- @9 P$ w* v8 q* i' ]- Zstruct tree {
    int l,r;
    int p[10];
} t[maxn<<2];
" \6 M/ z# }/ G( k, T& I
4 E5 h; M% e# a1 I* g. f0 fint l,n;

void build(int i,int l,int r) {
    t.l = l;
: V4 A( T5 q! ^4 y$ m; K1 l* R    t.r = r;
    mem(t.p,0);
- U. O- B9 _7 p# Z# p5 |
    if(l == r) return ;
( f* }: _9 F4 C1 V; ]    int mid = (l+r)>>1;
" k- B* @0 U8 z% w) Z9 E9 W, Q. g0 F    build(i<<1,l,mid);
. |* O6 w) d% [$ B( Y    build(i<<1|1,mid+1,r);
    return ;
2 X# x  o% y! v5 p}

void update(int i) {
  J% y/ V4 R# f& ?* I9 x4 \5 R7 c    int cnt1 = 0,cnt2 = 0;
    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];
# Q$ ]7 ?$ ~' T8 G6 ]            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
+ _0 R) s* K* U4 t1 x        }
1 Z+ E. u5 Y7 E0 \0 O0 D/ x4 Z    }
    return ;
}
# p  e9 h5 o5 V6 C6 M8 l5 T
" c0 l" H4 ^+ w( ^void modify(int i,int pos,int val) {
; P# r# E( M' i- v: H    if(t.l> pos || t.r< pos) return ;
; b* d) s7 p* C6 C; R8 k    if(t.l == t.r) {
        t.p[0] = val;
2 W3 g8 O0 `6 \* {- R+ K7 B; K        return ;
    }
    modify(i<<1,pos,val);
" b3 ?( F- d" `8 z! p6 h% `& d    modify(i<<1|1,pos,val);
    update(i);
    return ;
# w4 e; Y! c! y: a, p}

) G, U, b. Z2 z* fvector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
6 o; K: z2 I7 p2 O5 G# Y            cnt1++;
+ r7 c. B/ V3 D: T) u6 N2 l9 z        } else {
$ h, J3 K% A' |            ans.push_back(ans2[cnt2]);
# l# B" l8 G2 f/ A9 s$ |  b1 I. {            cnt2++;
( \2 |+ v, V. y/ _" R' K        }
6 p% n7 F" p! u' t; b' N    }
1 [7 T6 C0 E/ {8 L. i9 k    return ans;
}
; Q! p6 M1 q7 @4 p6 h0 q
2 b* P( @/ ]6 z% H; M2 R8 x% cvector<int> query(int i,int l,int r) {
    vector<int> ans;
* i; o0 i" p9 Y9 M+ r    if(t.l> r||t.r< l) {
: V0 a) E" g7 b- A9 j        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
4 b7 u  u+ F7 J$ _/ D0 q    }
9 m, \. N: I9 s- a2 l
    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
    }
+ ^! w3 T, {: Z( q7 g
4 V  i4 R  ]- ]2 W& F4 z4 k7 n    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
) M& l5 ]6 s. P+ `/ A2 i! r' H* p) W
' C" F1 ?2 {- W" h! }6 qint main() {
" ~4 P: D3 o1 U: l1 t  T. U, R* N    cin>>l>>n;

. L3 @2 ~$ U% p  {3 k! _& }    build(1,1,l);
- M' e5 y# ]' j  \3 e- M4 y2 [    char c;
    int x,y;
2 T2 e8 l* b% q3 K1 o5 L3 g( p    while(n--) {
( P" j: z+ }+ }        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
) z% w( K. [0 Z# g/ p8 V            modify(1,x,y);
; [1 f' a, R2 I: [$ ]. B        } else {
! l! y( E) h1 B6 o  H            if(y-x+1< 8) {
: K! `  X& x8 h* y: {- V' r                printf("0\n");
% r3 E: D0 J# j                continue;
4 M0 @4 u. n+ a; X: o            }
            vector<int> ans = query(1,x,y);
( Q2 a+ _! C, V2 C. P4 y            printf("%d\n",ans[7]);
        }
8 `" R1 z* A7 O# J/ |# b, t, e3 e    }

    return 0;
, {3 _' e7 R# p}

---------------------
' Z0 S* v/ J2 L" a: E作者：nka_kun
来源：CSDN

% {6 V( {2 R3 {5 `1 q1 ^' l& X