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

杨利霞

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

2 f* c; ~& t1 T9 b; H5 T

题意: 两种操作，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;
typedef long long ll;
) a; X5 S4 S7 U2 ?const int inf = 0x3f3f3f3f;
$ Q% v  Y4 L9 J+ A& _" iconst int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

struct tree {
) h/ h' x8 p8 r- }    int l,r;
0 D1 C" W- b( G; n0 s7 |0 [  _6 \    int p[10];
8 j9 g# z5 e2 |( C8 b4 r} t[maxn<<2];

: k$ z0 y+ @  o3 m' v) qint l,n;

5 S6 Z) v1 y1 X! V. uvoid build(int i,int l,int r) {
! m, m/ g: \, c* k( f5 D8 Z! W    t.l = l;
    t.r = r;
    mem(t.p,0);

' n2 w" n; c! `7 D    if(l == r) return ;
1 x* l% ^5 G* t" {8 r2 N    int mid = (l+r)>>1;
3 f. n, j- t5 Y    build(i<<1,l,mid);
) V$ }; u- I% h7 U    build(i<<1|1,mid+1,r);
- j8 g5 ^2 r1 B. G, g    return ;
. x$ z* D8 ~, ~% _2 v: g: v0 n' {}

' X' |+ ]2 J8 U* Jvoid update(int i) {
6 [2 g" I! g7 ?- h: [9 l" I1 K3 @    int cnt1 = 0,cnt2 = 0;
; u4 U. L, o2 L2 `+ [$ F; E6 N  J  z    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];
. ?$ p& m  T# I3 k' E1 J            cnt1++;
. p* H6 G' V3 U' P        } else {
$ z$ q+ K9 U( a: m3 N7 ~, k            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
    return ;
}
& N; [, `. G4 u: h4 a7 W
; q1 K/ w1 y- n1 ]/ p* X) p9 @void modify(int i,int pos,int val) {
. M! i1 @) d: Y6 u    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
        t.p[0] = val;
+ [# i% Q1 M8 h. I        return ;
6 q  N4 I  ]9 h2 d    }
4 c1 ^0 C2 [7 B- ~    modify(i<<1,pos,val);
2 ~& E1 E% B' O- v0 w0 D    modify(i<<1|1,pos,val);
    update(i);
* z" V1 }6 C. E' Y2 J2 J" F$ [9 u    return ;
# f+ t6 w8 Q5 }( V- e7 H}
7 h" F) ~8 n* m
vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
7 [2 ^3 Z' j; U( [4 _    int cnt1 = 0,cnt2 = 0;
' u' h4 E7 ^- q* S6 d    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
            cnt1++;
  S* C; }$ F- T        } else {
' k6 _' E$ e6 W/ Z0 e* Q1 u9 v            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
    }
+ Z! g+ k+ p7 Q; V+ P    return ans;
' [$ }- I- r( Z  A}

vector<int> query(int i,int l,int r) {
    vector<int> ans;
1 E" v- Q- b/ C3 u# o    if(t.l> r||t.r< l) {
6 c7 g' G% K' t2 H* l, ^- s        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }
# C5 ~! {+ B- l0 `0 W8 g% x
+ T# }) p+ N# B/ {    if(t.l>= l&&t.r<= r) {
8 [7 k) m& k; E0 C2 H" }- B& M        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
/ M8 D+ y" r" B' W6 Y. j% B        return ans;
    }

+ \6 }. H+ I- [4 o! ]    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
& |' U2 |8 }  y$ I}

int main() {
    cin>>l>>n;

    build(1,1,l);
0 U3 p( C$ c9 s: w3 g& @    char c;
    int x,y;
, @. q) Q5 k' ^8 s9 p/ Z1 ~% S    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
  [; H/ r! e1 o$ J* T            modify(1,x,y);
# y( w! K& B, I2 D        } else {
8 d) T, V8 n. Q6 U2 T) h0 h            if(y-x+1< 8) {
$ @6 K3 P* d2 V7 B) ~                printf("0\n");
. ^& ]" E8 {. ?4 q+ ^                continue;
+ Q2 P0 f4 l: g) Q# Z$ z/ r  o* G$ q            }
8 s0 l+ D0 H7 K  M; o+ h9 D2 B" [" b( I            vector<int> ans = query(1,x,y);
. b) l1 p/ y; v& q9 [            printf("%d\n",ans[7]);
        }
+ f5 N# c: g5 [) _5 T% k1 }% n    }
" G' ^7 F% b0 w9 ^/ m
    return 0;
}

' ^1 A# W7 Z" O3 E---------------------
作者：nka_kun
来源：CSDN
/ M) P* K' `& K4 [( o
. s+ j: A: W* u/ P# K6 T
$ z+ b; r; g$ F  A6 \2 s: W