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

杨利霞

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

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
0 S, N3 G6 I0 b: l/ ~每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
  t/ D2 Z3 g" d: i, ^3 E/ `& l0 G查询的时候返回含有8个值得list，并不断merge

代码:

* F7 |0 k7 l7 B& _#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
& j3 Q5 v2 }% W7 L* Y- lusing namespace std;
typedef long long ll;
- T3 m6 v# {$ S% uconst int inf = 0x3f3f3f3f;
) q0 A- b9 r7 x$ w' a- L" p' C( ^+ k: wconst int maxn = 1e5+55555;
9 X+ Y% H  Y" V% R+ \const ll mod = 998244353;
8 H' R0 O7 n4 G0 Sconst double eps = 1e-7;
3 w8 R" D" U4 U# b8 G7 l- b
struct tree {
    int l,r;
6 H5 c. h; Z, J  r7 [    int p[10];
% R0 v! N7 S8 j. j) @6 |} t[maxn<<2];

int l,n;

void build(int i,int l,int r) {
- l' D2 S$ l0 q& s& v2 f+ k* d5 k; l    t.l = l;
# O6 z' u7 h5 b- c  l/ R    t.r = r;
' }; h$ M, I8 n2 f7 B+ _' e    mem(t.p,0);
) d6 R3 B8 m4 E; a5 m! U
0 G: v. I/ B8 r, S( }    if(l == r) return ;
- f7 S! z" _# U  X4 J    int mid = (l+r)>>1;
    build(i<<1,l,mid);
! V$ F6 A* C. |3 G& }    build(i<<1|1,mid+1,r);
# w! w1 L; d1 q    return ;
3 J" `6 p( M- e+ C: i# ~}

- V7 h( F# i* b- \/ Evoid update(int i) {
% L5 y# m# D. F+ n    int cnt1 = 0,cnt2 = 0;
4 Y$ R+ r. S5 P    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
5 r# r2 k- i/ W" V# d: m! W4 Z            cnt2++;
        }
    }
& K( y' G* v! b+ X, ~, m+ Z9 d  s    return ;
1 O- d5 H4 v; W( m}
" t) |% K( J  o+ D
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
        t.p[0] = val;
1 V) U1 u3 F7 H4 i! Q! P        return ;
    }
8 x- y7 r& X6 }: z    modify(i<<1,pos,val);
( F. w1 H. ?5 B) a- |. C4 s& @    modify(i<<1|1,pos,val);
    update(i);
    return ;
; }2 e5 l6 p: a& H/ c1 v}
/ A2 t) R, V- A& M8 `5 q, g3 Y
9 u, z2 N: l) o! Ovector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
6 M/ Q' A' C: e' u5 d- f            cnt1++;
" L4 D, j3 l9 G7 ~% y        } else {
4 k: ~7 s+ i( E' s            ans.push_back(ans2[cnt2]);
1 ]- G, c% S* E8 D2 V            cnt2++;
        }
  j: K0 l/ l  e% y; P    }
, `: V! w) o/ s7 g3 b    return ans;
6 o* E3 A$ X) J}

vector<int> query(int i,int l,int r) {
    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
3 {" S( I! w# L3 D3 Y        return ans;
    }
5 b) ~4 ]' H6 |9 v  N& @
    if(t.l>= l&&t.r<= r) {
$ k3 A4 X; g8 Z/ D        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
( J7 b; W# r+ i  Y% l2 E0 Y1 c" u        return ans;
    }

) V8 ^7 y3 b3 P) \2 B  G7 O    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
7 l1 w+ |0 W0 Y% [  w, I7 x
9 ~( g, a0 i; y2 O8 Iint main() {
    cin>>l>>n;
4 i& S4 l7 a) s. C5 m  v  t
    build(1,1,l);
' u1 I$ a4 z" _" ~" w) k    char c;
" U, R2 b- L( C* v- `4 ^: W9 X    int x,y;
3 W0 ?7 ]" K' \1 Y* \    while(n--) {
7 m' }% {) `, U) P3 \" s( v# t        scanf(" %c %d %d",&c,&x,&y);
9 A8 V1 v1 h% t3 R        if(c == 'C') {
6 \0 f$ Z; D5 J" p            modify(1,x,y);
" a7 c: Q: i. ~5 W: N        } else {
            if(y-x+1< 8) {
                printf("0\n");
1 N% P. W3 V  }7 {( a                continue;
            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
2 j; l' y7 h) j        }
    }

    return 0;
}

* n- N5 a3 L0 S---------------------
作者：nka_kun
来源：CSDN

$ t6 Q( [1 q  _4 G1 G0 S
: ?  p, m% x" |" I  f5 e
# w/ M1 d% \6 L; @