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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
7 k2 x1 Y: Q# A( E: p1 f

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

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

代码:

7 F, n7 n, p* z% Y+ C$ f  D) t#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
% E3 h# T( c2 W" e+ I3 h3 D' ausing namespace std;
typedef long long ll;
& @# J$ h) n! r' ]5 F0 Q3 @const int inf = 0x3f3f3f3f;
0 m1 \( {$ l% n# k5 d8 Iconst int maxn = 1e5+55555;
  ^. [2 d- Z2 l: J1 f* |' G$ X. dconst ll mod = 998244353;
6 a1 V5 e  d. l+ P. v, Bconst double eps = 1e-7;

struct tree {
    int l,r;
    int p[10];
} t[maxn<<2];
5 J$ V) k( d% t3 F
int l,n;
/ W, l$ w3 v5 A  k6 K, b7 P' f
3 s/ O* |/ H5 J: Z4 R6 cvoid build(int i,int l,int r) {
2 A9 c, E. ?% a4 z% J    t.l = l;
' @3 V5 a6 v; \- W( a    t.r = r;
# w$ S5 S# O  {    mem(t.p,0);

( F: z+ O! B+ W    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
) C6 A: k( U' t" |    return ;
. t' u; @. ~3 h4 n* T}

- X$ f! h2 A3 N. P% ]/ f5 v/ qvoid update(int i) {
# B1 E+ m+ J1 ^3 D    int cnt1 = 0,cnt2 = 0;
# b- X: k8 i% d6 k    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];
- e8 V+ y' F# C0 P8 S6 o" j7 V3 I            cnt1++;
3 k) i" f! l( E- f9 C4 B        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
9 B3 \, f6 P5 g+ H6 y    return ;
8 N  z) X- m+ V: w" M% |+ ?( w0 {7 o}
6 J* X% B+ a; `, Z- b, `5 a
+ R' z5 e% C! ~7 |2 xvoid modify(int i,int pos,int val) {
( e. E: P' T. _9 ^# [5 ?% C    if(t.l> pos || t.r< pos) return ;
: R7 a- a. |6 D+ p$ {# N3 x    if(t.l == t.r) {
        t.p[0] = val;
        return ;
& _9 ~1 {( ~8 M- x- E    }
    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
/ ~! B: P- _9 H  Z. v    update(i);
$ O4 I# y: T- _    return ;
( {0 Z4 p8 n7 O7 S}
8 S! ?! a2 }( d6 k7 M3 s% l( K8 w; K# |
1 |% s1 P# {& L2 n9 A- W8 jvector<int> merge(vector<int> ans1,vector<int> ans2) {
" i# s2 `% e: u6 X    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]);
            cnt1++;
        } else {
: l: u5 R' t( N+ Z/ m% }( ~            ans.push_back(ans2[cnt2]);
            cnt2++;
% A) b) `6 v' P% Q, l! N        }
' O! s* j" f/ o# \- N    }
5 i4 Q; [# k) w# Y    return ans;
) x4 ]% x2 d6 ^- e}
4 a' I) h  t- z; y+ y
vector<int> query(int i,int l,int r) {
    vector<int> ans;
3 \% {, r+ r) I& A& y" [2 R    if(t.l> r||t.r< l) {
" w  O/ V  P3 H- q& z5 }$ G        for(int j = 0;j< 8;j++) ans.push_back(0);
/ H! C  e5 A7 r# A4 A: P+ R        return ans;
    }
) s+ @1 E. [' O# O$ P( E
    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
3 t  Y+ {, G& b    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}

/ ~; z0 a- L4 z. l& Aint main() {
) N, C7 n4 j9 u( w    cin>>l>>n;
; v8 \6 d1 ]: y1 h
1 r  U# z: F$ K/ I0 a$ x    build(1,1,l);
! u/ K1 m) k( q, x) r    char c;
' @3 D+ b  I# V  {7 G* p    int x,y;
# e6 l5 O7 G% W$ k) a    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
& `. L' e5 K* V' z) E        if(c == 'C') {
) q) A. h" m) K. f" [            modify(1,x,y);
9 T" [% K" e4 X; m3 l        } else {
            if(y-x+1< 8) {
                printf("0\n");
% v9 B+ \/ w; r                continue;
            }
3 O% Z3 B3 G* d. ]# ]& o; B  \1 ^            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
* S3 ?0 g4 F4 t* {9 B        }
    }

, d9 Y( W7 n- I+ j* T    return 0;
4 l1 W. m& ~" e% s}

2 V& |) q$ v3 G  }" Q# @---------------------
作者：nka_kun
* G6 p9 S! x6 U来源：CSDN

) U  V, K) ]# H, Z
3 J- g# ~7 |1 c& R* G4 h