1 program minimax
2 const
3 maxs=
1000;
4 maxn=
1000000000;
5 var
6 n,m,box,low,high:longint;
7 s,first,min,max:
array[
0..
1100]
of longint;
8 next,a:
array[
0..
1100000]
of longint;
9 procedure init;
10 var
11 i,j,k,x,y,size:longint;
12 begin
13 assign(input,
'minmax.in');reset(input);
14 assign(output,
'minmax.out');rewrite(output);
15 fillchar(next,sizeof(next),
0); readln(n,m);
16 for i:=
1 to n
do read(a[i]);
17 x:=
1;first[
1]:=
1;s[
1]:=
1;
18 min[
1]:=a[
1];max[
1]:=a[
1];
19 i:=
1;j:=
1;
20 while i<n
do begin
21 inc(i);
22 if s[x]=maxs
then begin
23 inc(x);first[x]:=i;s[x]:=
1;
24 min[x]:=a[i];max[x]:=
a[i];
25 box:=x;j:=
i;
26 continue;
27 end;
28 inc(s[x]);next[j]:=
i;
29 if a[i]<min[x]
then min[x]:=
a[i];
30 if a[i]>max[x]
then max[x]:=
a[i];
31 j:=
i;
32 end;
33 end;
34 procedure del(k:longint);
35 var
36 i,j,x,y:longint;
37 begin
38 x:=
0;y:=
0;
39 repeat
40 inc(x);y:=y+
s[x];
41 until y>=
k;
42 y:=y-s[x]+
1;i:=first[x];j:=
0;dec(s[x]);
43 while y<k
do begin j:=i;i:=next[i];y:=y+
1;
end;
44 if j>
0 then next[j]:=next[i]
else first[x]:=
next[i];
45 if min[x]=a[i]
then begin
46 j:=first[x];y:=
maxn;
47 while j<>
0 do begin
48 if a[j]<y
then y:=
a[j];
49 j:=
next[j];
50 end;
51 min[x]:=
y;
52 end;
53 if max[x]=a[i]
then begin
54 j:=first[x];y:=-
maxn;
55 while j<>
0 do begin
56 if a[j]>y
then y:=
a[j];
57 j:=
next[j];
58 end;
59 max[x]:=
y;
60 end;
61 end;
62 procedure query(p,q:longint);
63 var
64 i,j,x,y,k,yuan:longint;
65 begin
66 low:=maxn;high:=-
maxn;
67 y:=
0;x:=
0;
68 while y<p
do begin
69 inc(x);y:=y+
s[x];
70 end;
71 k:=y;y:=y-s[x]+
1;i:=
first[x];
72 while y<p
do begin y:=y+
1;i:=next[i];
end;
73 while (i<>
0)
and(y<=q)
do begin
74 if a[i]<low
then low:=
a[i];
75 if a[i]>high
then high:=
a[i];
76 i:=
next[i];
77 inc(y);
78 end;
79 if y>q
then begin writeln(low,
' ',high);exit;
end;
80 y:=k;yuan:=
x;
81 while y<q
do begin
82 if yuan<x
then begin
83 if min[x]<low
then low:=
min[x];
84 if max[x]>high
then high:=
max[x];
85 end;
86 inc(x);
87 y:=y+
s[x];
88 end;
89 y:=y-s[x]+
1;i:=
first[x];
90 while y<=q
do begin
91 if a[i]>high
then high:=
a[i];
92 if a[i]<low
then low:=
a[i];
93 y:=y+
1;i:=
next[i];
94 end;
95 writeln(low,
' ',high);
96 end;
97 procedure work;
98 var
99 i,j,k,f:longint;
100 begin
101 for k:=
1 to m
do begin
102 read(f);
103 if f=
1 then begin readln(i);del(i);
end else
104 begin readln(i,j);query(i,j);
end;
105 end;
106 close(output);
107 end;
108 begin
109 init;
110 work;
111 end. 这是一位同仁的代码，看起来真心很厉害的样子。 是的，又到了一天进行总结的时候了，今天说好的块状链表的，我确实搞了嗯，就是不是很专心，以至于现在都还没有搞清楚，这点让我每天总结都羞愧难当，我内心觉得吧，如果一心要搞OI，那看程序的时候就不要上 QQ\人人\贴吧，不然真的时间一下就过去了，等到睡觉的时间到了，才发现fp还空在那里，一动不动。 这样的话，明天还是要耗费在块状链表上了，我会加油努力，在编程的时候一定不会登 QQ\人人\贴吧 ，就这样，明天看看，我究竟有没有做到。 明天搞定块状链表，A掉editor，还有上面的那个题目，这样吧。加油！！
转载于:https://www.cnblogs.com/xiong298/archive/2012/05/06/2485462.html
相关资源：数据结构—成绩单生成器
