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

杨利霞

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

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

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

代码:

#include<bits/stdc++.h>
+ _# ]: G' l  K8 m$ R' z  L' K6 [4 g2 j#define mem(a,b) memset(a,b,sizeof(a))
& v% f3 o5 H, E: n/ b; Fusing namespace std;
* H% J8 K# k; v+ f' ~" S! Z0 Htypedef long long ll;
% n# ^+ @- g3 m& I9 S( bconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
+ S) v) r! t) uconst ll mod = 998244353;
6 e# J" U- x; _* ?$ ?9 ?' X$ ^const double eps = 1e-7;

struct tree {
# h/ ^( n* d# J4 q    int l,r;
9 I  |% E/ Q7 S; `+ M8 J4 u4 r/ |4 S8 O    int p[10];
} t[maxn<<2];

. ^# K0 c2 V' x  yint l,n;
1 P, e0 [% n$ M+ W
5 y& l' `# v* R& x8 C$ ]void build(int i,int l,int r) {
    t.l = l;
/ f, ?4 J  q- F  W    t.r = r;
" U5 N; Q  ^/ L. f+ _0 |: p    mem(t.p,0);
/ b5 \6 O  x# X/ q0 A4 G
- A) D  o6 |0 Y: D9 f3 Y- B    if(l == r) return ;
% _; }' Y  B" Q% |" W: k    int mid = (l+r)>>1;
2 v) O8 @, t) K$ X    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
  ~. u9 O5 E7 P  {* c7 L, M    return ;
$ t5 R; S; h# v' s}
& ]& Y7 n! }2 S% ?& s  u* ~
void update(int i) {
8 V4 w$ {: Y# R    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
2 ?2 m$ Q3 o, ~" ?+ G0 R            t.p[j] = t[i<<1].p[cnt1];
            cnt1++;
5 w& g/ t* P) |& @" n: }        } else {
; V" N% S# x, i            t.p[j] = t[i<<1|1].p[cnt2];
* H0 \& k( L6 J; q% [0 W6 q- q            cnt2++;
+ V; @) Y+ N1 a) h( G/ {- o. s  J        }
6 M5 u# f+ f9 C6 {7 ^    }
9 |6 p  ]2 f# Z3 Y7 u! N    return ;
}
4 i9 n* z& o7 A8 U: [8 L) i1 ]  T- Z
void modify(int i,int pos,int val) {
0 ]' `; ^1 N% O- |* |0 c    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
        t.p[0] = val;
        return ;
    }
0 h% I4 X! \# W- I) c/ k. _# G    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
    return ;
}
7 Z/ ]4 o2 w1 H8 M' M
4 [9 O9 a; K$ jvector<int> merge(vector<int> ans1,vector<int> ans2) {
* R0 z5 O( D/ U4 c+ K$ x    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
3 E& I! R/ j4 y    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
- ^. v+ D+ R' e% r, F            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
    }
$ W' i$ p2 f3 e2 L4 p; C: Q    return ans;
- P6 a3 @. i& }( K+ p}
) {5 v9 t( r$ u1 a# }& s8 {
/ _) `6 ~" I" b! f- ]7 U. L) g! Xvector<int> query(int i,int l,int r) {
    vector<int> ans;
    if(t.l> r||t.r< l) {
4 Q9 L- ~' Z: G- I0 y. X/ ]        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
" i! ]- ]% ~( M    }
+ @; l/ [5 S/ Z4 n+ n; R1 _$ {
    if(t.l>= l&&t.r<= r) {
+ C: G- U; l3 g0 e; N6 m        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
7 f% a2 I5 n% D$ [% U: g. j& `7 F    }

    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
7 a$ M2 a5 k' F9 B$ ]% V}
, h+ e% n0 Q0 s& g3 \/ @
: Z  U- b. j6 h9 J9 |int main() {
# b8 V: x; n% y. E2 f: B9 T    cin>>l>>n;

    build(1,1,l);
    char c;
    int x,y;
; v$ a, t5 b3 p* x' U" I: O    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
: a& h6 X7 t. x& i( Q" k1 P        if(c == 'C') {
  p# Y  m8 T# J            modify(1,x,y);
        } else {
            if(y-x+1< 8) {
                printf("0\n");
                continue;
            }
7 Y: v7 u4 A: i  E! Q! |            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
' x2 w$ v4 m4 W9 N: ]3 B2 ~    }

7 L  f* L) G$ v6 t    return 0;
}

. D, ~9 s8 J% Q' z) E' y# g4 k---------------------
7 n9 I! d; G4 H  ?作者：nka_kun
来源：CSDN

( F* T8 u2 i3 f1 u
# [# N9 u( e, D- s4 e