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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
. k) c) \. W& H# P! P, u6 e
& c! ^; H8 C# J: m8 t$ W7 E0 p/ l

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
( f/ X0 J4 r$ K& e# E+ t$ R查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
9 g7 F& \* U/ |6 h#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
* o+ m: @8 a% c- E: t/ Y7 C; ~. ytypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
) }0 x3 l( ~# l6 Dconst double eps = 1e-7;
+ C- q9 Q. m3 H+ H$ M
( r( g- }% w9 z: [2 |, T0 estruct tree {
    int l,r;
2 J( r" j! u0 x# m; D9 @  J    int p[10];
3 _% L0 G9 p) N. d- Z* I# I} t[maxn<<2];

! n% N, O* [. U6 h) Eint l,n;

( K9 v8 }7 z" V% O+ K3 K: rvoid build(int i,int l,int r) {
; E( u! i5 M$ q    t.l = l;
    t.r = r;
    mem(t.p,0);

    if(l == r) return ;
+ Z( S8 e3 F) t+ b% J    int mid = (l+r)>>1;
: L+ a& M- R' u* h; f% K) i    build(i<<1,l,mid);
1 O! o. j2 h2 {/ ~2 D: W    build(i<<1|1,mid+1,r);
    return ;
}

( P, ]  o6 ~/ K! Xvoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
' z" ]$ C0 k2 P5 P7 H    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
: ~7 Q0 g& a* k9 A4 U! c- |            t.p[j] = t[i<<1].p[cnt1];
/ V. ~$ R2 U! D            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
) v' w3 y3 a* N# O! n. T6 ~    }
8 A/ v0 B/ n* {    return ;
}

/ D  F! r) f7 ^8 d) @void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
6 e4 p4 X8 n& o, F9 ~% h4 z/ v! O% y    if(t.l == t.r) {
5 g1 \+ Q6 K. N! B        t.p[0] = val;
+ \6 k% Q/ S+ j0 ?) K  {  P        return ;
    }
6 x$ V3 |  s" g/ ]* a$ W7 b: z    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
    return ;
}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
- V0 M1 Z6 V" e& G& G. J    for(int j = 0;j< 8;j++) {
5 l7 U9 }. {* m! X        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
4 R1 T) _4 _* [  t- w            ans.push_back(ans2[cnt2]);
0 j8 X3 a: S8 J# V2 o# J: c2 J- P$ ~            cnt2++;
        }
4 |1 y9 r- n7 w4 N8 s: i( i    }
* S6 t$ i1 D  g8 D    return ans;
' f) L) ]. e  G* f}

vector<int> query(int i,int l,int r) {
    vector<int> ans;
8 E; F) P+ A, t) `' e7 A    if(t.l> r||t.r< l) {
6 i0 l3 n( b: m" j        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }

    if(t.l>= l&&t.r<= r) {
3 a& J; `- i4 W) {5 \8 s        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
- V5 ?, a* `- y" b3 K( d    }
( y- q3 h% o/ h, c* i8 }1 T
1 `6 m$ u1 p; N& V& K' L2 ^  Q    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
( M4 z, ^( ?  W5 f! N
int main() {
    cin>>l>>n;

    build(1,1,l);
# O9 k! w' R8 c! b' {; ~6 l    char c;
    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
            modify(1,x,y);
        } else {
! i+ Z" _( ]8 |  z5 B# h            if(y-x+1< 8) {
                printf("0\n");
( |3 s1 k8 p& I8 b                continue;
9 V  q6 t- `$ S0 M            }
3 j, ~2 z8 {) t5 v( K, A4 K* J            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
% j! n2 w) C4 B6 L        }
, l/ ~* R3 v, @+ Q3 b6 L% m    }

: M7 h2 L, a3 N  d, A  o9 P" B    return 0;
}
" m! [7 n# v) ~# A) u
---------------------
作者：nka_kun
( M, d3 X" D8 z9 z- E; u来源：CSDN
, L! l8 Y- B( z% ~: H  d

7 E6 Q3 y' z: x: M7 A7 T9 ~9 N! O1 P
% ~2 u* @0 E' a4 N3 U0 N& Y; [. G