爱华网--------------华丽的分割线--------------------------------------------------------------------刚看到这道题目，我暗笑是个水题。一个简单的思路冒了出来：分别对每段询问的排序，然后找到最小的点输出。这就需要Qsort了。可是回头看看数据范围，100000的数目这样是万万不能的。但是我还是冒着试试看的心情（希望数据很水的说）用这种方法交了一遍，WA，原因很简单：超时。看到这个题目的讨论区，大牛们都喊着要用线段树写。没错，这个题目线段树是正解，可是我想到了一个用Qsort就能过的方法如下（暗自庆幸ing..）。思路是这样的：1.可以先定义一个记录类型，在读入第二行数据时记录一下数据的位置Type datatype=record s,wz:longint;//wz是数据的位置，s是记录读入数据 end;Var a:array[1..100000]of datatype;就拿题目样例数据来说，那么 a[1].s=1,a[1].wz=1;2.好了，下一步就是Qsort（注意排序的时候比较a[i].s,交换时注意把a[i].wz和a[i].s都交换）；举例来说，如果第二行数据为 1 3 2 5 4,排序之前为 i a[i].s a[i].wz 1 1 1 2 3 2 3 2 3 4 5 4 5 4 5 排序之后为 i a[i].s a[i].wz 1 1 1 2 2 3 3 3 2 4 4 5 5 5 43.排序之后再读入n行的询问起始点x,y 因为排序是升序排的，而我们寻找最少的一笔，所以用一个for循环寻找排序完成的数组中第一个位置处于[x,y]范围的，就记录为此次询问的结果（c[i]是记录结果的数组，也可以不用这个数组直接输出） k:=0; fori:=1 to n do begin readln(x,y); for j:=1to m do if(a[j].wz>=x)and(a[j].wz<=y)then begininc(k);c[k]:=a[j].s;break;end;//这里一定注意break，我们是寻找的最少的一笔， Qsort是从小到大排的 end;好了，经过上面几步我们的程序就完成了。这个想法虽然荒唐（....），但是不失为一个解这个题的好办法。（后面有我打的第一个线段树代码，很丑很实用！）[附AC代码]Typedatatype=record s,wz:longint; end;Vara:array[1..100000]of datatype;c:array[1..100000]of longint;i,m,n,j,k,x,y:longint;Procedure init;beginreadln(m,n);for i:=1 to m dobeginread(a[i].s);a[i].wz:=i;end;end;Procedure qsort(l,r:longint);vari,j:longint;x,y:datatype;begini:=l;j:=r;x:=a[(l+r)div 2];Repeatwhilea[i].s<x.s do inc(i);whilea[j].s>x.s do dec(j);if i<=jthen begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end;Until i>j;if i<r then qsort(i,r);if l<j then qsort(l,j);end;Begininit;qsort(1,m);k:=0;for i:=1 to n dobeginreadln(x,y);for j:=1 to m do begin if(a[j].wz>=x)and(a[j].wz<=y)thenbegininc(k);c[k]:=a[j].s;break;end; end;end;for i:=1 to k-1 do write(c[i],' ');writeln(c[k]);End.
#01:Accepted(0ms, 1804KB)
#02:Accepted(0ms, 1804KB)
#03:Accepted(0ms, 1804KB)
#04:Accepted(12ms, 1804KB)
#05:Accepted(0ms, 1804KB)
#06:Accepted(0ms, 1804KB)
#07:Accepted(0ms, 1804KB)
#08:Accepted(28ms, 1804KB)
#09:Accepted(75ms, 1804KB)
#10:Accepted(67ms, 1804KB)
Accepted/ 100 /182ms / 1804KB
[附线段树代码]Vart:array[1..100000]oflongint;//这里的树数组只开一个，记录区间最小值a:array[1..100000]oflongint;//按输入顺序记录的数组i,m,n,j,k:longint;Function min(x,y:longint):longint;beginif x<y then exit(x) elseexit(y);end;Procedure build(l,r,p:longint);//递归建立线段树varmid:longint;beginif l=r then t[p]:=a[l]elsebeginmid:=(l+r)shr 1;build(l,mid,p shl1);build(mid+1,r,(p shl1)+1);t[p]:=min(t[p shl 1],t[(pshl 1)+1]);end;end;Functiongetmin(p,l,r,gl,gr:longint):longint;//查找区间l，r的最小值Varmid,lmin,rmin:longint;Beginif (gl=l) and (gr=r) then exit(t[p]);mid:=(l+r) shr 1;if gl>mid then exit(getmin(p shl1+1,mid+1,r,gl,gr))elseif gr<=mid then exit(getmin(p shl1,l,mid,gl,gr))elsebeginlmin:=getmin(p shl 1,l,mid,gl,mid);rmin:=getmin(p shl1+1,mid+1,r,mid+1,gr);exit(min(lmin,rmin));end;//考虑三种情况：查找区间在左侧，查找区间在右侧，还有查找的区间涵盖左右侧的区域End;Beginfillchar(t,sizeof(t),0);fillchar(a,sizeof(a),0);//数组初始化，好习惯readln(m,n);for i:=1 to m do read(a[i]);build(1,m,1);for i:=1 to n dobeginreadln(j,k);write(getmin(1,1,m,j,k),'');//这里很不规范，但是tyvj评测是忽略多余空格的end;End.
![TYVJP1038[忠诚] www.tyvj.cn](http://img.aihuau.com/images/31101031/31021822t01ac7702ca1a336d89.jpg)
#01:Accepted(51ms, 2980KB)
#02:Accepted(0ms, 2980KB)
#03:Accepted(12ms, 2980KB)
#04:Accepted(4ms, 2980KB)
#05:Accepted(145ms, 2980KB)
#06:Accepted(0ms, 2980KB)
#07:Accepted(145ms, 2980KB)
#08:Accepted(75ms, 2980KB)
#09:Accepted(200ms, 2980KB)
#10:Accepted(59ms, 2980KB)
Accepted/ 100 /693ms / 2980KB
