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

杨利霞

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

% J6 D& L; h) Z: X2 q# \

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

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

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
8 l, C) D# H& `6 etypedef long long ll;
' L( k; g* o# ?const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

struct tree {
" Y9 [+ P" |. m3 {# A2 ]; x; F    int l,r;
    int p[10];
- A- D. K" ?! E! g# u8 A! _+ p} t[maxn<<2];

( `7 x/ |& \- D$ B0 e6 Mint l,n;
, X  `7 |: N7 l8 k1 n
void build(int i,int l,int r) {
: V! i$ z7 _0 T: E+ E$ E" l7 j0 m    t.l = l;
" P1 Z, T! r5 p    t.r = r;
4 @; \4 ~8 K% v    mem(t.p,0);

; B& C& p$ g* r" F' Z# x    if(l == r) return ;
    int mid = (l+r)>>1;
  w8 a0 v+ A; B1 v: G8 G    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
}
( |# j+ q. a) B4 y$ K# p: V
) J3 q5 f3 H5 ovoid update(int i) {
    int cnt1 = 0,cnt2 = 0;
2 d9 |. o) ^* u4 z0 ?6 b" F) o- E    for(int j = 0;j< 8;j++) {
& s1 M2 q( Z# n8 _& ?/ ]: U        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
+ {) h/ [$ ~! J$ z/ R6 T        } else {
0 E+ S  [. ]! |: P/ C; U. L* @: {            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
2 j* ]2 i5 `7 B) _; r        }
    }
$ G' l  a6 X4 w: Q+ @, a    return ;
9 i  G1 ?! v4 |& N2 q( x0 C1 R8 z}
& g, ^: c/ N7 m8 Q
/ [+ ]) D( W* M$ c9 Y; `. fvoid modify(int i,int pos,int val) {
- N2 L0 o2 c" b3 u" W    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
+ H* @4 L) N4 ~# E5 s        t.p[0] = val;
        return ;
& w) n' J5 E7 r4 A    }
& \, A/ o. L( ^% e4 ]+ p+ ^0 T* j8 V    modify(i<<1,pos,val);
1 f. p4 c, ~) i5 ~! _6 K( [    modify(i<<1|1,pos,val);
# ~; Q9 v& C1 b: }5 b8 Q2 S' S    update(i);
    return ;
}

$ O7 d% h$ g- `* @9 O$ H2 kvector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
4 K* C4 H, N& s0 a    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
1 O2 j  a" B$ s' p% H        if(ans1[cnt1]> ans2[cnt2]) {
9 P3 t/ U) N: k5 f            ans.push_back(ans1[cnt1]);
8 m3 L8 v: \* u' N8 T            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
    }
    return ans;
}

vector<int> query(int i,int l,int r) {
% L. K3 E4 _# F( d$ c2 {8 U    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }

! j) P, ]. S5 `$ e' ]    if(t.l>= l&&t.r<= r) {
3 {: f3 o% ~9 {% N        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
/ I+ |3 o$ Y, c4 l3 Z! w7 w        return ans;
    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
! j" ^* g% D- g- O4 h
int main() {
- R7 T) f' J0 G, s    cin>>l>>n;
6 K: r, K) P9 u' `+ K
    build(1,1,l);
  m) O" e- I( X. x0 M0 G    char c;
& [' P% v' [2 `! H8 S    int x,y;
7 s. h* e9 a  P: Z9 K+ _    while(n--) {
' ?* c1 C7 N. }  P! e0 P  u; i& c        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
+ I  \5 y% S) r3 C! }) R" t            modify(1,x,y);
        } else {
& G4 p# ]# V! L. R& t! }9 y            if(y-x+1< 8) {
5 S3 n5 c3 X. w' w                printf("0\n");
3 {! \; g9 L5 v4 I/ W; C/ b" G                continue;
            }
            vector<int> ans = query(1,x,y);
. G( W4 N9 G" f2 K8 V. i9 o+ k            printf("%d\n",ans[7]);
        }
    }
5 N- I! D  {$ r+ b0 B$ {
+ Q3 t$ u1 ^" t( Q  ]    return 0;
}

6 Z. D. f$ `6 q$ V6 w! e---------------------
6 o) y! ^$ e, n9 R. x$ y. }) S作者：nka_kun
  H0 L: z1 R$ s5 H- F7 `( M& \: x来源：CSDN
4 ?  ?2 D- o- \- u( R  C; p# H# w