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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
; a! {7 Q; q! l7 g4 Q+ e
+ l. R5 Q5 O$ w& }: H* Q

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
. m& z( H% w3 i$ e  ]每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
) v% @. |( S' K& S6 J- u查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
$ b3 v+ m/ ?' W0 ]; Pconst int maxn = 1e5+55555;
( J# `0 X6 U0 m0 I# e- Aconst ll mod = 998244353;
, W8 p5 S" ?% M2 U1 V9 bconst double eps = 1e-7;

6 H1 H4 p7 p0 w& \" \& D& T: p  N" ~struct tree {
  q) F4 @& r# O    int l,r;
    int p[10];
} t[maxn<<2];
/ w$ W6 ^4 U  ^4 @
int l,n;

3 n# J( G7 ?2 ^1 z" Pvoid build(int i,int l,int r) {
    t.l = l;
5 h, b, V' h" z) Q    t.r = r;
* k5 h% k$ j9 v+ o: b1 I2 n    mem(t.p,0);

! z; i1 T# O* l# u$ \    if(l == r) return ;
    int mid = (l+r)>>1;
( x8 B5 y! k/ a4 l    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
2 S% V1 q% m4 a) `3 M    return ;
}
2 W. o* R% n6 y$ ^3 ?4 C
void 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]) {
# S. f' ^1 F, s& _: r5 F+ r& @. b            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
        } else {
; O9 u" L* z  P& C            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
) G. X, W. T4 q    return ;
}

( ^+ @, U2 G  S# Jvoid modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
) W  L/ c  P& \) d        t.p[0] = val;
4 H$ k9 C- y2 Q, L. ^( A        return ;
    }
8 i0 f( I- H: g/ y( o% U  _7 u, M    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
+ `# Y7 }( b3 L2 g& n! ?% p$ O    update(i);
0 d4 W6 n: b( ]8 x) t    return ;
}

4 a# K* F8 u# h0 ~. Svector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
1 |6 d7 B2 f- n2 V' r3 p$ L    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
1 m0 o0 s; E1 H- ~0 z        if(ans1[cnt1]> ans2[cnt2]) {
* h  B  _% _5 p+ s$ g5 N            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
; `3 x6 o7 g$ [( m            ans.push_back(ans2[cnt2]);
% S; y$ }: {1 G4 v            cnt2++;
- `; C4 b1 D+ d        }
    }
    return ans;
3 W+ v2 r6 d3 b+ @4 P}
# `; l4 S& f! j- g; [- q: b# ~
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);
) F; @9 |0 s, U% I+ D% ?0 ?, `& D        return ans;
9 u0 z: Q' c4 A4 L9 t% g6 @    }

" Z. p' H5 d6 p- v! N# d    if(t.l>= l&&t.r<= r) {
$ k% T) G0 }0 l; J4 z- F5 U        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
: }; h0 V3 u' L& b! P" T}
+ i+ w/ y' Y4 D+ ~8 e& x
  G: B+ `9 S. d& ?, X* H& A" i$ dint main() {
$ k# f" {9 w# f/ y  b# M6 `, j$ ^    cin>>l>>n;

- e# V) z( n- }- x6 M3 h6 m    build(1,1,l);
0 b* z& R, C- l' g( U# @( j    char c;
    int x,y;
8 p/ `$ Z, {+ `6 S    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
* w' @9 n1 V' V        if(c == 'C') {
            modify(1,x,y);
. v. A; K) W3 {- H  M+ U0 A2 N9 V        } else {
8 `/ w- X. C# C            if(y-x+1< 8) {
                printf("0\n");
                continue;
( w2 J9 d& v$ V+ w. \            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
8 d2 m+ n# j% X3 `/ `' I        }
; [6 ?6 N+ m. K4 C8 @    }

    return 0;
' y2 z8 f: H, q- X}
$ h5 Y1 l6 o' y8 i/ ]0 B
---------------------
/ y1 ]* m  }) j9 [( D作者：nka_kun
来源：CSDN

/ v8 D9 B" d% P5 W

: c1 `: m5 h6 f; l" v