2019第十届蓝桥杯B组决赛题解第九题
7 x8 k9 p8 r+ ^# g! h3 W& B7 m! R7 v* A4 H. U' F7 z7 Q) o
题意: 两种操作,C x y,将x位置的数修改为y,Q x y,查询[x,y]之间的第8大值,y-x+1<= 8的话输出0 思路: 区间第8大值,线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
1 l) ?7 \8 l' z" m; {每个节点存储它管辖的这个区间的前8大值,修改的时候暴力merge,单次修改复杂度log(n)*8
; h3 i1 G! k& _% C查询的时候返回含有8个值得list,并不断merge 代码: " W' c! }- z7 E! J+ w" U
#include<bits/stdc++.h>: \ p+ E5 R' C
#define mem(a,b) memset(a,b,sizeof(a))2 N0 L8 n$ z1 O1 I* ~( r
using namespace std;. @! ^, Z" k4 `- i
typedef long long ll;% e, _; y( p S h$ P: H
const int inf = 0x3f3f3f3f; y3 g. H+ i& h% L9 @# ]- R
const int maxn = 1e5+55555;
* w) ^" K( Y- F# _, m8 \3 Bconst ll mod = 998244353;
( |/ ?, k4 c& H. p3 Econst double eps = 1e-7;
- q* _; Y( r9 U5 `
: x( |1 n" _$ [) mstruct tree {- T) k9 t- j; }- P4 H
int l,r;; j- l0 m" g* B' {) S9 a
int p[10];! q4 H) a5 F0 E. } ~
} t[maxn<<2];
, ^9 g% x! Q2 N" P$ I0 Y7 o& m3 j0 \
3 d1 j. v- r7 w r6 B: r# m7 rint l,n;, J. ]6 b/ ]2 M
; U& W8 u3 P$ p& \( H. wvoid build(int i,int l,int r) {
, b) r W- D0 d t.l = l; K( }- q8 g0 V$ {: Z X, ~) M
t.r = r;
' r& o/ y2 V, \0 r mem(t.p,0);- B9 Q7 O5 ]0 B
1 ^# d" V- w( G, s Q
if(l == r) return ;
. U8 i9 f5 V" q4 b% {) T& g int mid = (l+r)>>1;+ Q" i' S0 A. e/ t: h- C
build(i<<1,l,mid);
1 N u; q" J% s+ U. @0 S build(i<<1|1,mid+1,r);' ]+ S7 j8 A4 I$ p0 K
return ;3 |) \2 {: x! q1 K; @$ _
} `' u2 p6 y/ v1 |2 l ]; f
- Y0 B& t+ f# b) ^void update(int i) {7 W# d+ R) J9 C3 i- o6 p
int cnt1 = 0,cnt2 = 0;# t/ p" L! U3 F. W$ U+ @: ` k
for(int j = 0;j< 8;j++) {
, a& A9 Z' U" d; g$ y. h) I* i7 ]( d if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {' |3 b- Z( B1 u# K! {7 H% f
t.p[j] = t[i<<1].p[cnt1];
6 x7 a) p$ |0 q# r+ E cnt1++;% S3 l( U6 M y9 d4 d; w
} else {
1 q! M. q( {0 w! r; W# [6 d; j t.p[j] = t[i<<1|1].p[cnt2];
0 v& O6 x5 Y! l' [6 r+ Z# i0 j! \ cnt2++;% T* n: m( Q0 V3 W' I f) i( J
}
! }- G% h% t6 i$ t4 C4 G% O }" b# M. @7 x% P6 T- D5 e
return ;
K. U7 K- w ]: |}" {& i9 a- C5 n# g
0 \) w+ n6 w9 D) J2 R& c+ Svoid modify(int i,int pos,int val) {
" A4 a/ a1 R) w if(t.l> pos || t.r< pos) return ;0 x _- p; w# d. P3 F0 Q
if(t.l == t.r) {
8 A! A2 l t7 \& R1 O7 e6 r! d t.p[0] = val;* w# o" q0 \0 K. G/ ]5 ~
return ;( j- u! Y" D6 l
}
: d. a' @! `: Y1 b4 \7 S modify(i<<1,pos,val);
# x$ u1 W) S1 [ modify(i<<1|1,pos,val);
5 B9 A9 w7 P% K) `0 ^0 _$ t6 i update(i);
: C' B* n6 z3 g. M9 T* g# x0 e return ;* L8 v" | ]) x" H. Y
}" v& |. U6 T! H9 Z4 G: n2 z
8 x0 F9 v" d5 i }% W5 E/ x6 Z a/ T+ Z. M
vector<int> merge(vector<int> ans1,vector<int> ans2) {
5 X& K( m; r C+ {. }9 O vector<int> ans;
( {) ~8 B* t! a int cnt1 = 0,cnt2 = 0;
9 C- `6 E4 g+ v6 P9 X0 |& v for(int j = 0;j< 8;j++) {
8 Y5 T8 ]- U# q& _. g. l) Z if(ans1[cnt1]> ans2[cnt2]) {
" _4 s4 n& f, x6 O( e" Q ans.push_back(ans1[cnt1]); {; g$ `- `% E
cnt1++;* ]2 ^+ H$ v" L+ e, H
} else {
" l2 \; s* \8 x k- g ans.push_back(ans2[cnt2]);, p/ |. d5 F, x) u
cnt2++;
- }7 |& ?* n% X4 \+ k }, r0 M+ c; v y7 i! u% D
}3 _1 r# ^7 |' U
return ans;$ g7 P4 F7 `, T& V. z3 s+ @
}. b6 A f, M) t
& h6 a) q4 S: q' O% g% V, @7 p
vector<int> query(int i,int l,int r) {
# M+ |% `3 h& E' ]; [' e vector<int> ans;# Q& A2 e) S. `# @. T" }' e2 i4 |
if(t.l> r||t.r< l) {
6 `4 O! O ^7 A z- D: ]6 _ for(int j = 0;j< 8;j++) ans.push_back(0);1 ]6 x/ c/ B. e7 i7 U* H
return ans;
* }/ t p/ k$ x! a }! q6 y. \, c) X
; U1 C, r6 U; s# S& |3 { if(t.l>= l&&t.r<= r) {
+ T b9 ^7 p! d- ]9 p( L for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
5 A, x% q0 X3 c: a5 ~* R return ans;
5 x6 g9 J+ a% r) | }+ n4 w; e$ I* \3 O2 b0 x: g+ H7 `
: g8 E# o( Z) A
return merge(query(i<<1,l,r),query(i<<1|1,l,r));
0 o+ f Q/ ^! ~/ A2 j}* e' j6 r8 F' e; l
8 W2 B0 z. x2 tint main() {# H5 Q& R7 K/ E* ]6 V
cin>>l>>n;
1 j! V% ]9 `" m7 h
, Z( p# ^- G0 v7 J5 C% Q* ~ build(1,1,l);
2 B4 k `; t; S. F9 g/ B char c;
6 ^" z" o2 x! C int x,y;7 L6 h# ^2 z, U" {3 n, t
while(n--) {1 N2 O0 D0 P7 d7 I+ a( F
scanf(" %c %d %d",&c,&x,&y);' u2 J" I/ l* A8 F4 u
if(c == 'C') { S8 }$ q( O8 t! O+ A
modify(1,x,y);
7 e9 j1 H4 }2 K* o1 c, S } else {
5 Y9 T) n: ~4 K if(y-x+1< 8) {
5 b3 r5 I9 b; K) h printf("0\n");
/ Y$ t7 d; e( c continue;
) S( r+ M5 s. j+ N }6 L7 x6 g- C9 r8 i% }
vector<int> ans = query(1,x,y);! w, e6 @4 l, m! Y3 z) p
printf("%d\n",ans[7]);
9 S+ I7 G" C" j' |7 f }
9 r* b" L% q4 w; E/ ?) |* c3 b% y }: O' T, k3 H8 P" s4 U) ]
* Z" m% E( ~4 W6 ^
return 0;; ? Q) _& C( H! v3 U, H$ J
}
7 z" |2 J; V2 U# p+ t/ x. b& H: Y0 O% L- H9 W9 a/ E& M" A
--------------------- * G* A' z: A6 {& \3 ]8 S2 z
作者:nka_kun 9 P1 W& Y1 h \' A8 v0 ^
来源:CSDN
) S' `' M' [4 P. p
. h f. X$ a0 h; Z/ x0 s$ P1 B8 Y' H7 Q4 F# ?1 y3 P
7 j1 W0 L0 W9 ]) _) X |