2019第十届蓝桥杯B组决赛题解第九题
9 _: ~; z1 F6 x$ B7 _! }$ r/ n' E5 O1 a$ p4 G6 o( V8 t4 B
题意: 两种操作,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))- B" X3 o& s7 v. W
using namespace std;
9 H; U4 K2 n7 {! }2 ~* ?typedef long long ll;% r: I* {9 F$ L4 s$ O+ o! N- x. Y# W1 w# ~
const int inf = 0x3f3f3f3f;( i# O6 \( o [+ K- G
const int maxn = 1e5+55555;- e7 q7 C4 b# Q9 M$ D: `* d4 \
const ll mod = 998244353;
( Z5 t2 D s# N% {; a; L( [const double eps = 1e-7;
# o: w$ M: @9 Q9 m8 _% L6 b T5 Y& ]: n" W# U
struct tree {* @9 e8 \4 K- O: ^6 W9 {( E* S" G! u
int l,r;3 j D+ Q* v9 X
int p[10];
6 U1 ?$ Y) K; R) d R} t[maxn<<2];/ H) Y6 a i4 ~$ E
$ T# B- I7 N, qint l,n;& O4 O/ p7 {" y
& i Z" b: g5 j" q
void build(int i,int l,int r) {- F# c3 T: C9 Y* K; q9 x8 I9 u
t.l = l;
! ^' u% ~6 D& ^ t.r = r;9 w& `$ \8 n% F0 J0 _8 S/ F% h
mem(t.p,0);. ` c+ g5 h( Q% M3 g% x" i% P ]' J: E
9 P$ I& ?" }) J! D- {& C$ Q! G
if(l == r) return ;. n+ s9 X7 \. ]3 g
int mid = (l+r)>>1;; G$ B1 @) i c
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} z5 g1 {# {! q( v
+ g& G( T9 K* S) q3 B0 _
void update(int i) {* a+ q4 I. Z$ ?* l1 \4 V; o' J2 U. C: ^
int cnt1 = 0,cnt2 = 0;% M. z& J: V3 T/ k) v/ L7 h
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 }3 v. f8 f1 S3 T& M5 K1 Z8 {
}
) 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% u2 n! U. i& T+ Y# q
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) {: J+ L. b; |0 ?' {/ ] N
t.p[0] = val;8 n2 }6 h5 U' p* J2 }: }
return ;0 ^/ p$ k; E& e b1 f, M
}
_, ]2 o5 O; F k( W modify(i<<1,pos,val);' x+ W! o* n3 G0 \+ D, a+ x
modify(i<<1|1,pos,val);
W/ |, Z# h& Z: G! j1 n update(i);7 k5 M, M5 O9 S" Z, g |! G
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;5 g0 m- ?# h+ p% ]
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]) {: m) I6 A5 r) G5 p, l! ^. c- E' ^% [* Y
ans.push_back(ans1[cnt1]);
- r: X3 `! V( S, x9 W+ u- b cnt1++;7 a9 d d. C- T
} 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( @ }" U( {2 f m3 y: m! o9 ~! e4 b4 c
return ans;7 |' p7 n3 B5 U7 z: K
}
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) {0 N5 q* z. p1 N2 U
for(int j = 0;j< 8;j++) ans.push_back(t.p[j]);) O6 h% ]8 B% Q# ]' P* c
return ans;
: M' D/ E/ M; r" A- o+ x }
4 Z6 S% K0 S" \% M* j. b$ u( o! t! l
return merge(query(i<<1,l,r),query(i<<1|1,l,r));
, e g+ l" `1 k) V: @& Y}& p- K) o4 i4 ~) _/ H' `) E5 X- C- ]6 R7 W
! 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);4 d: N" Z" G/ I) ?& V8 g( C3 [
char c;& c% s8 H& \ U6 X
int x,y;( w$ I* p+ J$ \1 f/ c
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);( n; N% _1 i$ |/ h4 X. [
printf("%d\n",ans[7]);7 w# a2 D% G; I& Q
}, B+ ~7 I, I- w; R
}
7 v: E; l$ q3 Y1 P5 k# [' d. Z( w3 t
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--------------------- ( D! w7 `7 N! ], O6 w, Z5 ?
作者:nka_kun
4 t( ?6 p' p8 Q1 M9 ^" \来源:CSDN * k% G; T/ U/ n; ~" Y7 m: w6 b
6 L9 e8 k( Q; ~" |, i/ d8 }1 p
/ o6 M* S3 R& f5 E, _& ~$ r
1 k" I( K/ p( q' d
|