2019第十届蓝桥杯B组决赛题解第九题/ \3 O: \: {" p' t) K$ u( G
- n2 }3 g; t5 J, p题意: 两种操作,C x y,将x位置的数修改为y,Q x y,查询[x,y]之间的第8大值,y-x+1<= 8的话输出0 思路: 区间第8大值,线段树在时间、空间都够了(蓝桥怎么会让手写主席树。。)
0 J* d1 Q2 y4 z+ t7 e8 ]+ z每个节点存储它管辖的这个区间的前8大值,修改的时候暴力merge,单次修改复杂度log(n)*8
8 ?% R" ~3 }2 O4 f$ B查询的时候返回含有8个值得list,并不断merge 代码: 9 R( P! _# j: {* k8 y% @
#include<bits/stdc++.h>
; i- c! \5 f6 W- @4 u4 d#define mem(a,b) memset(a,b,sizeof(a)): x- Q# Q5 Q" \2 E4 \
using namespace std;
3 w& {: Y+ p/ w7 s4 g) a# P$ Ztypedef long long ll;
4 _( a* q6 M @# f7 Zconst int inf = 0x3f3f3f3f;% c9 W8 I1 K8 ~6 r3 o p9 f! [' K
const int maxn = 1e5+55555;
6 h# N3 L8 _" c# M/ yconst ll mod = 998244353;
( e8 P: K+ I- u8 v! B+ E7 Dconst double eps = 1e-7;, U7 [5 f" K( {) }# a
G* W& _3 n# l( ^5 U9 n. Q
struct tree {
! Z$ O" h6 |" m+ m, O6 {3 v int l,r;
' \8 J& v) j1 Z | int p[10];
: Y! N D1 e, M+ C} t[maxn<<2];; A( A* d+ d" w7 p7 |. v7 G
' G: j, o% Z/ G6 d0 b2 ^int l,n;1 x* w9 S% z! e; L+ V
3 m+ _$ ] D# E1 T7 j `
void build(int i,int l,int r) {2 E P* i. A. j$ t; z
t.l = l;
2 T& f5 ^# f7 a% |. \) W! [7 ~0 ` t.r = r;& P& N# Q6 e* F% R: x
mem(t.p,0);/ x) ^/ G: g* `3 ~3 D% J. w) g
3 ^5 e4 E% _4 X0 e3 u7 y if(l == r) return ;# t2 z) g( j: M' Y6 R' w
int mid = (l+r)>>1;
3 B2 p, J/ {, a) z# D3 o build(i<<1,l,mid);
. H7 v; O. W2 B* C& v& m build(i<<1|1,mid+1,r);
: v6 ]9 r5 ?7 o return ;
$ g) d. a! Q" W4 }/ t}
4 \, W8 x) i! ?3 {0 \9 P# B2 Z& ~+ d) C0 m2 B5 w8 f) ]
void update(int i) {% C2 g% \. E4 Y
int cnt1 = 0,cnt2 = 0;6 Y7 _0 o- y# V& X. F6 j7 a
for(int j = 0;j< 8;j++) {
& a& ` C+ \6 V4 X5 @ if(t[i<<1].p[cnt1]> t[i<<1|1].p[cnt2]) {
% a6 q9 G% k" p- b0 _& H; ]4 L t.p[j] = t[i<<1].p[cnt1];$ B0 \3 {( [: a
cnt1++;
* U! b; z! z7 V } else {& t) P! Y. L9 k) b! t: v
t.p[j] = t[i<<1|1].p[cnt2];3 g9 Y7 J0 w% N7 k/ C# r& b
cnt2++;- U) v5 {& q5 B! I! P; M9 ?9 j9 C
}
$ C$ i# p* n" C0 B# E' p# O) c$ R }! u* m* l) b3 E! x4 B# l+ {3 D
return ;9 V6 j& j( Q$ x4 e) L' z
}
7 z1 E; B0 m1 g4 k7 G5 A+ T: O
void modify(int i,int pos,int val) {
# ?/ h+ ?- e8 P! C" n8 f: a if(t.l> pos || t.r< pos) return ;; C8 H8 S& E: ~$ K4 s d2 C" Q
if(t.l == t.r) {
z; e0 ~# z' ^( l" l w) U t.p[0] = val;
* Y$ l, h. M& [9 F1 E; n9 | return ;
& S/ m/ G2 f/ j0 R& t }
: x* p6 t: B. E modify(i<<1,pos,val);
$ @& B' f, P% p; z1 q& C: b5 P) l modify(i<<1|1,pos,val);9 g! V( [8 W, l' e+ y& S/ f0 }
update(i);
5 u8 o4 v* u# _+ [ return ;
8 v: v& @& n( R, A}
8 b6 [; x% t" b4 H/ a4 E! ]
7 z) M( u/ R' g( ~/ c. J6 Wvector<int> merge(vector<int> ans1,vector<int> ans2) {
1 f% U! `) C, d' s% H& P vector<int> ans;3 d# ]2 y; f4 O. D" R
int cnt1 = 0,cnt2 = 0;0 P" y) M. V; `: ~- W& u0 }
for(int j = 0;j< 8;j++) {
" A2 N9 \0 q- y) B% K# u# {! a' x* R if(ans1[cnt1]> ans2[cnt2]) { G/ T4 z x$ P. {* U
ans.push_back(ans1[cnt1]);$ [: s3 p$ {: N0 @! Y& Q. p+ C
cnt1++;
( Q6 l- c- h! `8 H } else {' O7 d) \4 K/ V7 p1 i- f V
ans.push_back(ans2[cnt2]);
# V4 H8 d d! o+ K- F cnt2++;8 ~. i7 l4 {8 ?) y M
}
" w/ k( |8 x' V( Q8 Z9 u3 k9 L }
1 n0 c6 I5 q/ O0 { return ans;7 o' B7 }/ O- K
}
1 F) g' s5 c6 m" C T" v& Z" R: q# [* ` k0 j+ D3 L: k% |
vector<int> query(int i,int l,int r) {* V4 F6 L5 o8 H- v
vector<int> ans;
" i* b3 N! Q7 o: Z if(t.l> r||t.r< l) {! d( f3 W7 q1 W! w( \) t
for(int j = 0;j< 8;j++) ans.push_back(0);
X; f9 w& v) @! |0 c1 i return ans;( k- d7 C3 R- E
}
% _/ u( W$ P% k- q" `" _ u" _9 k) Q- b' e( J' u0 b3 m$ |
if(t.l>= l&&t.r<= r) {3 o1 k" h/ V* t' F
for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);
0 h1 _/ ]+ L) k, v4 b* r return ans;
1 A& ]& Q( L. O) d }1 |5 [ U' N4 l, _2 b3 G; R2 A
1 g) V+ ^/ w. F4 f4 d; z! k return merge(query(i<<1,l,r),query(i<<1|1,l,r));& X1 o/ C: z" w& z, R2 Y
}
) r( L, `& @, C# \- h
) b* a. e) W9 v0 s' P. \5 Mint main() {$ A+ d8 i, v0 O6 w
cin>>l>>n;# M: Y1 g5 F- U8 b5 w. R: N
@, j7 g2 i9 K4 x U- j build(1,1,l);$ }' V& [! f2 s/ `) X' L u
char c;
, B; w2 ^1 y1 f+ q1 g" d: L int x,y;
' o8 Q( Z2 {" g! ~$ I7 P while(n--) { B2 e3 C) q( w
scanf(" %c %d %d",&c,&x,&y);0 ?1 s, W: v# Y& X4 T( U3 R
if(c == 'C') {
3 @7 x2 \ k1 v% P6 } modify(1,x,y);& |! @$ w( A, j4 E
} else {& c) i3 @0 e3 E" `! p/ \4 T
if(y-x+1< 8) {4 ^2 G. t0 f, v3 |8 `+ e: l
printf("0\n");
$ Z8 i. r6 l6 l) s0 q" c continue;
/ u; m! g" |7 r: e9 n' l( d& K7 W }
& W7 i# Y* a# X5 D1 J! F! ~ vector<int> ans = query(1,x,y);
. a. \ p/ b) b+ K3 T% `7 F) p printf("%d\n",ans[7]);. _/ d2 y5 G/ D; k5 r
}2 |& o. }/ R& G, U; H7 J$ F
}
% l; K. P: u5 L4 ^& B9 }9 G9 [7 W7 q U! E
return 0;7 k/ m2 y0 f( i/ q7 b4 R$ t, g
}) R, r# a5 m i, A5 S8 r/ c
3 `- x& Y$ _( v, [, b5 ]---------------------
& p5 k$ M! L0 S9 n作者:nka_kun
$ v: @# i, {6 ] p* X来源:CSDN
: {9 o# p5 I8 w; A; }7 b! _3 L1 n
3 d7 j/ @) g9 q B2 y
7 |6 ~' V2 {0 \3 I2 M+ D6 I$ z |