传送：http://acm.hdu.edu.cn/showproblem.php?pid=6483
题意：有长度为$n$的数组，对于一个子区间$[l,r]$内，存在最大值$mx$与最小值$mi$，有$q$的询问，每个询问要求判断在某个子区间$[l,r]$内$[mi,mx]$的值是否连续存在，即$mi,mi+1,....,mx$每个数都出现过至少一次。$T=5，1<=n<=10000，1<=a_i<=10^9，1<=m<=100000$
分析：
多个区间查询问题，考虑莫队算法。
对于每一个询问，需要判断$mi$到$mx$内的数是否全部存在，且需要知道$mi$与$mx$。考虑先预处理出每个子区间的最值，离线查询。
$a_i<=10^9$，数组$num[]$没办法开下，需要离散化处理。
先ST预处理最值，然后离散化，莫队求区间内值种类的个数。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
struct node{
int l,r,id,block,mx,mi;
}q[maxn];
int a[maxn],b[maxn],maxPoint[maxn][],minPoint[maxn][],num[maxn];
bool ans[maxn];
int cnt=,n,m,block,ll,rr;
bool cmp(node p,node q){
return p.block<q.block || p.block==q.block && p.r<q.r;
}
void add(int x){
int tmp=a[x];
if (num[tmp]==) cnt++;
num[tmp]++;
}
void del(int x){
int tmp=a[x];
if (num[tmp]==) cnt--;
num[tmp]--;
}
void init(){
for (int i = ; i <= n; i++){
minPoint[i][] = maxPoint[i][] = a[i];
}
for (int j = ; ( << j) <= n; j++){
for (int i = ; i + ( << j) - <= n; i++){
int p = ( << (j - ));
minPoint[i][j] = min(minPoint[i][j - ], minPoint[i + p][j - ]);
maxPoint[i][j] = max(maxPoint[i][j - ], maxPoint[i + p][j - ]);
}
}
}
int queryMin(int l, int r){
int k = log2((double)(r - l + ));
return min(minPoint[l][k], minPoint[r - ( << k) + ][k]);
} int queryMax(int l, int r){
int k = log2((double)(r - l + ));
return max(maxPoint[l][k], maxPoint[r - ( << k) + ][k]);
}
bool calc(node tmp){
if (tmp.mx-tmp.mi+==cnt) return true;
return false;
}
void init2(){
sort(b+,b++n);
int tmp=unique(b+,b++n)-(b+);
for (int i=;i<=n;i++){
a[i]=lower_bound(b+,b++tmp,a[i])-b;
num[i]=;
}
}
int main(){
int t; scanf("%d",&t);
while (t--){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
init();
//离散化
block=sqrt(n);
for (int i=;i<m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i; q[i].block=q[i].l/block;
q[i].mx=queryMax(q[i].l,q[i].r);
q[i].mi=queryMin(q[i].l,q[i].r);
}
init2();
sort(q,q+m,cmp);
ll=,rr=; cnt=;
for (int i=;i<m;i++){
while (ll<q[i].l) del(ll++);
while (ll>q[i].l) add(--ll);
while (rr<q[i].r) add(++rr);
while (rr>q[i].r) del(rr--);
ans[q[i].id]=calc(q[i]);
}
for (int i=;i<m;i++)
if (ans[i]) printf("YES\n");
else printf("NO\n");
}
return ;
}
hdoj6483