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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
& g; a/ F5 x9 X( F

题意: 两种操作，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

代码:

0 v/ v6 g# |/ W#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
3 d% T+ y1 b1 {1 X, K+ x& Pusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
: I% u' D9 W4 X8 j6 ^const int maxn = 1e5+55555;
8 T4 X, j6 i  j3 I3 W! F# ]const ll mod = 998244353;
const double eps = 1e-7;
; p+ x  _0 s0 A
struct tree {
/ b' u: W( H) Q9 n% F) _    int l,r;
    int p[10];
} t[maxn<<2];

. Y' o/ F$ H4 Tint l,n;
% E2 Y; J4 a) Q0 N1 Y* y
void build(int i,int l,int r) {
    t.l = l;
    t.r = r;
. O2 v3 x' f/ u    mem(t.p,0);
9 r$ i, L, P7 Q  O, \
    if(l == r) return ;
    int mid = (l+r)>>1;
. B( E& ?, D( e5 b8 {! D- O) K8 ~& J    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
+ v4 m! x6 K5 T" a7 Y) ?    return ;
. M3 k2 u# r' e% a}
/ V5 O: f% O; z6 ~% u, Q! \
void update(int i) {
    int cnt1 = 0,cnt2 = 0;
! M) K  b2 V( X& l    for(int j = 0;j< 8;j++) {
& k0 V; U9 a0 H! W        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
0 [& I$ @. f8 H  P0 ?            t.p[j] = t[i<<1].p[cnt1];
! A4 n, H* `) o9 J, [6 d5 \' }            cnt1++;
        } else {
0 \) K- Z( H0 D% g0 Z            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
! x" |; X8 j# t- M    }
8 i) S+ _5 C7 h- K; O    return ;
: h( l, v0 R# X. y8 B( D- A}
7 z) g" j; a% V& @) K$ u1 k$ j! l+ l
" Q& I  p  g) G& U$ qvoid modify(int i,int pos,int val) {
2 S( E1 C& G, g: [    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
  A) r' i6 ]' c        t.p[0] = val;
        return ;
, ]$ ]4 h/ v  F3 {8 Y4 r8 C    }
    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
    return ;
- Z9 [( [+ N9 d5 i( N, y4 z' B+ f}
- v* u' L% O/ Q; k  V
/ [0 q8 {" B# X5 Pvector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
' K; c6 x+ e; z7 H! N$ I& Z    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
- ~$ {0 J1 l6 h+ Q' i% k        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
: t2 A+ t( x7 P) u, Y8 D        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
    }
1 `& G& ^, a0 l& h3 `2 x    return ans;
. O+ q. A7 ~  W. s3 N& I9 }* A0 ]}

vector<int> query(int i,int l,int r) {
' c( S2 y8 h; e  f! ?& `- W    vector<int> ans;
    if(t.l> r||t.r< l) {
/ ^" \' {# r4 _9 s7 i6 m        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
+ F1 d  V/ `* Q9 x' @    }

    if(t.l>= l&&t.r<= r) {
" R' f- e) z7 i8 V        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
& \( q# s; r: K$ D  ~) m, T5 J$ G1 J7 `        return ans;
3 [; D% b" N& e+ D3 d/ @9 l    }
, S: p  t1 _- j' J, C- X9 B
" x$ s  z. W" ?* n6 U7 m3 p, ~    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}

9 i* V9 c. K2 s- cint main() {
    cin>>l>>n;

    build(1,1,l);
9 u: E* N$ b* S' O* [& w! }1 c3 G+ H% j    char c;
    int x,y;
( W% o" g* `, ~    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
; L/ w: D3 b8 q            modify(1,x,y);
        } else {
            if(y-x+1< 8) {
. s' o, i* l( i                printf("0\n");
5 a) g$ R* C& x+ J                continue;
            }
. y1 v& @) H; ~7 n) b1 K: M            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
1 d1 `* K" j0 [) {        }
. m2 C6 I1 }. n- p    }

2 R! e5 n  ]1 `( A. k" ~* V) g    return 0;
}

---------------------
* ?( \' |: |& c; N9 o( `* t1 G作者：nka_kun
& N3 T+ v1 }# ?8 D* H  Y. b. D来源：CSDN
3 F7 @1 f- A! W% _5 ?( e
6 o- Q/ ?1 ]* q8 U

4 v/ m5 Q5 z. ^5 }  \0 F- V