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

杨利霞

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

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

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

代码:

- W; H' [4 b5 o#include<bits/stdc++.h>
9 x: h9 j) p( e" p" D, @#define mem(a,b) memset(a,b,sizeof(a))
2 p. [' W% s% kusing namespace std;
, ~; x9 J' g' ^" W' utypedef long long ll;
1 o1 I3 }5 I# T4 o' Mconst int inf = 0x3f3f3f3f;
5 z+ W1 C& k9 n3 c3 k8 X4 _const int maxn = 1e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
/ @# r* p6 c2 G0 l. P0 [8 j: \
2 M# g# T3 `9 J/ c7 j4 p5 U& E. Vstruct tree {
( n1 s7 s4 G3 c    int l,r;
6 L& m1 g; z7 [    int p[10];
3 _7 N2 E# V1 x} t[maxn<<2];
8 S: b. E& a/ N. G
int l,n;

void build(int i,int l,int r) {
) _4 i6 O+ s1 h0 ^  @- f# I! u1 J    t.l = l;
6 S+ n. E( q# S5 L5 g0 O  {    t.r = r;
% f: L7 r+ |$ l# ]3 K, j    mem(t.p,0);

    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
5 d9 p7 i& w- t3 r. x2 i3 y    build(i<<1|1,mid+1,r);
  c6 I% q/ ^2 f1 n" C8 ~6 ?    return ;
}

$ t" [$ ?: G7 i8 [9 F9 Nvoid update(int i) {
; n1 e, z) z8 X4 ?- f/ W' p+ [' t2 o. I    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
6 g/ w9 \$ ]3 [' ]        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
& `0 j* U7 F1 a' U4 E- |" |" k            t.p[j] = t[i<<1].p[cnt1];
. x, ?: I: U% T4 {0 V            cnt1++;
        } else {
* M( t. w" i. h- }            t.p[j] = t[i<<1|1].p[cnt2];
' a. N! W# Q% `( ^- R8 B            cnt2++;
+ W7 Z+ {3 x- V# N/ g& E        }
( ]* p5 k2 L$ C8 b0 v, r4 n    }
1 ^* _$ G' o, {" t" \- W: m4 Y% J) ^    return ;
1 p2 I' Q& z& i9 C0 H}

void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
; y. R& @+ b5 @) Z& |        t.p[0] = val;
        return ;
    }
7 w3 |+ K8 y$ n+ H    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
' @& F" v; E6 [' b9 n$ `" m    update(i);
. r3 O- Z, U6 U7 ]8 D. t9 Y    return ;
}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
+ w' f, ~- X$ }: N/ N0 y    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++;
$ ?  @0 {0 m1 x" q* x        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
: L0 v- F; n* W2 `( [1 X% Y5 E        }
    }
    return ans;
% W0 I0 k; Q  E}
0 A; J6 `2 ^' g9 I
" G% Z8 B& n* M) Evector<int> query(int i,int l,int r) {
5 b5 G$ `5 Q# n1 K    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
: z' `9 W' ^" W  q) ~" Z+ Q* L        return ans;
    }
! z4 y! y/ |! U1 r' l/ R
    if(t.l>= l&&t.r<= r) {
) P+ L+ q# x9 g* `        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
# ?' C0 x4 U+ _) d- m( K1 {# d        return ans;
    }
. a2 Z  S4 a4 R4 p1 M& w
% j. p/ P- e8 X! k# q    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
& U$ G0 Y" ^4 n- w( z' {0 A}

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

    build(1,1,l);
7 Y, |/ F4 h, T: I# Q+ {& q    char c;
5 d9 u& z8 v0 T& L( f! D    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
0 T9 o# d) D/ A# v0 @- _0 X        if(c == 'C') {
            modify(1,x,y);
, m, S( c5 v) s3 \; O; L; Z        } else {
            if(y-x+1< 8) {
                printf("0\n");
/ C2 e2 T8 J3 {7 E. Z                continue;
            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
# V" r* _/ f; k' q  a7 f1 O& U/ X4 A        }
    }
; \2 x/ x8 p7 P6 Z$ c/ Z
    return 0;
8 \& O$ D  Y( o$ @# l}
) C- b' M2 _" b$ E: }4 c4 M
---------------------
作者：nka_kun
7 f- J2 K( H& {: }5 K来源：CSDN