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

杨利霞

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

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
5 d6 E2 h+ N) p# o. E* y! k每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
( d' A2 u( @2 K  {# q! N查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
* |. u- [" X8 a7 p0 l#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
. i8 Q: I, u5 ~2 Bconst int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
8 e" G0 c% P" P1 R7 e  T8 Wconst ll mod = 998244353;
const double eps = 1e-7;
9 _; J  r1 w6 V. ^, h" n
& h1 J2 S9 U3 Q  o2 }( vstruct tree {
+ Z  I4 C! V) j' u$ i4 f  [: ]! u    int l,r;
) H2 k8 y* b0 ?    int p[10];
} t[maxn<<2];

- r* Y: ]0 R" G) e% W2 a. dint l,n;

5 k; @2 l  S! f3 `: zvoid build(int i,int l,int r) {
    t.l = l;
    t.r = r;
    mem(t.p,0);

1 v' M( h8 z6 \5 i* C' B    if(l == r) return ;
    int mid = (l+r)>>1;
3 f8 m2 v2 V8 j/ E- `/ {  |  n    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    return ;
  D. P* D9 {$ X; \5 q}

, H% |+ E" Q6 n# f1 {$ Ivoid update(int i) {
& t; R' Y4 E3 R6 W1 @; u1 E+ F- D( ^    int cnt1 = 0,cnt2 = 0;
* J( Q- M7 j: @# ^    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];
            cnt1++;
        } else {
" S3 J  b8 L3 D9 X            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
        }
    }
    return ;
. |6 n/ y! E# X# L4 F}
% X* Q3 s' N. X
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
9 m! p4 P5 W/ F1 n1 \. [    if(t.l == t.r) {
        t.p[0] = val;
- ]0 G5 i9 o+ N7 r, ^3 N        return ;
0 A) e& V: P. f) V8 i    }
    modify(i<<1,pos,val);
5 o: ^9 Y) o6 Q# W; I) T    modify(i<<1|1,pos,val);
    update(i);
    return ;
}
0 N1 q4 I; h" D. e3 D. d$ d2 e+ L" ?! w
vector<int> merge(vector<int> ans1,vector<int> ans2) {
- V4 }% X4 P$ q" Y" t+ X    vector<int> ans;
2 V4 \" m5 H) Z% V/ ^    int cnt1 = 0,cnt2 = 0;
3 G- m! F1 K: e4 A) g# t6 O    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
, X" |- J9 ^, @% n4 e$ E/ P6 V$ p            cnt1++;
/ @# Q: s* d8 V6 [8 y- Z* A5 R7 q        } else {
            ans.push_back(ans2[cnt2]);
  u6 K! L; W# o! Y9 c, m            cnt2++;
        }
    }
5 e2 p1 m! y4 T1 ^    return ans;
}
* w3 B& y9 x4 l1 X/ c1 E) ~/ m8 a
vector<int> query(int i,int l,int r) {
( Y* k( j' a; F6 ~1 }& W    vector<int> ans;
. S1 Y/ B: O+ u* e    if(t.l> r||t.r< l) {
+ ?: f: p/ D$ Q        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
    }

# T- f) J/ v& U- z. z    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
) [/ \: R2 @% C' l+ A& o; U        return ans;
) k+ J, d5 ?' S0 C( p    }
9 v4 {1 `* \/ Z# y
    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
8 J: u, T7 I& h$ {}
* t* I! T7 H% A# M
int main() {
    cin>>l>>n;

    build(1,1,l);
    char c;
    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
5 D. _# m6 U! C* H! b            modify(1,x,y);
$ i8 x, I2 k/ x; C3 h; K$ x        } else {
            if(y-x+1< 8) {
2 M4 N5 E+ }$ I6 Q; J. q1 o                printf("0\n");
                continue;
! Z3 f( |% _+ I. {            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
* y6 F( M4 {  L' {$ z1 l    }

    return 0;
}

3 S9 q3 T. b3 i# c---------------------
: B; p: l. d! j0 ?- D, }, O作者：nka_kun
  A& w# K4 T+ Z( }) A来源：CSDN

, j: W" F3 Y$ D& m/ l3 ~
$ u0 O5 Y8 P; m0 R# A
2 z9 q" ^1 p3 m2 j5 ]/ e