http://www.gdfzoj.com/oj/problem/64 Problem Description BNU ACM校队有n名队员，从1到n标号，每名队员根据自身情况拥有一个特征值，其中第i名队员的特征值是a[i]。现在BOSS问了m个问题，每个问题给定[l,r]，要求小Q同学马上从标号位于区间[l,r]内的队员中选出两名队员，使得这两名队员的特征值相同，并且不默契度要尽可能小，两名队员的不默契度定义为两名队员标号之差的绝对值。对此小Q同学倍感压力，急需你的帮助。
Input 第一行包含2个整数n、m。
第二行包含n个整数a[1]、a[2]、…、a[n]，保证0<=a[i]<2^31。
接下来m行，每行包含2个整数l、r，请注意所给的l、r均是经过加密的，解密方式是l=l xor lastans、r=r xor lastans，其中lastans表示上一次操作的输出结果，初始lastans=0，保证解密后1<=l<=r<=n。
对于30%的数据，1<=n,m<=5000。
对于60%的数据，1<=n,m<=50000。
对于100%的数据，1<=n,m<=500000。
Output 输出m行，每行包含一个整数，表示最小的两名队员的不默契度，如果不能选出满足条件的两名队员，请输出-1。
Sample Input 5 3
1 1 2 5 2
1 5
3 5
-4 -6
Sample Output 1
-1
2 dhr讲了分块的做法，but我自行脑补出RMQ的水法： 先预处理出下一个与a[i]相等的位置（双关键字，第一为左端点，排个序即可），然后用一个栈维护使右端点单调，因为若第i个区间右端点被前面的区间覆盖，显然此时应该用第i个区间取代前面的区间。这时左右端点均为单调，只要二分查找最左端>=l和最右端<=r的区间内最小值即可，用RMQ做即可。
#include <cstdio> #include <algorithm> #include <stack> #include <cstring> #include <cmath> #define INF 0x7f7f7f7f #define maxn 500000+50 #define a_ first #define b_ second using namespace std; int p[maxn],q[maxn],ans,len,ll,rr,f[maxn][64],l,r,n,m,next[maxn],t; pair<int, int> a[maxn],b[maxn]; stack< pair< int,int > > s; bool cmp(const pair < int,int > &a,const pair < int,int > &b ) { return a.b_<b.b_; } int main() { //freopen("data.out","r",stdin); //freopen("wa.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i].a_),a[i].b_=i; sort(a+1,a+n+1); for (int i=1;i<=n;i++) if (a[i].a_==a[i+1].a_) //next[]=a[i+1].second(); b[++t]=make_pair(a[i].b_,a[i+1].b_); //for (int i=1;i<=n;i++) sort(b+1,b+1+t); for (int i=1;i<=t;i++) { while (!s.empty()&&s.top().b_>b[i].b_)s.pop(); s.push(b[i]); } t=s.size(); memset(f,INF,sizeof(f)); for (int i=t;i>=1;i--) b[i]=s.top(),f[i][0]=b[i].b_-b[i].a_,s.pop(); for (int j=1;(1<<j)<=t;j++) for (int i=1;i+(1<<j)-1<=t;i++) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); //for (int i=t;i>=1;i--) a[i]=s.top(),s.pop(); for (int i=1;i<=t;i++) p[i]=b[i].a_,q[i]=b[i].b_; for (int i=1;i<=m;i++) { scanf("%d%d",&l,&r); l^=ans;r^=ans; ll=lower_bound(p+1,p+1+t,l)-p; rr=lower_bound(q+1,q+1+t,r+1)-q-1; len=(int)((double)log(rr-ll+1)/(double)log(2.0)); if (ll>rr) ans=-1; else ans=min(f[ll][len],f[rr-(1<<len)+1][len]); printf("%d\n",ans); } }