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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
7 x8 k9 p8 r+ ^# g! h3 W& B7 m

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
1 l) ?7 \8 l' z" m; {每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
; h3 i1 G! k& _% C查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
* w) ^" K( Y- F# _, m8 \3 Bconst ll mod = 998244353;
( |/ ?, k4 c& H. p3 Econst double eps = 1e-7;
- q* _; Y( r9 U5 `
: x( |1 n" _$ [) mstruct tree {
    int l,r;
    int p[10];
} t[maxn<<2];
, ^9 g% x! Q2 N" P$ I0 Y7 o& m3 j0 \
3 d1 j. v- r7 w  r6 B: r# m7 rint l,n;

; U& W8 u3 P$ p& \( H. wvoid build(int i,int l,int r) {
, b) r  W- D0 d    t.l = l;
    t.r = r;
' r& o/ y2 V, \0 r    mem(t.p,0);

    if(l == r) return ;
. U8 i9 f5 V" q4 b% {) T& g    int mid = (l+r)>>1;
    build(i<<1,l,mid);
1 N  u; q" J% s+ U. @0 S    build(i<<1|1,mid+1,r);
    return ;
}

- Y0 B& t+ f# b) ^void update(int i) {
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
, a& A9 Z' U" d; g$ y. h) I* i7 ]( d        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
6 x7 a) p$ |0 q# r+ E            cnt1++;
        } else {
1 q! M. q( {0 w! r; W# [6 d; j            t.p[j] = t[i<<1|1].p[cnt2];
0 v& O6 x5 Y! l' [6 r+ Z# i0 j! \            cnt2++;
        }
! }- G% h% t6 i$ t4 C4 G% O    }
    return ;
  K. U7 K- w  ]: |}

0 \) w+ n6 w9 D) J2 R& c+ Svoid modify(int i,int pos,int val) {
" A4 a/ a1 R) w    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
8 A! A2 l  t7 \& R1 O7 e6 r! d        t.p[0] = val;
        return ;
    }
: d. a' @! `: Y1 b4 \7 S    modify(i<<1,pos,val);
# x$ u1 W) S1 [    modify(i<<1|1,pos,val);
5 B9 A9 w7 P% K) `0 ^0 _$ t6 i    update(i);
: C' B* n6 z3 g. M9 T* g# x0 e    return ;
}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
5 X& K( m; r  C+ {. }9 O    vector<int> ans;
( {) ~8 B* t! a    int cnt1 = 0,cnt2 = 0;
9 C- `6 E4 g+ v6 P9 X0 |& v    for(int j = 0;j< 8;j++) {
8 Y5 T8 ]- U# q& _. g. l) Z        if(ans1[cnt1]> ans2[cnt2]) {
" _4 s4 n& f, x6 O( e" Q            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
" l2 \; s* \8 x  k- g            ans.push_back(ans2[cnt2]);
            cnt2++;
- }7 |& ?* n% X4 \+ k        }
    }
    return ans;
}

vector<int> query(int i,int l,int r) {
# M+ |% `3 h& E' ]; [' e    vector<int> ans;
    if(t.l> r||t.r< l) {
6 `4 O! O  ^7 A  z- D: ]6 _        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
* }/ t  p/ k$ x! a    }

; U1 C, r6 U; s# S& |3 {    if(t.l>= l&&t.r<= r) {
+ T  b9 ^7 p! d- ]9 p( L        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
5 A, x% q0 X3 c: a5 ~* R        return ans;
5 x6 g9 J+ a% r) |    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
0 o+ f  Q/ ^! ~/ A2 j}

8 W2 B0 z. x2 tint main() {
    cin>>l>>n;
1 j! V% ]9 `" m7 h
, Z( p# ^- G0 v7 J5 C% Q* ~    build(1,1,l);
2 B4 k  `; t; S. F9 g/ B    char c;
6 ^" z" o2 x! C    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
            modify(1,x,y);
7 e9 j1 H4 }2 K* o1 c, S        } else {
5 Y9 T) n: ~4 K            if(y-x+1< 8) {
5 b3 r5 I9 b; K) h                printf("0\n");
/ Y$ t7 d; e( c                continue;
) S( r+ M5 s. j+ N            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
9 S+ I7 G" C" j' |7 f        }
9 r* b" L% q4 w; E/ ?) |* c3 b% y    }

    return 0;
}
7 z" |2 J; V2 U# p+ t
---------------------
作者：nka_kun
来源：CSDN
) S' `' M' [4 P. p
. h  f. X$ a0 h; Z/ x0 s$ P

7 j1 W0 L0 W9 ]) _) X