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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
8 w3 {+ U# e8 o  P

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
* @  h# N$ v, T) R4 D每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
+ E1 u, ~) S6 y& V; }2 I查询的时候返回含有8个值得list，并不断merge

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
" m# M+ y4 g+ k: D' x2 Nusing namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
" v& w$ V! h* r  m4 E7 D4 uconst int maxn = 1e5+55555;
- T/ T, n. ~6 |5 w; E) mconst ll mod = 998244353;
const double eps = 1e-7;
0 k) e- f; R4 t! a( q
struct tree {
9 t5 N. U. ]0 V, `) h" K    int l,r;
0 Y) u) m/ [* J, {, ~9 ~, r    int p[10];
} t[maxn<<2];

3 Q9 g7 z3 i& g. f, C4 k# {int l,n;

void build(int i,int l,int r) {
    t.l = l;
    t.r = r;
8 n( w( B, c: l) r- Z    mem(t.p,0);

    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
) i; _4 I$ M5 z6 [( F    return ;
: x. z5 Z; H5 W6 f# o}

6 q- l3 [; G3 o# n- bvoid update(int i) {
7 f) O/ z, ~) o4 g9 F+ q    int cnt1 = 0,cnt2 = 0;
7 q: W+ k9 |% Y    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++;
. K0 y8 j' ?! P, o4 d% P6 s9 f        } else {
            t.p[j] = t[i<<1|1].p[cnt2];
            cnt2++;
+ r7 M2 [: l' W0 i0 f& @9 I: X        }
    }
+ ^0 k& N4 k7 v    return ;
}
8 Z7 H2 J# M2 ~( D+ g! I3 h3 A
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;
6 t+ A4 z2 e- o$ T; M5 H* i+ E        return ;
0 |/ a+ t% `7 [5 Q0 q' T. G- l    }
    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
    update(i);
  n8 S8 g4 e8 x" Y- a/ P    return ;
7 V' H, l. |5 u8 L. Y0 H' j) x}
. t& U2 C- l/ b: k& E
. k& A" _3 U& gvector<int> merge(vector<int> ans1,vector<int> ans2) {
    vector<int> ans;
3 c8 Z( G, s  f8 [, s2 H% v  N    int cnt1 = 0,cnt2 = 0;
3 `' `& x' H9 }7 b% @9 c    for(int j = 0;j< 8;j++) {
        if(ans1[cnt1]> ans2[cnt2]) {
: ~4 E# h7 V- B# P8 @; ?            ans.push_back(ans1[cnt1]);
8 \( n0 D8 E8 Z4 |3 D' E4 X            cnt1++;
" d% N' A7 K% g- f; v        } else {
            ans.push_back(ans2[cnt2]);
            cnt2++;
        }
    }
& P& [; t' h8 L1 B9 U1 C    return ans;
}

vector<int> query(int i,int l,int r) {
    vector<int> ans;
    if(t.l> r||t.r< l) {
        for(int j = 0;j< 8;j++) ans.push_back(0);
% k' b! A7 w0 P6 o) Q! W1 L        return ans;
    }

2 ?+ Y* e! ^) `( V  V9 T    if(t.l>= l&&t.r<= r) {
0 S# N/ E9 `; a7 D' |        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
2 |  j% }1 ?7 \0 |" e        return ans;
, H& S" _& z4 x; }. T    }

9 w. d3 E" u. S' x: V4 X& e0 k    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
  C) \! i6 C3 z. e4 H7 d% N}

% B3 A* m2 \4 ]+ F/ D4 P9 U( Hint main() {
    cin>>l>>n;

5 J+ ^" X2 ~2 m% p2 H    build(1,1,l);
    char c;
    int x,y;
+ ?" Y& P+ \7 O! |6 {    while(n--) {
        scanf(" %c %d %d",&c,&x,&y);
        if(c == 'C') {
4 B9 b2 s# s1 x- w            modify(1,x,y);
( J5 r8 M6 T% G- L" R, z) Y* T6 D        } else {
1 S2 M9 m7 ~  L% Z8 L            if(y-x+1< 8) {
# ^/ m# X) T' f7 y( Q                printf("0\n");
                continue;
, b9 e7 W" o$ F6 T            }
            vector<int> ans = query(1,x,y);
7 M( B1 E# i+ a% A            printf("%d\n",ans[7]);
        }
    }

    return 0;
}

" D1 L% Z7 N! r: a) y---------------------
作者：nka_kun
来源：CSDN
1 `6 J( {3 ]/ k1 g' W