传送：

题意：有长度为$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预处理最值，然后离散化，莫队求区间内值种类的个数。

代码：

1 #include
      
        2 using namespace std; 3 const int maxn=1e5+10; 4 struct node{ 5     int l,r,id,block,mx,mi; 6 }q[maxn]; 7 int a[maxn],b[maxn],maxPoint[maxn][30],minPoint[maxn][30],num[maxn]; 8 bool ans[maxn]; 9 int cnt=0,n,m,block,ll,rr;10 bool cmp(node p,node q){11     return p.block
       
        << (j - 1));30             minPoint[i][j] = min(minPoint[i][j - 1], minPoint[i + p][j - 1]);31             maxPoint[i][j] = max(maxPoint[i][j - 1], maxPoint[i + p][j - 1]);32         }33     }34 }35 int queryMin(int l, int r){36     int k = log2((double)(r - l + 1));37     return min(minPoint[l][k], minPoint[r - (1 << k) + 1][k]);38 }39 40 int queryMax(int l, int r){41     int k = log2((double)(r - l + 1));42     return max(maxPoint[l][k], maxPoint[r - (1 << k) + 1][k]);43 }44 bool calc(node tmp){45     if (tmp.mx-tmp.mi+1==cnt) return true;46     return false;47 }48 void init2(){49     sort(b+1,b+1+n);50     int tmp=unique(b+1,b+1+n)-(b+1);51     for (int i=1;i<=n;i++){52         a[i]=lower_bound(b+1,b+1+tmp,a[i])-b;53         num[i]=0;54     }55 } 56 int main(){57     int t; scanf("%d",&t);58     while (t--){59         scanf("%d%d",&n,&m);60         for (int i=1;i<=n;i++){61             scanf("%d",&a[i]);62             b[i]=a[i];63         }64         init();65         //离散化66         block=sqrt(n);67         for (int i=0;i
        
         q[i].l) add(--ll);79             while (rr
         
          q[i].r) del(rr--); 81             ans[q[i].id]=calc(q[i]);82         }83         for (int i=0;i