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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
2 Y: h/ d; Y2 u8 o* k  q* |
* _: ?/ P3 T( D+ \* Y& t

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

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

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
6 p# t0 n. P* ^6 Fusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
  u3 X2 Y! d" s5 r' @8 F/ |const int maxn = 1e5+55555;
# m, j  Y7 H7 t' @4 ~  N+ Z- v; uconst ll mod = 998244353;
const double eps = 1e-7;

3 K! `. C& a7 F4 `- w% U  Bstruct tree {
4 o( ?& Y% U2 k; \! L/ s/ Y* k    int l,r;
/ x5 E' ~4 H( ?    int p[10];
} t[maxn<<2];
' y- _0 I8 Y9 q* W
int l,n;
3 c+ i* d) q/ N$ s
void build(int i,int l,int r) {
8 ~: K9 q9 B3 V( K: \/ \) @    t.l = l;
    t.r = r;
! p0 P" u, f$ s' r! {    mem(t.p,0);
$ U) F2 M" X0 C, T3 n1 c; I
" f+ {( p- G6 m9 r, D+ M* N    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
$ L' {0 G6 C2 p! b' G( _$ A6 t    return ;
}

void update(int i) {
    int cnt1 = 0,cnt2 = 0;
1 v( S1 y4 k& C  f3 p6 G' r    for(int j = 0;j< 8;j++) {
* m' M* e. p- M; V) j  M        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
" [* Q5 Z: A" b( z            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
6 R8 M! Z8 o$ i. g    return ;
}
& i# W1 z7 s* y1 {
, K8 D+ v1 p. @+ \, P- @void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
- M9 ~/ g  U9 d6 H( d" k    if(t.l == t.r) {
        t.p[0] = val;
        return ;
! T! s3 b/ k6 u) Y1 [+ b/ r    }
3 S' P! _6 m) A  [$ |+ V5 ~    modify(i<<1,pos,val);
. T+ x& g, d! T, g2 |) f2 [    modify(i<<1|1,pos,val);
9 z8 y' G  q! e( |; O; q$ V5 f    update(i);
3 ^/ \9 S0 W  \4 y1 T. J+ ?    return ;
$ w; Y: o$ f8 H6 a( t9 j}
# T3 _8 K' T3 ^4 x# B% k
vector<int> merge(vector<int> ans1,vector<int> ans2) {
! a" G, b$ N7 N. H, }4 F+ Y    vector<int> ans;
. A) k# [/ V  A1 L# K    int cnt1 = 0,cnt2 = 0;
8 U, H: Y; y: I' n: e    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
' i$ ]" ^1 e  p2 V" x            ans.push_back(ans1[cnt1]);
! k  B8 r0 ~- h. J            cnt1++;
5 j0 M/ L! \/ L, I  r* L5 S        } else {
            ans.push_back(ans2[cnt2]);
; F+ b; A% C) S# g' Z- K2 w) U            cnt2++;
" s* x  i5 a& d. R1 c0 K0 O        }
    }
    return ans;
$ n, }1 X  z7 s! G5 k' {}
) a6 y9 i& X' N5 d
$ k6 L& z& s8 S6 b' `/ dvector<int> query(int i,int l,int r) {
    vector<int> ans;
0 h$ X- b9 t; p- T# ^    if(t.l> r||t.r< l) {
$ t9 {3 R8 Y1 P$ P8 P3 C        for(int j = 0;j< 8;j++) ans.push_back(0);
. \1 O( u- a6 ^1 ~        return ans;
    }

    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
    }
2 p& _1 y7 K0 f, E, Y
4 D7 }$ Y' J! `7 ^    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
0 Y$ P4 P  Q" W" W: y( x}
& `0 U4 C* X2 C$ B
: y, B1 l. V" b% fint main() {
    cin>>l>>n;
" t- r5 \' j( ]& |& G5 t
) V9 h/ R6 a# ~2 Y# z8 y/ Z$ X    build(1,1,l);
% }# U1 R( E  y7 J- F# u    char c;
0 x7 D! B, ~/ j+ w    int x,y;
    while(n--) {
  r7 T. ]" n  p        scanf(" %c %d %d",&c,&x,&y);
* ~( g: z* Q8 I' V        if(c == 'C') {
+ f) B% K5 X. L: w            modify(1,x,y);
/ U6 m7 s4 o( {        } else {
: d+ Y4 q& a& {# O" v            if(y-x+1< 8) {
                printf("0\n");
                continue;
            }
: P8 X9 ~+ Z- n% x* V" {& u. Z            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
, R/ o" q$ M& ?. e' M        }
    }
/ j/ W, C: ?3 b
    return 0;
) i. E( C1 w" W6 r3 w  j}
3 i5 Y7 A( g8 \$ S* v4 }1 r/ N
---------------------
作者：nka_kun
& |* Y4 x" _4 [2 |: G8 j. j* z来源：CSDN
. X' g4 M1 N! Q7 ?& U6 E' `8 I' p8 W$ q