tyvj P1039 충성 2 - 선분 트 리 동적 조회 구간 극치 실현

17135 단어 선분 수
링크 를 드 리 려 고 했 는데 tyvjp 1039 충성 2. 여러분 이 직접 찾 아 보 세 요.이 문 제 는 구간 극치 문제 가 분명 하고 동태 적 이어서 RMQ 를 사용 할 수 없다.선분 수 는 비교적 좋 은 선택 이다.그리고 저 는 한 가지 문 제 를 발 견 했 습 니 다. 예전 에 선분 트 리 와 같은 것 은 코드 가 비교적 죽는다 고 생각 했 습 니 다. 대체적으로 똑 같 습 니 다. 사실은 제 가 틀 렸 습 니 다. 고급 데이터 구조 쓰기 가 살 수록 유연성 이 강하 습 니 다.안 타 깝 게 도 이번 생 에는 noi 가 없 었 습 니 다. 간단 한 문 제 를 스스로 학대 하고 시원 하 게 찾 을 수 있 었 습 니 다!비극 이 야!
 

  
    
1 type
2 ji =^ rec;
3 rec = record
4 l,r,min:longint;
5 lson,rson:ji;
6 end;
7
8 var
9 a:ji;
10 b:array[ 0 .. 100000 ] of longint;
11 i,j,x,y,m,n:longint;
12
13 function minn(x,y:longint):longint;
14 begin
15 if x < y then exit(x);
16 exit(y);
17 end;
18
19 procedure build(var a:ji; l,r:longint);
20 var
21 mid:longint;
22 begin
23 new (a);
24 a ^ .l: = l;
25 a ^ .r: = r;
26 mid: = (l + r) >> 1 ;
27 if l = r then
28 begin
29 a ^ .min: = b[l];
30 exit;
31 end;
32 build(a ^ .lson,l,mid);
33 build(a ^ .rson,mid + 1 ,r);
34 a ^ .min: = minn(a ^ .lson ^ .min,a ^ .rson ^ .min);
35 end;
36
37 function find(a:ji; l,r:longint):longint;
38 var
39 mid,k:longint;
40 begin
41 if (l <= a ^ .l)and(r >= a ^ .r) then exit(a ^ .min);
42 mid: = (a ^ .l + a ^ .r) >> 1 ; k: = maxlongint;
43 if mid >= l then k: = minn(k,find(a ^ .lson,l,r));
44 if mid < r then k: = minn(k,find(a ^ .rson,l,r));
45 exit(k);
46 end;
47
48 procedure change(var a:ji; x,y:longint);
49 var
50 mid:longint;
51 begin
52 if (x = a ^ .l)and(x = a ^ .r) then
53 begin
54 a ^ .min: = y;
55 exit;
56 end;
57 mid: = (a ^ .l + a ^ .r) >> 1 ;
58 if mid >= x then change(a ^ .lson,x,y);
59 if mid < x then change(a ^ .rson,x,y);
60 a ^ .min: = minn(a ^ .lson ^ .min,a ^ .rson ^ .min);
61 end;
62
63 begin
64 readln(n,m);
65 for i: = 1 to n do read(b[i]);
66 build(a, 1 ,n);
67 for i: = 1 to m do
68 begin
69 readln(j,x,y);
70 if j = 1 then write(find(a,x,y), ' ' )
71 else change(a,x,y);
72 end;
73 end.

좋은 웹페이지 즐겨찾기