数学建模社区-数学中国

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

---

作者: 杨利霞    时间: 2019-6-28 16:17
标题: 2019第十届蓝桥杯B组决赛题解第九题
2019第十届蓝桥杯B组决赛题解第九题

$ y  m) Q, W1 n; o% L# I

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
% E% K4 r( z" R( O) N3 [$ u0 L每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
  Y" r) Y* \. O' q  O#define mem(a,b) memset(a,b,sizeof(a))
9 b% Z/ F; g5 m; D3 w' d6 t/ ?; eusing namespace std;
. J" t4 Y' S& f0 Ytypedef long long ll;
, Q. y7 P) X! W( B' w4 L9 nconst int inf = 0x3f3f3f3f;
; G1 u. c# h4 K; {const int maxn = 1e5+55555;
6 ^6 C- k+ {; fconst ll mod = 998244353;
7 y9 l5 i$ D7 R+ N0 ^9 Tconst double eps = 1e-7;

struct tree {
' ~2 e/ V9 C8 {' @2 L- |    int l,r;
    int p[10];
- Z6 l$ x7 ~" }# C} t[maxn<<2];

5 w" g- B& M2 B: H5 H% _int l,n;

void build(int i,int l,int r) {
    t.l = l;
    t.r = r;
    mem(t.p,0);

7 `6 @  S  o, a) P. p# e/ [9 T2 x    if(l == r) return ;
    int mid = (l+r)>>1;
  A/ L, ^0 o  g$ G' l( P! i6 E    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
, w2 }. ^# T1 Z) q. e- W1 f6 G" j    return ;
: h' m$ r" x! n$ v: }- `}
/ s0 \' J! P$ c: e3 J6 V
void update(int i) {
    int cnt1 = 0,cnt2 = 0;
1 J( O) ]$ m7 a: k) P    for(int j = 0;j< 8;j++) {
5 k& f& @1 R" y, Q! f. B  H        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];
            cnt2++;
        }
+ C4 X0 k# m4 R! R0 N6 A& S' _    }
    return ;
}
- l# s- v) l; ^8 U  Z
: P) E9 H1 \, F9 l+ ]void modify(int i,int pos,int val) {
    if(t.l> pos || t.r< pos) return ;
    if(t.l == t.r) {
% y  v4 Y6 d, ?8 u" m# N$ ^        t.p[0] = val;
        return ;
    }
' B/ a/ y" J) T2 U- y/ f$ ]7 s% R$ L    modify(i<<1,pos,val);
- u* j, l, l6 ~0 i, K    modify(i<<1|1,pos,val);
6 u  @) R! i+ w& ^: |* u3 a    update(i);
    return ;
+ ]& M' L2 S% C6 `' n6 u}

vector<int> merge(vector<int> ans1,vector<int> ans2) {
0 \$ o# |+ D7 e; Q    vector<int> ans;
- U. \: [  Q! I    int cnt1 = 0,cnt2 = 0;
. [2 }, V; T3 l9 n6 F    for(int j = 0;j< 8;j++) {
+ J- h6 u6 u, L' a        if(ans1[cnt1]> ans2[cnt2]) {
3 J) |4 f6 Z7 U2 k, T( k4 O! Z            ans.push_back(ans1[cnt1]);
            cnt1++;
        } else {
1 p7 T- u% r) t$ M+ Y            ans.push_back(ans2[cnt2]);
; f2 Z5 F) h& }2 q* I3 e7 y* A            cnt2++;
9 C) W* V( n! p4 X$ k        }
4 o8 ?; l, S6 x5 z& B    }
5 \7 Y7 G2 o7 U    return ans;
* _" X9 J/ H+ |& F, M0 s- ^3 A5 q}

vector<int> query(int i,int l,int r) {
. h6 r7 [/ J/ \0 v5 d9 x+ n3 h    vector<int> ans;
    if(t.l> r||t.r< l) {
1 U( {* A& X, @9 A        for(int j = 0;j< 8;j++) ans.push_back(0);
, [( j4 y! G0 g' q        return ans;
6 c0 F8 {" g. H9 M6 {3 N0 i    }
0 H% t+ M  U! Z. C0 _" E1 |
: y% }6 N! a2 r' G/ R. J    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
    }
2 ?7 D$ m' q" O- G6 p" Q2 Q: Q6 r( ]
6 T6 U, V' `# i/ ]0 M( f' ]    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
4 R  b5 C( B" o5 \8 e+ V+ i- i# ^  L}

int main() {
7 u& ?- Z/ {( u9 C    cin>>l>>n;

0 A8 ?4 |3 c; P  t. }0 }1 \$ r; M    build(1,1,l);
/ h% ]( x) U9 ?4 [; `9 T. Y; ]2 i    char c;
    int x,y;
; E( i* x, W) ?: J! A9 p6 {6 J    while(n--) {
& ?  E, N' x, T7 A6 b        scanf(" %c %d %d",&c,&x,&y);
- \& R4 P" g! ^4 u% D        if(c == 'C') {
            modify(1,x,y);
% f% g  w0 E  `. E! G        } else {
' p( N5 Z$ {5 V( k            if(y-x+1< 8) {
                printf("0\n");
                continue;
            }
            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
    }

- P6 W- D7 _6 o# J9 P: \    return 0;
}

---------------------
, ?* G. d: N/ ]/ T& s作者：nka_kun
来源：CSDN

6 S; h5 i! d- h1 H7 V
; k1 T- Z7 B3 M; s. u
2 I$ L6 g" m9 q' G8 H  d  U# |& k# k

---

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

Powered by Discuz! X2.5