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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
5 y9 p+ T& c& O. u% C% V% s
  K- n7 f* M; o" l. B

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

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

代码:

) s9 I" h% }8 i( D5 x+ X$ f#include<bits/stdc++.h>
& {* C: c: j- y#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
- c7 i& X. y  y3 `" u- l4 c  atypedef long long ll;
3 c) Z5 d3 w8 Vconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
$ d/ v' W7 P  j0 i2 \! ?
4 A7 y( R: @6 a& X% }struct tree {
    int l,r;
! }( {. y& n% `    int p[10];
, F) q2 m! t! D4 {1 \} t[maxn<<2];

int l,n;

$ k# L, c0 e1 ?& ?- Gvoid build(int i,int l,int r) {
    t.l = l;
    t.r = r;
    mem(t.p,0);
3 @# w3 @; b* J' a) N/ i( j8 I# q
    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
9 w; t, @) k" V, R. _0 S}

% b1 w9 T" R: Bvoid update(int i) {
2 Z# N* y+ c, }3 _4 W: N. K    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
, Z8 K! [9 R! j! b( w8 Z  h3 T6 O        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
  n/ ?1 ]4 ^, Y; J9 O9 k/ w( `% o            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
' @3 f* I: N; r1 O        }
0 @% C! B1 i" ~. Z8 a. c$ F    }
    return ;
}
# p  Q& K; v0 ]# p
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
+ Y7 b5 i, }- A. ?' P6 P5 g$ ]        t.p[0] = val;
! h8 f2 J* ^4 K, x1 ?# C7 c0 T        return ;
    }
" X9 |& J2 n; p' H- @    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
4 b. g; t6 I5 ?1 G& {- a" v    return ;
}
: e) }" i) h2 Y; p& A/ I8 w
vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
$ c$ B8 x0 w: `, m    int cnt1 = 0,cnt2 = 0;
0 O' _5 _, r) y. e: v! W$ T    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
# Y% D7 l! n5 S& n0 n            ans.push_back(ans1[cnt1]);
            cnt1++;
5 m( H& H, P. ~        } else {
0 e+ J: Q. q5 e3 S( ^% p2 G+ g            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
% \! ^! g" p9 {# o. q5 E    }
1 D# i& T1 [. o* H/ B; s    return ans;
) z9 U2 Y% J% \2 o4 M5 u+ T' ~( V}
, ~6 n$ `# W! c/ w$ w  s, }
, R- Y$ P, v0 I0 b; b- y, G6 o- ^0 [vector<int> query(int i,int l,int r) {
) N( L/ N6 a6 s3 C9 W    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }
5 M# g! U. H* U0 C
    if(t.l>= l&&t.r<= r) {
) w- Q/ R: M2 Z/ W% I        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
+ ?3 o) C- y0 i2 c+ V6 G( m        return ans;
' P, @# i5 [3 Z; a/ t9 X! ^    }

! f# K6 y7 a% _. c+ U    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}

9 G3 r6 k* p, k' _6 i/ B! B* eint main() {
2 D  w" i1 o5 j7 o/ L; L( R" T( f    cin>>l>>n;

# u6 R. |& H; H% ^$ h# I8 \    build(1,1,l);
* y, N! T+ @. D    char c;
9 B" R8 J/ L3 r2 A$ ?% i, E    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
' p. U4 \5 t6 x3 E* q! j: l& c* B( @            modify(1,x,y);
& P: j, b5 {0 I4 L2 j3 A" g        } else {
            if(y-x+1< 8) {
                printf("0\n");
, _8 M" \, `* D2 f                continue;
            }
            vector<int> ans = query(1,x,y);
: ?: [# b4 H3 s" t; O' j/ Z' ^            printf("%d\n",ans[7]);
% h5 E5 F7 u- P; c* m7 ?, K) Y        }
5 d+ f4 i& q/ F" O* p    }
) {- ]/ S7 h4 v2 `7 a) l2 o
    return 0;
4 L0 j+ F, }( R% w}

7 V! H! [. u! Q+ j( R1 T---------------------
作者：nka_kun
! g3 n: a2 `  l2 \+ K7 v* \来源：CSDN

  I' F7 d6 C+ A( x+ N+ ~