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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
; m" S0 n0 m1 _7 g: `7 z5 V6 x
. t% z. z5 e' Q$ J

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
  v3 I. `* a- E5 y5 @每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
. M  F; F9 c2 @0 F" ?* j$ U查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
. c; j: L' [0 v" z3 ntypedef long long ll;
$ ~1 U: {8 C0 ^  q/ \, _const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
+ V$ @1 A, y9 c3 a; ?7 @const double eps = 1e-7;

struct tree {
4 _& f/ B% |2 q5 f% q4 Q    int l,r;
; D9 Y: X& C  Y4 j    int p[10];
& [5 j/ r' v/ W} t[maxn<<2];
: T1 `4 B* `- ^  U
int l,n;
' \1 \1 b! }& G0 g, ]' Q
! Q, {. B; v1 k! }/ U$ mvoid build(int i,int l,int r) {
# V+ v, c8 _. Z) [2 g6 O5 H$ p' V    t.l = l;
    t.r = r;
( p& ^! t  l! |, \! q- r( s4 T- d7 I    mem(t.p,0);

) {; K4 L9 l7 B" ?$ w  s% C. h    if(l == r) return ;
    int mid = (l+r)>>1;
; H0 F* T# ^! M) D3 _6 s8 q( L( ?    build(i<<1,l,mid);
" p0 ^: g4 N. _0 a7 n    build(i<<1|1,mid+1,r);
    return ;
0 Q4 n6 H9 e' x! h, b( F}
5 V! f$ P' v9 ^3 p. Z4 M5 J
7 C) }% X' p/ t; C5 E+ Q( Q& {- e/ Rvoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
4 C3 u  g( u# |- m, n        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
8 I/ L  c$ Y, ~" e# Z( n. b        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
# Z* Q/ x9 K& B* ~/ Z0 G    return ;
}

5 W4 \9 Z+ `1 gvoid modify(int i,int pos,int val) {
# B3 a) s# Y' p    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
5 D0 c/ y, E: ]% n$ `9 m$ m        t.p[0] = val;
" n! y$ c, A9 k        return ;
    }
    modify(i<<1,pos,val);
0 N4 H5 i& q) g4 P7 l! B) m" X    modify(i<<1|1,pos,val);
0 u( h3 u3 h: ]6 [" L3 T0 b    update(i);
    return ;
}
9 h  M" q6 V$ H# ~0 A% M
vector<int> merge(vector<int> ans1,vector<int> ans2) {
: }; ?9 w4 x& p( o3 g% n: d    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
+ x9 t% }( P0 C& ~2 k- e    for(int j = 0;j< 8;j++) {
, B0 L, f. n# ?; \7 Z4 _        if(ans1[cnt1]> ans2[cnt2]) {
, {, [0 X, \' P% R: x) W. O            ans.push_back(ans1[cnt1]);
            cnt1++;
" n% z! b3 P+ Q# U4 j        } else {
! u; T, }$ i* _, k            ans.push_back(ans2[cnt2]);
( Y. |1 d2 P6 O            cnt2++;
, L% e0 E# N" V, ], s. d        }
    }
6 s5 M3 L# l3 i; K6 E7 e    return ans;
}
3 ^6 r- j. w" J) W
vector<int> query(int i,int l,int r) {
    vector<int> ans;
    if(t.l> r||t.r< l) {
- F. q# m2 B) X+ w4 P1 T        for(int j = 0;j< 8;j++) ans.push_back(0);
* X4 M/ w3 T# k$ O6 D& F! E2 O        return ans;
( Z& W$ |  z( G  N" r0 h    }
) r1 f" W- m  t/ z0 R( Y
    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
( Y9 J* z; V3 t! T7 t3 [        return ans;
    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
! z; W, {9 q: o0 V1 z
  c7 W1 T7 G( l3 g/ Mint main() {
    cin>>l>>n;

    build(1,1,l);
9 f& J* ^9 E" q- ?. X$ R    char c;
, V! T/ a; A& B1 v    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
! O! ]# y) [0 @$ B: U% S            modify(1,x,y);
$ @3 ?/ ]; Z' }5 X" R  k! @5 F        } else {
- b) X3 E9 h) ~. N# c( s. ^            if(y-x+1< 8) {
2 N5 y' s( f6 k) M# {& Y                printf("0\n");
: o: |6 a# g4 W                continue;
2 b6 U  [# n' {1 l            }
            vector<int> ans = query(1,x,y);
1 }/ `* @& P% @' v- T6 ~            printf("%d\n",ans[7]);
: ?$ l% @+ Z( h, i% A( N: C        }
    }
* ]. }) D7 ?: t( R5 m
6 |  @+ R7 I8 _& Z. R    return 0;
5 M. V' b% P" C9 w& u( R}

( j7 P; n4 t. Q6 M! `---------------------
) d( I+ p8 w9 T1 A+ P作者：nka_kun
来源：CSDN

- d+ n$ n! ?6 d% R7 X! k

& q% O- j: e& h3 P& I