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

杨利霞

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

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

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

代码:

#include<bits/stdc++.h>
: `6 J6 s$ n/ {0 y# k- B2 @4 A#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
& e6 ~5 m# `2 Lconst int maxn = 1e5+55555;
# i, B: N. E5 S) i( l+ Jconst ll mod = 998244353;
" z/ i# k& _1 b; Nconst double eps = 1e-7;
: b1 g4 W6 G3 ~: f! f3 [
struct tree {
    int l,r;
* a( w5 r( Y- p# D6 e6 g    int p[10];
; Q9 Z. x  N7 z5 H" V6 M  k2 e. I} t[maxn<<2];

int l,n;
0 g. E1 T$ ]" ?5 x& P- y  l
. h0 N3 Z( N" \$ @void build(int i,int l,int r) {
0 y& ]  O+ I; \& }/ U    t.l = l;
0 S( g( F2 N2 z& F    t.r = r;
, D" W# @3 J6 Y. x8 `8 [, {    mem(t.p,0);
  x, _+ P  j7 D6 W4 b) p
+ T$ \3 q; K! O2 e5 A5 s  x    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
3 g9 `) @( M" Y7 x# b% o+ G7 z7 v    build(i<<1|1,mid+1,r);
    return ;
}

7 i1 F6 N) U% q( X3 ovoid update(int i) {
3 f2 j& @" H  W0 u; t  @    int cnt1 = 0,cnt2 = 0;
6 l1 ]! q9 X$ K6 B9 \4 Y    for(int j = 0;j< 8;j++) {
+ m. L! r$ f. L/ B        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
        } else {
' Q* c+ x; v8 Y            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
2 ~3 Q9 P9 F) ], G, \    }
    return ;
5 d3 P7 S0 L* F3 O4 x2 }% p9 C}
' _6 b/ M5 q+ Y1 N
7 q- F4 @7 i  `2 j  H( Tvoid modify(int i,int pos,int val) {
8 A% F5 ~. S. \* ?    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
2 b8 o, s) b, y2 r& t8 A        t.p[0] = val;
        return ;
    }
% V; X( O4 k( S  v1 J0 G    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
3 s+ Y6 j$ j9 d; z& p9 Z    update(i);
6 t  F& `: [* b    return ;
2 X# a1 Y$ Q% Q1 c% N$ R3 u9 _}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
0 h/ I. }2 O/ P8 H+ ?# I        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
; I6 }2 b" M$ i* I, T+ U        } else {
            ans.push_back(ans2[cnt2]);
/ N8 `  |5 F! l/ t, u            cnt2++;
, M8 V8 i9 E' v; _9 ~; ~% N        }
    }
    return ans;
}
' k: {' D  ~# s" C% Y
4 N5 Z% C* z; V* a1 wvector<int> query(int i,int l,int r) {
0 \3 M; f. L- k- x. i: P    vector<int> ans;
0 E& m6 N% d# i# i  f5 A/ v6 O1 k) p" h    if(t.l> r||t.r< l) {
5 o+ P+ X- S( W# q; ]        for(int j = 0;j< 8;j++) ans.push_back(0);
& d( B: V. I+ |+ J. S  b2 L0 e; D5 L0 n5 ^        return ans;
: z3 n2 y7 V$ g6 O* B1 Y+ `' [    }
& d+ t, X7 D6 w. h1 @4 R
$ b' r3 G- w3 z5 h    if(t.l>= l&&t.r<= r) {
$ j  C' M1 M4 d% F' t. t+ J6 h" c        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
. C, I5 n3 }& T. D+ _& o        return ans;
    }
" q) W% h3 A* @. K; k9 `/ r. @+ q
    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
3 [# N- X) X* @/ K9 ?8 w( Y}
$ g& G; E/ a5 H7 F7 l
( t+ w& @0 a3 ]1 [" _! sint main() {
    cin>>l>>n;

' f& k$ t9 o- U" Q+ j5 j) F    build(1,1,l);
$ |, O# f6 R) D    char c;
    int x,y;
: \, \3 k% X7 [* z4 b/ j  g! [    while(n--) {
( i: A7 _3 A* u; }+ l+ |        scanf(" %c %d %d",&c,&x,&y);
. t2 B2 Y8 l; P* Q1 l7 g5 i2 V; g        if(c == 'C') {
            modify(1,x,y);
- m; u2 i7 n  Y; M8 q8 A( A        } else {
- e5 z" d# W0 f* S            if(y-x+1< 8) {
$ e, _8 @+ _+ h1 x* b4 ~2 R                printf("0\n");
2 c- ]) T9 a& a) L                continue;
. N& E- ?) f+ o* h; y- P            }
5 W/ u! h# ]3 W0 ^            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
0 M. s2 e, z' M        }
    }
& P2 z6 b( O7 E0 H$ k/ X/ u# [3 ^
0 @1 n4 ~* |# S    return 0;
6 n+ g0 E/ L/ n$ e) A6 p4 f* N. ]}

+ Z4 Z3 Z/ K8 @* Q* `! o2 O---------------------
" T6 f! [, J# p% J作者：nka_kun
3 u7 }6 E! e( k' V& g% G来源：CSDN

4 w0 ]6 O6 w# ~1 }3 @) A& W0 r- {
! R- ~/ t. I2 o+ o2 W/ C
6 `3 i1 r" I/ b% X" {