Killer Problem （UVA 11898 ）
Problem You are given an array of N integers and Q queries. Each query is a closed interval [l, r]. You should find the minimum absolute difference between all pairs in that interval.
Input First line contains an integer T (T ≤ 10). T sets follow. Each set begins with an integer N (N ≤ 200000). In the next line there are N integers ai (1 ≤ ai ≤ 104 ), the number in the i-th cell of the array. Next line will contain Q (Q ≤ 104 ). Q lines follow, each containing two integers li , ri (1 ≤ li , ri ≤ N, li < ri) describing the beginning and ending of of i-th range. Total number of queries will be less than 15000.
Output For the i-th query of each test output the minimum |ajak| for li ≤ j, k ≤ ri (j ̸= k) a single line.
Sample Input 1 10 1 2 4 7 11 10 8 5 1 10000 4 1 10 1 2 3 5 8 10
Sample Output 0 1 3 4
题解：因为给的N个数的范围很小，如果查询的区间的长度大于10000，那么区间一定有重复的数字，所以结果返回0，如果不是，把这个区间的所有出现的数记录在数组中，跑一遍[L,R]区间，求得相邻的出现的差值最小就是最后的答案。（根本不是线段树QTQ）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int Max = 10004;
const int inf = 0x3f3f3f3f;
int a[maxn];
int b[Max];
int main()
{
int t,n,m,i,l,r,ans,last;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i = 1; i <= n; i ++)scanf("%d",&a[i]);
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&l,&r);
if(r - l + 1 >= 10000)
{
printf("0\n");
continue;
}
else
{
memset(b,0,sizeof(b));
for(i = l; i <= r; i ++)
{
b[a[i]]++;
if(b[a[i]] > 1)
{
printf("0\n");
break;
}
}
if(i <= r)continue;
ans = inf;
last = -inf;
for(i = 1; i <= 10000; i ++)
{
if(b[i]==1)
{
ans = min(ans,i - last);
last = i;
}
}
printf("%d\n",ans);
}
}
}
return 0;
}腾讯云开发者
