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

杨利霞

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

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
5 _: Y4 h% h$ a3 c' r. o+ y每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
9 m( l4 o9 o" _' h& _查询的时候返回含有8个值得list，并不断merge

代码:

5 w" I- \- d& O5 W9 F" E' s#include<bits/stdc++.h>
$ ^7 A& ~2 H) a. |7 O1 I#define mem(a,b) memset(a,b,sizeof(a))
7 @9 q+ X, G8 v; Q) [/ J2 v1 ^$ Cusing namespace std;
0 f& c: H" B% ^6 P' t4 I1 `* Ttypedef long long ll;
const int inf = 0x3f3f3f3f;
* u" N2 _. m/ F" D' ?0 Y5 _const int maxn = 1e5+55555;
: f3 a: K! S) j: u' o1 aconst ll mod = 998244353;
, b9 R4 u) }( F: s7 G' G3 Dconst double eps = 1e-7;

& ]: y4 ~1 _+ `  T- K) ^struct tree {
    int l,r;
    int p[10];
# O! ]7 Y/ D0 z7 f0 ?} t[maxn<<2];

  R# `/ `3 n9 v5 N( N( q  [int l,n;

# O' s: A7 R. [9 I/ T+ F" C1 P8 Mvoid build(int i,int l,int r) {
/ K( m, u7 P3 N; V2 w! ]    t.l = l;
. E5 A( a6 l6 d, G" Q    t.r = r;
: {8 W; w1 v7 a1 C    mem(t.p,0);

    if(l == r) return ;
4 n. S$ y, m9 k, i    int mid = (l+r)>>1;
    build(i<<1,l,mid);
) r, ?9 x0 \2 n    build(i<<1|1,mid+1,r);
    return ;
, w7 i  ^4 V; f6 {1 ]* Z}

void update(int i) {
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
# E5 k* L1 u2 `7 i* p        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
/ G, o3 x; b, t* ~6 W            t.p[j] = t[i<<1].p[cnt1];
& E, @7 E; O: u; \. V7 X; C            cnt1++;
8 h: b, C7 W/ m- L        } else {
) x& K2 g( O) v3 V; @& `0 \5 j            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
' l+ M! R' r  V5 h    }
6 @0 R8 i: Y2 C) e$ f$ N, w8 n    return ;
8 L- [1 H& ^( |+ o$ d" U}
8 c6 H+ r) J6 A3 V2 B3 V
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
# O# Y: v6 i+ n# B    if(t.l == t.r) {
        t.p[0] = val;
3 o% _2 ]: a- ]3 X& O) ?        return ;
    }
    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
2 l; _1 P/ E! S1 v6 j    return ;
}
4 @  E4 K9 ]2 z1 P$ t
6 B# e& W1 _/ H% j9 V. g5 lvector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
* u: }$ T; F* X% A7 s) k            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
. l: U2 d  d" L5 Y2 G% R! Y% y# u            ans.push_back(ans2[cnt2]);
            cnt2++;
( i: o- f+ R  K; e0 K0 H        }
% R6 C  A* ~% _) u# H- q' E" [    }
    return ans;
1 F: I) J) M- }: q* {7 l}
' a2 l1 J! K9 v; l8 I1 b
vector<int> query(int i,int l,int r) {
    vector<int> ans;
7 f* E, R$ D" e, Q0 ^    if(t.l> r||t.r< l) {
  H* e$ M; y( o3 w. F        for(int j = 0;j< 8;j++) ans.push_back(0);
$ t) t+ E( [) P: L$ S, |        return ans;
    }

: z/ I4 j2 v- L) E    if(t.l>= l&&t.r<= r) {
+ U2 ?1 n( W; m) G        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
" _) ?; j( z6 {5 a$ N    }

. f4 F& I9 `3 O1 r5 E1 Y    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
8 k3 i/ c( [- e* b2 U- h: c2 b7 ~, E}

0 V8 [' G/ ]+ F2 p+ c. Lint main() {
    cin>>l>>n;
0 q, p3 f, d& h' a
) _% x2 o& M' X4 E3 D& V    build(1,1,l);
1 F4 ~/ b, h: I( [& @- n9 v    char c;
8 X  ^0 B9 j$ R0 j. Z    int x,y;
+ B) C1 Q5 Q6 F* Z  ^" X    while(n--) {
# t' l/ u( O" b        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
6 X3 @% Q  b( ]' x- P, u2 q6 U            modify(1,x,y);
+ L" ]' n5 n" Y' }6 K- }        } else {
; ?# z* d+ I& B  l            if(y-x+1< 8) {
                printf("0\n");
                continue;
7 U. [) Z7 f/ e; D. ~# h            }
. {- }0 ~6 `) e# l- j7 ]8 l+ W            vector<int> ans = query(1,x,y);
$ S, e3 Y  J/ D$ ?! v            printf("%d\n",ans[7]);
        }
    }

" H% `9 O5 U. j; e$ N    return 0;
6 I4 s$ ?6 A9 o3 x% R}
2 I) _) ~4 n( \4 n" |# M/ v
---------------------
作者：nka_kun
来源：CSDN

# ?" e% g! h: L- f1 A, C2 l) x# C' B$ d

7 E+ c3 P) F/ E" v