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

杨利霞

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

题意: 两种操作，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

代码:

) u8 w" d+ Y5 e#include<bits/stdc++.h>
' o; f& P$ _8 Q+ `& n& L#define mem(a,b) memset(a,b,sizeof(a))
0 O% F8 n. Z4 Qusing namespace std;
: T1 S! T) m' ktypedef long long ll;
: A" d7 N2 b8 `( fconst int inf = 0x3f3f3f3f;
* Y( `, j; {; {: M* l) ]8 ~1 nconst int maxn = 1e5+55555;
2 n2 N3 |. L4 I* M7 ?const ll mod = 998244353;
const double eps = 1e-7;

$ z" p" @& [) t  t0 d- pstruct tree {
9 ]. ?3 R/ b/ @5 G) R; m    int l,r;
    int p[10];
} t[maxn<<2];

int l,n;

void build(int i,int l,int r) {
3 X9 a/ g6 C2 [9 b1 F    t.l = l;
1 h' O6 V& }. v8 q' L    t.r = r;
    mem(t.p,0);

    if(l == r) return ;
    int mid = (l+r)>>1;
) P6 c  s  E1 \3 Z$ V    build(i<<1,l,mid);
. {4 x1 A) P7 K8 e# s# |2 |  B1 ]  c0 m    build(i<<1|1,mid+1,r);
    return ;
) B' }2 A) y# a6 {1 Q1 k}

void update(int i) {
$ g; M5 u. R; V. ^9 z    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
& W( Y' _  [6 R            t.p[j] = t[i<<1].p[cnt1];
0 o& V; E0 F0 K- ^            cnt1++;
        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
: _& k3 ~: B9 D( }  U' g        }
& R- V! j2 k, G+ f) v0 W. a    }
' q, R- J" v& E% Q) L3 X8 K    return ;
+ i( _8 T' m8 U3 ]4 r$ _}

void modify(int i,int pos,int val) {
4 W! u+ ^' f) P% I    if(t.l> pos || t.r< pos) return ;
2 U0 f. c: v8 M  {    if(t.l == t.r) {
        t.p[0] = val;
2 R( V- D2 ~$ }. d/ b* K. m# K        return ;
; ^" Z+ ~7 _& R3 t5 s    }
6 X" {6 {4 d( R, H6 u, t* `    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
) g8 C& s7 M- a  V3 @( d# P: q; S    update(i);
    return ;
% E2 q' K& z! \$ m- y}
$ R$ T# `2 ]# r) i5 o/ J
1 g" v) }2 W. d* M2 y' z0 ]vector<int> merge(vector<int> ans1,vector<int> ans2) {
% `% K+ m% d$ U" b! M+ J    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
) s1 h1 h- N* G% D    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
% h. K- X$ F5 E, c& X2 |7 o0 [            ans.push_back(ans1[cnt1]);
; u4 O2 X9 U# P* x2 ~            cnt1++;
        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
9 R& j; s8 U  v# o- }4 S        }
% J) \" a2 E! l2 Z    }
$ U- U9 J- p6 G' s    return ans;
}
2 w# b9 F0 F6 H2 X
vector<int> query(int i,int l,int r) {
    vector<int> ans;
! j" b: g7 Q* E    if(t.l> r||t.r< l) {
2 z4 [7 }" h! V! S/ e( Z        for(int j = 0;j< 8;j++) ans.push_back(0);
, |) x+ U- b" v$ _, {+ B        return ans;
    }
$ Y- j& T5 t; j; W4 ]) {
    if(t.l>= l&&t.r<= r) {
# c% V3 Q  ~5 D9 Z        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
0 X& C3 e9 X$ W' l! Q" U: h* l    }
5 K; t( [) ^+ ?, ~; I% P$ D( [
4 t1 R% o- t4 h* r    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
- Q4 v' O" B3 F! L; V}
2 ^# o. A0 V3 w" u! G' v
* d5 j6 G, P# l# e( }' ~int main() {
    cin>>l>>n;
+ V! e6 g" u7 ^5 _' A
    build(1,1,l);
    char c;
    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
' W7 d) d- I1 [! p; M        if(c == 'C') {
% q& T3 ^( f$ ^+ A            modify(1,x,y);
        } else {
0 \1 U! B  h+ u5 \# C! _            if(y-x+1< 8) {
                printf("0\n");
/ Q  Q7 L! G5 g$ U. s6 I' H                continue;
            }
+ H+ x/ \* m1 g& W# ^& M$ ^            vector<int> ans = query(1,x,y);
6 E+ a0 N2 ^( e5 Q8 L8 \            printf("%d\n",ans[7]);
        }
/ K. k' u- [! q* ~. H    }

    return 0;
9 B- W' p: }7 d# o}
8 @& p4 D; R7 w  n# Q8 C
---------------------
作者：nka_kun
来源：CSDN

- D$ V  x2 j/ B: j3 y

) u4 O  v2 {7 b+ F8 B