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

杨利霞

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

- n2 }3 g; t5 J, p

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
0 J* d1 Q2 y4 z+ t7 e8 ]+ z每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
8 ?% R" ~3 }2 O4 f$ B查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
; i- c! \5 f6 W- @4 u4 d#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
3 w& {: Y+ p/ w7 s4 g) a# P$ Ztypedef long long ll;
4 _( a* q6 M  @# f7 Zconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
6 h# N3 L8 _" c# M/ yconst ll mod = 998244353;
( e8 P: K+ I- u8 v! B+ E7 Dconst double eps = 1e-7;

struct tree {
! Z$ O" h6 |" m+ m, O6 {3 v    int l,r;
' \8 J& v) j1 Z  |    int p[10];
: Y! N  D1 e, M+ C} t[maxn<<2];

' G: j, o% Z/ G6 d0 b2 ^int l,n;

void build(int i,int l,int r) {
    t.l = l;
2 T& f5 ^# f7 a% |. \) W! [7 ~0 `    t.r = r;
    mem(t.p,0);

3 ^5 e4 E% _4 X0 e3 u7 y    if(l == r) return ;
    int mid = (l+r)>>1;
3 B2 p, J/ {, a) z# D3 o    build(i<<1,l,mid);
. H7 v; O. W2 B* C& v& m    build(i<<1|1,mid+1,r);
: v6 ]9 r5 ?7 o    return ;
$ g) d. a! Q" W4 }/ t}
4 \, W8 x) i! ?3 {0 \9 P# B2 Z
void update(int i) {
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
& a& `  C+ \6 V4 X5 @        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
% a6 q9 G% k" p- b0 _& H; ]4 L            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
* U! b; z! z7 V        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
$ C$ i# p* n" C0 B# E' p# O) c$ R    }
    return ;
}
7 z1 E; B0 m1 g
void modify(int i,int pos,int val) {
# ?/ h+ ?- e8 P! C" n8 f: a    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
  z; e0 ~# z' ^( l" l  w) U        t.p[0] = val;
* Y$ l, h. M& [9 F1 E; n9 |        return ;
& S/ m/ G2 f/ j0 R& t    }
: x* p6 t: B. E    modify(i<<1,pos,val);
$ @& B' f, P% p; z1 q& C: b5 P) l    modify(i<<1|1,pos,val);
    update(i);
5 u8 o4 v* u# _+ [    return ;
8 v: v& @& n( R, A}
8 b6 [; x% t" b4 H/ a4 E! ]
7 z) M( u/ R' g( ~/ c. J6 Wvector<int> merge(vector<int> ans1,vector<int> ans2) {
1 f% U! `) C, d' s% H& P    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
" A2 N9 \0 q- y) B% K# u# {! a' x* R        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
( Q6 l- c- h! `8 H        } else {
            ans.push_back(ans2[cnt2]);
# V4 H8 d  d! o+ K- F            cnt2++;
        }
" w/ k( |8 x' V( Q8 Z9 u3 k9 L    }
1 n0 c6 I5 q/ O0 {    return ans;
}
1 F) g' s5 c6 m" C  T" v& Z" R: q
vector<int> query(int i,int l,int r) {
    vector<int> ans;
" i* b3 N! Q7 o: Z    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
  X; f9 w& v) @! |0 c1 i        return ans;
    }
% _/ u( W$ P% k- q" `" _  u
    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
0 h1 _/ ]+ L) k, v4 b* r        return ans;
1 A& ]& Q( L. O) d    }

1 g) V+ ^/ w. F4 f4 d; z! k    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
) r( L, `& @, C# \- h
) b* a. e) W9 v0 s' P. \5 Mint main() {
    cin>>l>>n;

  @, j7 g2 i9 K4 x  U- j    build(1,1,l);
    char c;
, B; w2 ^1 y1 f+ q1 g" d: L    int x,y;
' o8 Q( Z2 {" g! ~$ I7 P    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
3 @7 x2 \  k1 v% P6 }            modify(1,x,y);
        } else {
            if(y-x+1< 8) {
                printf("0\n");
$ Z8 i. r6 l6 l) s0 q" c                continue;
/ u; m! g" |7 r: e9 n' l( d& K7 W            }
& W7 i# Y* a# X5 D1 J! F! ~            vector<int> ans = query(1,x,y);
. a. \  p/ b) b+ K3 T% `7 F) p            printf("%d\n",ans[7]);
        }
    }
% l; K. P: u5 L4 ^& B9 }9 G
    return 0;
}

3 `- x& Y$ _( v, [, b5 ]---------------------
& p5 k$ M! L0 S9 n作者：nka_kun
$ v: @# i, {6 ]  p* X来源：CSDN
: {9 o# p5 I8 w

3 d7 j/ @) g9 q  B2 y
7 |6 ~' V2 {0 \3 I2 M+ D6 I$ z