题目：http://www.gdfzoj.com/oj/problem/64
描述：给一个长度为n的数组a[i]，和m个区间<l,r>，求<l,r>内最小子区间<i,j>使a[i] == a[j]（n,m<5*10^5）
一开始想到 离散化+RMQ，但后来发现RMQ不能像维护区间最值一样用max/min维护该问题
正解是主席树或分块，时限5s，但分块写好的话1s也能过（746ms水过），其他题解写在注释里了
关于块的大小的推理可能不是很严谨，具体还要看不同题目的数据范围.
下面放代码
#include <cstdio> #include <map> #define k(x) ((x-1) / K+1) //x属于分块中的第k(x)块 using namespace std; const int N = 500010,K = 150,M = N / K + 10; //K为块的大小 当K=1000时耗时1620ms,K=150时耗时746ms(相信玄学) //M为块数 int a[N],f[M][M],nxt[N],pre[N],n,m,i,j,l,r,ans; //f为分块数组 f[i][j]表示第i块到第j块的最小方案 //想不到只用next数组的方法，于是nxt[i]表示 a[i]=a[nxt[i]] 且 nxt[i] > i 的最小值 //pre[i]表示 a[pre[i]]=a[i] 且 pre[i] < i 的最大值 map <int,int> q; //偷懒用 map 离散化 inline int min(int a,int b) { if (!a) return b; if (!b) return a; return (a < b) ? a : b; } //求a,b的最小值，特判a==0 b==0 int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) { scanf("%d",a+i); j = q[a[i]]; if (j) { nxt[j] = i; pre[i] = j; f[k(j)][k(i)] = min(f[k(j)][k(i)],i-j); } q[a[i]] = i; } //一个简单的用 map 实现的离散化 复杂度约 O(n log n) for (i=1;i<n/K+1;i++) for (j=1;i+j<n/K+1;j++) { f[i][i+j] = min(f[i][i+j-1],f[i][i+j]); f[i][i+j] = min(f[i][i+j],f[i+1][i+j]); } //i为区间长度，j为起始位置，一个预处理 //f[i][i+j] = min(f[i][i+j],f[i+1][i+j],f[i][i+j+i]) //复杂度 O(n²/k²) while (m--) { scanf("%d%d",&l,&r); l ^= ans; r ^= ans; ans = f[k(l)+1][k(r)-1]; //块内最小答案 O(1) for (i=l;i<k(l) * K && i<=r;i++) if (nxt[i] <= r && nxt[i]) ans = min(ans,nxt[i] - i); l = i - 1; for (i=r;i>(k(r)-1) * K && i>=l;i--) if (pre[i] >= l) ans = min(ans,i - pre[i]); //暴力枚举块外答案(pre和nxt的作用) 复杂度 O(2k) if (!ans) ans = -1; printf("%d\n",ans); } //综上，时间复杂度约 O(n log n + n²/k² + 2mk) //代入n=m=500000，k≈540。但n,m<500000，因此k取约150-400是有一定道理的。 }