数学建模社区-数学中国

标题: 2019第十届蓝桥杯B组决赛题解第九题 [打印本页]

---

作者: 杨利霞    时间: 2019-6-28 16:17
标题: 2019第十届蓝桥杯B组决赛题解第九题
2019第十届蓝桥杯B组决赛题解第九题
) {" _$ s# B, @/ Z, L  y9 M* P
. y" |: }* ]2 E$ `7 b0 S

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
% n) m  g4 g% Z4 c! y. b* f0 Y每个节点存储它管辖的这个区间的前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;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
5 D) j! ~4 Y" E$ A( |const ll mod = 998244353;
6 E" e% A; n2 s# d1 Y1 }4 ~const double eps = 1e-7;

/ `: E8 l- r& P/ ~; Ustruct tree {
$ h) @: Z' X! _  W9 f! I* _( t! e. A6 p    int l,r;
( M. t, w8 T$ k    int p[10];
! @+ I% s5 C. H, N! e8 a* x} t[maxn<<2];
- O9 f& Y3 j! |' j" U0 M2 p0 B
int l,n;

/ Z/ N2 H2 ^  }) F1 vvoid build(int i,int l,int r) {
( G( b- i% L3 y0 g/ w    t.l = l;
  b( b0 Q8 W  J- o$ `    t.r = r;
  q( _2 ?- i! @$ t    mem(t.p,0);

$ b6 C" j" \% D9 {6 q- S* W    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
5 L0 c" j, S# ^    return ;
}
- _) w0 g; `, \" f. ^4 Y* L! x
void update(int i) {
5 |/ O7 |+ h' G. d* t    int cnt1 = 0,cnt2 = 0;
    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 {
            t.p[j] = t[i<<1|1].p[cnt2];
5 o) L! |2 J+ q4 w0 {            cnt2++;
        }
* P1 r& `8 A) }+ _    }
    return ;
7 o8 n! e5 b, Z4 x}
+ m0 U( {( v; _1 y: [
void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
        t.p[0] = val;
+ U+ j2 l. Y- }3 Q1 ^# I1 v+ W% U        return ;
" V$ B3 Z& X& g3 Q1 b    }
3 o- E8 M- q4 t& E/ \8 @    modify(i<<1,pos,val);
4 r( J: |5 [, h4 U: M    modify(i<<1|1,pos,val);
    update(i);
/ e6 n$ G. C4 I" [3 D5 J    return ;
}
- q5 f% U0 j! \/ D9 a
vector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
$ w0 o  E; k3 G! O    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
1 O, k9 p" C% y3 X( k            ans.push_back(ans1[cnt1]);
            cnt1++;
1 E$ B; t  |+ s7 R) ?8 B        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
0 @' s$ l, C0 j        }
0 c& w$ y2 A: k; A4 ^  _. M6 s    }
1 D& }/ E( D! k+ z/ v. u& y' C    return ans;
0 f. J# _) C. F}

9 W  t7 H& v' ^1 M) Xvector<int> query(int i,int l,int r) {
/ o- I) A7 Q8 R& w$ b+ x% t    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
        return ans;
7 H! r1 ]5 o4 T& ]0 Q: K0 T    }

; J" r5 W2 h5 `, n0 g    if(t.l>= l&&t.r<= r) {
9 W4 s& M* S0 \* a$ g9 l- H        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
3 h; S* d4 ^. R. X: u2 c1 v$ q        return ans;
$ p+ g+ T  u5 z2 y    }

8 [9 z  u* {$ J- `" |    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
}
  p. E2 d. S. Q5 |
' Z$ [7 E7 r/ v' j2 [$ Vint main() {
    cin>>l>>n;
! V- W9 |3 r4 h8 G4 Z( t
! f. V) L  V( J9 }' S4 d/ u- F    build(1,1,l);
! _& g0 ]7 W7 C' L    char c;
    int x,y;
    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
6 u5 X  v; F& u" ]" U        if(c == 'C') {
0 w  H9 x& I# e            modify(1,x,y);
/ p: x0 D) l5 T$ b3 }" b& K/ a        } else {
" q# L4 ~8 E" T0 c4 Z            if(y-x+1< 8) {
                printf("0\n");
( [, [* N9 c  `' Y9 ?1 g                continue;
) f5 V9 w, a+ ~% U            }
            vector<int> ans = query(1,x,y);
5 h! N6 y% u) w- b9 Q: U! O! R            printf("%d\n",ans[7]);
        }
    }
, `6 C+ k5 @6 g! B! r
$ ]6 t! f& y) {) Y& Y, F    return 0;
}
( e# E  r' ~3 Y$ j* i4 {
---------------------
2 `& E7 ~: k. J6 t4 T. L作者：nka_kun
来源：CSDN

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5