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

杨利霞

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

5 k. R3 {5 U( C, R2 M* g- ~

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

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

代码:

. ~7 ]' t1 n+ y5 [  K#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
0 n+ S& n' i& w0 y; gusing namespace std;
! O" R- K+ u  _" A" M  Vtypedef long long ll;
8 D# W8 ]; i7 A. ~, Z4 r- ^. cconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
; g% \3 q! {+ n! O* i6 Iconst ll mod = 998244353;
const double eps = 1e-7;
, j1 _/ z3 f3 U& {$ ^0 }
( _4 s6 T0 X. x- `8 ?2 f( estruct tree {
    int l,r;
    int p[10];
# _! O6 S* a1 h} t[maxn<<2];

) O3 X- b  ^5 [" l) Y! hint l,n;

. V( p4 o. w) Q- a- Y/ \0 F* Yvoid build(int i,int l,int r) {
$ ?& |& d7 Y$ h! P1 K    t.l = l;
    t.r = r;
    mem(t.p,0);
7 G, J, a; X) d9 j3 I
4 x/ D" u( B0 n% C; Q    if(l == r) return ;
, b3 {& |$ e# o( f. u9 K. _    int mid = (l+r)>>1;
' `. ^1 [( Y) T" U9 r    build(i<<1,l,mid);
; M; Z7 K; [1 Q7 @    build(i<<1|1,mid+1,r);
    return ;
7 w; c/ q9 t1 B}
4 |6 o8 h& b  G; ]  \) \, V
. C% y1 d1 F( e8 ^; \! r/ qvoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
    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++;
: G: q( A& q4 M* k        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
" i% N3 ^9 B2 F  Q            cnt2++;
        }
, l3 ?; S- \1 }) g2 t    }
    return ;
}
  u9 H# u5 x, K1 A- H% ~' N
void modify(int i,int pos,int val) {
( Z% [& l+ E* P0 W" g    if(t.l> pos || t.r< pos) return ;
- T# n* X2 h" ?7 L! n: c    if(t.l == t.r) {
        t.p[0] = val;
        return ;
+ {2 ?1 W. ?4 [: d5 n5 `    }
: r% J! ^) F. H    modify(i<<1,pos,val);
( v" _$ @8 @8 r. P2 h/ D. b, Z: u    modify(i<<1|1,pos,val);
    update(i);
4 w4 R$ R8 V; F# h7 N    return ;
8 V" }) z/ \! r}

$ C5 n. y, d- Q# Z* Q9 ivector<int> merge(vector<int> ans1,vector<int> ans2) {
+ ^; t: J& I- \    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
& k- y$ X4 O$ N. X' B# x6 ^1 q    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
  {- H: K# Q0 r" b% x            cnt1++;
        } else {
& t  L  N# s2 \* y3 {            ans.push_back(ans2[cnt2]);
5 m; \/ k3 `# {" @' [. B# [            cnt2++;
1 I: b& p! n9 I2 C# Z& ?        }
    }
    return ans;
}
. [- o: T# s. x, }' ?: e* Z1 d& `
5 r% _2 f) O7 d' `vector<int> query(int i,int l,int r) {
    vector<int> ans;
- m& y) ~" Y' g" e- D% \' A" i$ a- Q' i    if(t.l> r||t.r< l) {
- V" V. z3 X4 g! f! G  g        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }

    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
    }
& a/ V- H! ?+ m+ t: k0 v- J! f
    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
* ^/ T4 W# ^# ~8 i5 C; R}
5 `6 [0 {2 c$ C
0 z2 o6 c$ Q/ N, oint main() {
6 Z) Y* v, V5 Z; K6 `    cin>>l>>n;

    build(1,1,l);
5 H* L5 ~' j7 ^4 a( r/ q: c# M    char c;
    int x,y;
2 w7 j9 S8 l) A5 I$ _9 ?" R  A    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
1 U" e1 _" e$ a- @            modify(1,x,y);
# q" t4 K+ D7 q, n( O        } else {
* y4 ^' w- v' H8 `            if(y-x+1< 8) {
                printf("0\n");
8 p- ~  E. F; A1 x                continue;
- Y1 p: ]+ e0 u' D! W            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
4 B0 J; g0 ]# Q        }
    }
/ U  X+ T& [% m; g( O+ ^
    return 0;
( O/ u* d8 ]+ a/ P) |; z( P}
3 Q1 K3 b8 Z5 W: P3 ^
---------------------
作者：nka_kun
来源：CSDN
( {% D8 Y5 m1 J; M
7 [& v) X0 k5 p) |$ z' L" L3 L
1 C( s& I4 D! \- m) V8 U