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

杨利霞

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

6 V' H( p) G2 T( Z

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
9 O5 @- ?' K+ _4 G# Q0 u  ^# e查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
& R% s' n! j) _5 `1 q#define mem(a,b) memset(a,b,sizeof(a))
' {0 ^- s+ {/ b9 O! s; l- |using namespace std;
typedef long long ll;
1 n0 z4 G1 g$ N% uconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

struct tree {
    int l,r;
    int p[10];
} t[maxn<<2];
/ ~5 o1 @) p/ Y* `5 [0 r# p1 P
int l,n;

5 |# P3 Y( e. t& M2 i  `& [void build(int i,int l,int r) {
* Y; a9 D3 e2 k* z! m8 z: N    t.l = l;
    t.r = r;
    mem(t.p,0);
6 j+ T, q' B, y3 A- W8 o: G
6 @' v5 G. j0 a- [/ G, L    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
* Q5 r' m1 E' u" r7 G6 g    return ;
}

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]) {
6 l) b' N* a' N6 h            t.p[j] = t[i<<1].p[cnt1];
$ m0 B0 W  w$ i7 G. H            cnt1++;
' p. q! {* i* T4 R! C7 N" Y& M  e! \* g        } else {
0 y3 h+ j) Y6 I, B            t.p[j] = t[i<<1|1].p[cnt2];
! ~# L( }; b: f7 x: `6 g            cnt2++;
        }
    }
8 N/ A' {  g2 C  x    return ;
0 s* q, Q3 F5 M  P/ ^: t}
$ E2 {5 o: F$ H( G# k
) ~! ]0 r9 a: Z3 |6 evoid modify(int i,int pos,int val) {
4 d, u0 ~, D) e7 a7 F( ]    if(t.l> pos || t.r< pos) return ;
" c- L; F0 P' E0 M    if(t.l == t.r) {
8 C+ v2 B9 {( l$ w8 N3 N9 Y' U3 g        t.p[0] = val;
$ A. d, t; S8 [% X, q2 Y( B1 C: y        return ;
# t- G: ]# k$ \9 g    }
) A" `  B7 A' D( I- {3 q8 ^    modify(i<<1,pos,val);
# Q  k0 a* T- ^" H% Y9 @- c" a0 k    modify(i<<1|1,pos,val);
- ^/ n3 U0 E6 k6 [) ~    update(i);
6 v  L* a; h) U; w: ?- Q6 K    return ;
}
1 Y8 F$ y: O, b% e+ ~
vector<int> merge(vector<int> ans1,vector<int> ans2) {
( i, ]7 `3 z' N8 \    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
( N7 K5 n9 a9 R' u  r3 v1 C        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
1 {: C; H# E: L9 C5 c            cnt1++;
0 f) w/ u& A9 x% v        } else {
            ans.push_back(ans2[cnt2]);
4 W7 l* }. O4 e: g            cnt2++;
        }
( J- V' W3 G# h( w    }
    return ans;
6 [/ z$ o2 z* J6 H}
/ [2 x$ v1 v4 t6 l; ?: w
& i% n. p5 g( Y( r+ Svector<int> query(int i,int l,int r) {
    vector<int> ans;
5 [5 D8 o/ S' @0 y$ H, v: _    if(t.l> r||t.r< l) {
9 N2 e, n0 F; _# S        for(int j = 0;j< 8;j++) ans.push_back(0);
- ~! z* @6 k9 r8 d! d        return ans;
: X# }5 `, q- ~- {: t3 c    }

    if(t.l>= l&&t.r<= r) {
        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));
}

int main() {
    cin>>l>>n;
1 `; i' s$ ?' l. Y& u; C4 n
    build(1,1,l);
    char c;
6 E) c+ J3 F& \" I5 M    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
8 b) p2 p3 L9 n, d& M: ]6 y, }        if(c == 'C') {
            modify(1,x,y);
        } else {
            if(y-x+1< 8) {
" o$ |' @. g: D( D; ?5 N1 S                printf("0\n");
                continue;
: S) [: j- S9 v! q            }
6 L( k1 y& `4 ^+ H9 N            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
9 v& D* l/ {+ y        }
    }
, i1 B) E* l5 ~+ M- y( P
    return 0;
}
! U# |) u. ~3 l' d! g
---------------------
8 t/ U6 x! t( Y7 z作者：nka_kun
来源：CSDN

# [$ |- R' l6 f# ^
! d: e; x5 l) Z0 l; p0 @
: ]% X1 ?! h4 P$ J5 S7 T" [- O  H