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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
" }$ Z( T8 }- y7 H
/ _; N3 e/ q, E/ v7 y4 I

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

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

代码:

0 f. {( h5 t3 t8 W  e6 d7 n- _#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
( \+ L* L# b6 H- u1 I& Tusing namespace std;
0 g( b5 Z6 o% c# n. Atypedef long long ll;
const int inf = 0x3f3f3f3f;
+ E8 t2 [" T( A1 L% x+ U9 Kconst int maxn = 1e5+55555;
! [0 ?# C3 }/ v1 J- O: r; Bconst ll mod = 998244353;
const double eps = 1e-7;

1 X+ q5 y4 l  Dstruct tree {
    int l,r;
* Z9 e6 R: l9 |    int p[10];
} t[maxn<<2];

0 D. m- T' Z4 Y+ r- n6 m9 m/ lint l,n;
8 W7 d& @6 u! Z, `4 G
  g. }& x( U) Wvoid build(int i,int l,int r) {
    t.l = l;
    t.r = r;
2 }4 p5 q4 C3 R: q. N. |    mem(t.p,0);

    if(l == r) return ;
/ S$ ^7 \' F+ M2 |+ Q* j! w  E    int mid = (l+r)>>1;
2 b. `5 S3 b" w0 `- k    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
9 W  q. G! d( v- k}
: s% t0 d# U9 d# B0 B* ]
void update(int i) {
    int cnt1 = 0,cnt2 = 0;
! P, ]. p* L1 s& @) p9 q    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];
& `. p* q0 f3 B4 u9 @& g9 u            cnt1++;
' y2 J+ G  A0 L: e) C) i' C6 M        } else {
5 e' Q; r' a' M, r            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
' F3 x+ l% s8 G    }
    return ;
}
& k7 g( g1 i% o3 D
4 d: Q2 b) v0 avoid modify(int i,int pos,int val) {
+ K# l$ U5 D1 V* A4 k) U    if(t.l> pos || t.r< pos) return ;
8 T; j  ~& E8 s* X$ E    if(t.l == t.r) {
        t.p[0] = val;
& `7 z4 Z# }0 I. M        return ;
    }
    modify(i<<1,pos,val);
2 o9 S: h% _- s9 z9 i" n. v; N    modify(i<<1|1,pos,val);
    update(i);
' E3 ?% b- t3 I2 }    return ;
) }0 g/ Y5 y, F- n5 r}
/ l/ x% C/ k1 j0 A; j# ~
vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
0 E  ^( N7 Q/ L8 E$ t$ J& X    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
. k6 ~2 x  c  s9 V            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
! t2 Q+ l; c1 Q9 R2 m            cnt2++;
        }
) S+ Q+ m; R7 H  {5 Y    }
    return ans;
# Y& a  C& _8 H6 f  k}
8 H6 |8 c; j% }" w8 w
; N; `* }5 e2 C1 Nvector<int> query(int i,int l,int r) {
$ g& j; Q0 [" C' y9 \' @    vector<int> ans;
9 \' u5 p* G& p2 t- a8 L$ e    if(t.l> r||t.r< l) {
3 e: @3 y) Z4 A. N! T        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
% G, Q& S% s( k4 @( E5 ?6 E0 |6 ~    }

    if(t.l>= l&&t.r<= r) {
8 I& _6 n* B3 l  C" q  ]& n. j        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
! I% C# x# N& {$ m: n) e        return ans;
    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
3 \1 ?3 Z" F0 ?3 X}
8 Q& S3 k. y, g- f4 o( @  L
9 R. ~0 l9 \' v/ ]% Hint main() {
9 J2 Q* F, K0 g6 R4 Z0 t  e    cin>>l>>n;
- L! A. d/ r, r* }
/ \! F# R$ J) O# o    build(1,1,l);
5 o- F1 h, L: z! A2 `6 [" o2 R    char c;
7 |5 n+ \( \* \/ Q' }9 x- x  S4 t    int x,y;
: L: f% g) h: d) M8 Y5 {5 `    while(n--) {
! T1 A5 L% Y1 ~. i        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
4 j( y: S$ J& s; ?% m6 l) Y            modify(1,x,y);
+ f/ w& b& v9 X/ a( L        } else {
            if(y-x+1< 8) {
                printf("0\n");
                continue;
            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
* C& M; h# ]$ F3 h" T* d0 d8 {! H    }

    return 0;
* e5 o+ s' k' a}
( S+ B$ O" |+ l; \2 J* D! J
---------------------
* j! S8 h$ ]4 o, r9 W& k/ F作者：nka_kun
1 y. y! V: p6 }) ?来源：CSDN


" C3 F- g; d3 i% ]