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

杨利霞

2019第十届蓝桥杯B组决赛题解第九题
9 _: ~; z1 F6 x$ B7 _! }$ r/ n

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

思路: 区间第8大值，线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
, Z7 P/ b% x& [8 m( T每个节点存储它管辖的这个区间的前8大值，修改的时候暴力merge，单次修改复杂度log(n)*8
* [$ B! K% R  i& m  g- U& k查询的时候返回含有8个值得list，并不断merge

代码:

6 A0 O' @0 ]5 S#include<bits/stdc++.h>
3 c, o" y% d. C) U#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
9 H; U4 K2 n7 {! }2 ~* ?typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+55555;
const ll mod = 998244353;
( Z5 t2 D  s# N% {; a; L( [const double eps = 1e-7;
# o: w$ M: @9 Q9 m8 _
struct tree {
    int l,r;
    int p[10];
6 U1 ?$ Y) K; R) d  R} t[maxn<<2];

$ T# B- I7 N, qint l,n;

void build(int i,int l,int r) {
    t.l = l;
! ^' u% ~6 D& ^    t.r = r;
    mem(t.p,0);

    if(l == r) return ;
    int mid = (l+r)>>1;
    build(i<<1,l,mid);
3 X+ @* _" Z  v; p    build(i<<1|1,mid+1,r);
2 d& X: H$ ?7 l2 J# l5 M4 F3 ?* L; L    return ;
4 n6 x* K. a7 t* }# j}

void update(int i) {
    int cnt1 = 0,cnt2 = 0;
    for(int j = 0;j< 8;j++) {
: E/ i& r* k: C* i& n  x- s7 f: d        if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
  Q) x1 w" E' K; D$ \  x6 v2 l* C            t.p[j] = t[i<<1].p[cnt1];
( o) f; ^$ N5 |. h* h            cnt1++;
5 I* |0 @2 K1 z# m6 M        } else {
3 F9 G$ {6 s* ]$ s) C" K3 h& f            t.p[j] = t[i<<1|1].p[cnt2];
- ^# r4 G8 }" h            cnt2++;
5 {: {3 b: D" v0 C        }
    }
) Q& V: [5 H0 h6 M5 ?: w; ?    return ;
9 {1 u6 @4 S- ]2 L9 A* C* n}
5 j  j" I2 |4 J3 W  n% u
void modify(int i,int pos,int val) {
# u6 r0 e2 D+ H, b& j+ D* l4 X1 O    if(t.l> pos || t.r< pos) return ;
; [" O. Z0 `) V- T9 J    if(t.l == t.r) {
        t.p[0] = val;
        return ;
    }
  _, ]2 o5 O; F  k( W    modify(i<<1,pos,val);
    modify(i<<1|1,pos,val);
  W/ |, Z# h& Z: G! j1 n    update(i);
    return ;
0 l$ y! {% k: A9 M% m! p6 O}
% z3 u( k- H# O; B( g6 P. q3 m7 p& J
$ k# C; {2 Y* D) j' Jvector<int> merge(vector<int> ans1,vector<int> ans2) {
$ U" {3 J' O, G+ r; W6 q! |+ P2 M    vector<int> ans;
    int cnt1 = 0,cnt2 = 0;
& N" O7 q- V7 {7 n/ k    for(int j = 0;j< 8;j++) {
5 l8 w- T# S4 P7 H' i, @        if(ans1[cnt1]> ans2[cnt2]) {
            ans.push_back(ans1[cnt1]);
- r: X3 `! V( S, x9 W+ u- b            cnt1++;
        } else {
$ n2 V* N3 @+ h            ans.push_back(ans2[cnt2]);
6 C8 |  l& R8 R3 }& L2 `- _            cnt2++;
7 H. N- X  A8 y( ?& c# B7 P        }
9 f; k' G/ K- E  c2 t9 z( @    }
    return ans;
}
8 U6 O. }# p8 f2 @' R0 @+ q# F$ r
# D; c3 z9 U5 N6 Wvector<int> query(int i,int l,int r) {
' [" A6 w& L* c    vector<int> ans;
' Q" W0 `3 r2 k& z$ l    if(t.l> r||t.r< l) {
* Q9 {/ D! S1 M        for(int j = 0;j< 8;j++) ans.push_back(0);
# q7 J7 z- X0 k/ n( Q+ ~$ G- }        return ans;
2 h# Y- U; s. F7 V. o1 a/ q    }
( @3 T( ?% `4 @+ b9 ~' v* \7 g
+ r/ C9 e8 D6 f6 S    if(t.l>= l&&t.r<= r) {
        for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
        return ans;
: M' D/ E/ M; r" A- o+ x    }
4 Z6 S% K0 S" \% M* j
    return merge(query(i<<1,l,r),query(i<<1|1,l,r));
, e  g+ l" `1 k) V: @& Y}

! w/ \+ U" }- ]9 ^3 \int main() {
+ R1 Z0 F3 ~% a! g5 u6 O0 J* {* r    cin>>l>>n;
! V- o. N5 I+ O3 |0 ]& [: ~' J5 K
* O1 z4 X( {" {) S8 m5 `/ ]    build(1,1,l);
    char c;
    int x,y;
    while(n--) {
0 `- j8 |. F" }9 ~0 z1 m0 ]        scanf(" %c %d %d",&c,&x,&y);
+ U3 h7 y# P* n' ?        if(c == 'C') {
* m: d. c6 J3 i8 C# c* j            modify(1,x,y);
9 I: I5 s, {2 R& }$ w, [4 }4 U, G        } else {
3 W0 `) Q! }. S5 s            if(y-x+1< 8) {
" I6 |! e" X8 S& t$ ?  _4 o                printf("0\n");
4 \3 l3 P5 H# G0 Q                continue;
* Y( c& c  `; D2 s; H; r' }            }
8 r( @: f7 [9 X6 v! ?* I            vector<int> ans = query(1,x,y);
            printf("%d\n",ans[7]);
        }
    }
7 v: E; l$ q3 Y1 P
    return 0;
3 I' Q" B8 |4 w; b1 b" |; @! ?0 z# \8 F}
0 u  @+ Z5 k6 X! ]+ q7 {
( ]* V- H3 C6 t' J* m---------------------
作者：nka_kun
4 t( ?6 p' p8 Q1 M9 ^" \来源：CSDN