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)
#includeusing 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;}