http://lightoj.com/volume_showproblem.php?problem=1100
刚一看到这题，要询问这么多次，线段树吧，想多了哈哈，根本没法用线段树做。
然后看看数据范围纯暴力的话肯定超时。然后比赛时就liao那了。
今天是补题，然后做这题，前两发傻逼呵呵的想了一种暴力方法，报着也许能过的心态交了，果然没让我失望超时了。
不说这些没用的了，下面说说这题是咋做的。
没用什么高深的算法，好像算法都没用，就纯暴力写的，关键是加入一种常识来优化。传说中的鸽巢原理，其实有点常识的就会，只不过脑子笨想不到我。
鸽巢原理看这篇博客http://blog.csdn.net/pi9nc/article/details/8506306；
题目给的数据是所给的n个数据的范围为[1,1000];
再看n 给的范围为1e+5;每次询问给你x1，x2,然后找[x1,x2]中两个数相差最小的距离。
那么如过x2-x1>1000,那么在[x1,x2]范围内肯定有重复的数，这个应该很好里解，因为其中每个数的范围都是[1,1000];
假如每个数都不一样那没其中必定有一个数要大于1000，与所给的范围矛盾，然后这种情况特判一下就行。这就用到鸽巢原理了，是不是很简单。
然后每次询问的复杂度就是1000了，那么总的复杂度为q*1000*2;
然后每次询问暴力就行了。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<stdlib.h> 4 #include<string.h> 5 using namespace std; 6 int b[1005]; 7 int main(void) 8 { 9 int aa[100005]; 10 int n,i,j,k,p,q,x1,x2; 11 scanf("%d",&n); 12 for(i=1; i<=n; i++) 13 { 14 scanf("%d %d",&p,&q); 15 for(j=0; j<p; j++) 16 { 17 scanf("%d",&aa[j]); 18 } 19 printf("Case %d: ",i); 20 while(q--) 21 { 22 memset(b,0,sizeof(b)); 23 scanf("%d %d",&x1,&x2); 24 if(x2-x1>1000) 25 { 26 printf("0 "); 27 }//特判 28 else 29 { 30 for(j=x1; j<=x2; j++) 31 { 32 b[aa[j]]++; 33 }//记录出现的数字的个数。 34 int cnt=-1; 35 int vv=2000;//记录最小差距，赋初值大于1000 36 for(j=1; j<=1000; j++)//从1开始循环到1000，所给的范围为【1,1000】； 37 { 38 if(b[j]>=2) 39 { 40 vv=0; 41 break; 42 }//如果出现重复出现多于一个的直接跳出 43 if(b[j]!=0&&cnt!=-1) 44 { 45 if(vv>j-cnt) 46 { 47 vv=j-cnt; 48 } 49 cnt=j; 50 } 51 if(cnt==-1&&b[j]!=0) 52 { 53 cnt=j; 54 } 55 }//这样循环是根据数列的递增的性质，出现的前后个数间保证了间距最小。 56 printf("%d ",vv); 57 } 58 } 59 60 } 61 return 0; 62 }