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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
8 M6 }& L: w  K; X1 C& @: h
  C% Z( B$ K) G8 @# x3 }

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

代码:

: J. F; R7 Z. Y- _' x2 A. o/ c#include<bits/stdc++.h>
' p& b% d. G; |+ ]8 x, ^1 s1 Y#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
+ p0 o. D, c# s- L- C) v% uconst int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
( X2 }( I- C3 i. j1 Z
( `' L+ d; l8 T( Qstruct tree {
" F/ D5 {: r! Y    int l,r;
    int p[10];
# ?; ^" q; k5 z} t[maxn<<2];

int l,n;

void build(int i,int l,int r) {
9 o* V/ k) w$ Y    t.l = l;
    t.r = r;
% ]0 j+ b& H4 @: {. k( q( A    mem(t.p,0);
% T- w6 N0 J. ~$ W
9 H/ {# _- Q+ }    if(l == r) return ;
5 _) F2 n# f0 h7 I  X1 c    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
}
* b1 x8 l  K( y; G* W( K7 p: |' N
! A6 P/ g8 `6 t4 U5 {. kvoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
# u& r: O2 D! T% m    for(int j = 0;j< 8;j++) {
3 A- J- r" |+ F5 I) N        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
& e' W( Z/ _, Q" w* _        } else {
0 g& u& V6 z* c- m, c            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
* L( N4 ^; k# W8 b; y        }
    }
    return ;
}
$ P/ Z% [3 ?8 G
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;
        return ;
& e7 J9 e  P. m7 j0 i. ?" q    }
    modify(i<<1,pos,val);
1 H4 Y  u/ D. F4 j  @% z0 x    modify(i<<1|1,pos,val);
    update(i);
    return ;
' |" [' E9 H' P}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
8 r9 M# w) G: s    vector<int> ans;
8 x/ h) _5 T* q    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
. V8 B9 L8 q7 e3 i& S" v        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
0 j# J( s/ X8 D% [        }
" N$ j: m5 y+ C2 A7 c# |    }
    return ans;
}
/ r" ]' p( _5 _$ P2 h
5 y# }; m. A, ?  t9 I+ n  Hvector<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);
" q& w3 A( [/ F4 {        return ans;
4 A4 r' u! x9 Z) L; e$ @    }

& N* y9 t7 b1 l    if(t.l>= l&&t.r<= r) {
0 V% c" \8 n5 ~" E4 Q: Y9 \8 B        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
2 \% A3 l( r* h) G  H        return ans;
. T0 f* U" G/ @# A    }
- d' T* f2 A, M! w& ~
. s6 t+ I" u: B6 |9 s! i    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
* M: h, V. N1 R9 Q" ^, n}
4 G1 u' o3 [1 w) a  n5 @
8 l4 f9 }5 L8 u3 V. J4 Xint main() {
    cin>>l>>n;

    build(1,1,l);
    char c;
    int x,y;
    while(n--) {
  f" J0 D% G' R4 E- X        scanf(" %c %d %d",&c,&x,&y);
, }. i3 [( e5 |; U' t5 M        if(c == 'C') {
            modify(1,x,y);
        } else {
            if(y-x+1< 8) {
                printf("0\n");
                continue;
  a2 y" x+ `6 l$ K  e: u            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
    }

    return 0;
}
) I7 ]; d. z$ m5 h; u
---------------------
5 A7 M3 o. e. E作者：nka_kun
来源：CSDN
! h; P8 n! ?7 x/ }- U7 |

- z8 {7 m, v' Z3 a' n5 G& g! P
5 f# C$ h3 [9 z