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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
8 V! {% l8 u3 \# M

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
* Z9 b$ N8 g7 j; J& G每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
查询的时候返回含有8个值得list，并不断merge

代码:

8 Q+ _3 B' r: f#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
3 Z7 L) a" c: Mconst ll mod = 998244353;
6 }, x/ Y: x3 ]$ s2 Q( h+ rconst double eps = 1e-7;
1 }1 H% x3 Q: {" \, a
3 _9 Z; |+ ?  Dstruct tree {
1 s* @. q  [$ H( [    int l,r;
! {( G- O9 y3 l6 e8 s& ^% u3 F    int p[10];
} t[maxn<<2];
& \/ T! u/ h7 H& T) c
$ i4 X# O  ?" x+ s. d/ Fint l,n;
4 Z4 }* N) P' o' j2 E2 Y- q  @
void build(int i,int l,int r) {
    t.l = l;
9 V7 p& b5 m* v, G' X6 ~/ [    t.r = r;
: m4 ]' M2 W1 h- R    mem(t.p,0);

    if(l == r) return ;
    int mid = (l+r)>>1;
5 @7 X7 h- I# y6 u1 o4 n    build(i<<1,l,mid);
7 B" W" a4 V5 I# [: Z" ^    build(i<<1|1,mid+1,r);
    return ;
' a2 q) U+ l9 ?" N. s5 N' c3 g}

8 Y) ]# d. |' M' g/ t7 qvoid update(int i) {
& k7 o! q$ T$ m' D% R8 {    int cnt1 = 0,cnt2 = 0;
  Z# F3 n# u/ e6 k4 M    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
$ ]0 F9 }3 _; N& L" S4 I6 d& j5 Z            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
9 y/ Z1 L0 [5 Z( U  u    }
    return ;
}

void modify(int i,int pos,int val) {
  Z8 E4 s: ^0 ?    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
8 ]) g  h2 y# C1 y# Z5 e        t.p[0] = val;
        return ;
% ]5 {) k' T" U5 h    }
" s1 S8 y1 W. O% n- C    modify(i<<1,pos,val);
% j+ C  F( @. v1 K9 `+ t    modify(i<<1|1,pos,val);
    update(i);
    return ;
}

vector<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]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
- e/ r) Z0 G. z; v9 k: q& p  ]" O8 O. k        }
    }
: D7 T* l& _/ W# L- L: g, ~    return ans;
}
+ @8 M( A, V% }& ~7 k
0 g6 I. W/ N3 y' |# R! k. Uvector<int> query(int i,int l,int r) {
! M% w8 i" ]8 s    vector<int> ans;
+ M) M# D8 O" d9 \* G) o/ F    if(t.l> r||t.r< l) {
4 p3 v3 _+ M0 Z* ?& }        for(int j = 0;j< 8;j++) ans.push_back(0);
  L/ k' D& H* T& M0 E  _        return ans;
. d" j4 W* x. S" k: c6 [    }

8 o8 w" C6 P& X* W% L8 m+ a6 m    if(t.l>= l&&t.r<= r) {
7 D  b1 n/ S3 S, H        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
  x# E8 r3 S% `+ I2 X    }
/ l9 S! o9 c+ k
* N, u9 ]' ]% A' {    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
) @& l+ e+ ^& E: C; V}

int main() {
, n! p, |% o$ j+ I$ C    cin>>l>>n;
/ x: M, }5 m; V+ J
+ m6 w' P5 a' ~: q    build(1,1,l);
7 l  {/ H* r$ Y6 D4 G* V- W/ x- z    char c;
    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
            modify(1,x,y);
8 A) m$ L- G" ?        } else {
            if(y-x+1< 8) {
                printf("0\n");
                continue;
            }
3 z8 z8 e& C. z: a2 T$ |            vector<int> ans = query(1,x,y);
  y# Y7 x/ Y7 v( P            printf("%d\n",ans[7]);
        }
    }

    return 0;
8 _) Q8 t1 Z4 C7 _/ W}

0 X" P: ]4 a, c$ h3 w: Z" c---------------------
作者：nka_kun
来源：CSDN


1 |  o* n  P( k1 i! U
) K# y9 |3 \: f9 C8 G$ r