原题大意：原题链接
给定元素无重复数组，查询给定区间内元素是否连续
解体思路：由于无重复元素，所以如果区间内元素连续，则该区间内的最大值和最小值之差应该等于区间长度(r-l)
解法一：线段树(模板题)
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+;
int va,curmi,curma;
int mi[*maxn],ma[*maxn];
void Build(int p,int l,int r)
{
if(l==r){
scanf("%d",&va);
mi[p]=ma[p]=va;
return;
}
int mid=(l+r)/;
Build(*p,l,mid);
Build(*p+,mid+,r);
mi[p]=min(mi[*p],mi[*p+]);
ma[p]=max(ma[*p],ma[*p+]);
}
void Query(int p,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr){
curmi=min(curmi,mi[p]);
curma=max(curma,ma[p]);
return;
}
int mid=(l+r)/;
if(ll<=mid)
Query(*p,l,mid,ll,rr);
if(rr>mid)
Query(*p+,mid+,r,ll,rr);
}
int main()
{
int n,m,q,l,r;
scanf("%d",&n);
Build(,,n);
scanf("%d",&q);
while(q--){
scanf("%d%d",&l,&r);
curmi=inf,curma=-inf;
Query(,,n,l,r);
if(curma-curmi==r-l) puts("YES");
else puts("NO");
}
}
解法二：RMQ(模板题)
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+;
int n,q,l,r,va,curmi,curma;
int mi[maxn][],ma[maxn][]; void Rmq_Precede()
{
for(int j=;(<<j)<=n;j++){//长度最长为log2n
for(int i=;i+(<<j)-<=n;i++){//最后一个元素编号为i+(1<<j)-1
mi[i][j]=min(mi[i][j-],mi[i+(<<(j-))][j-]);
ma[i][j]=max(ma[i][j-],ma[i+(<<(j-))][j-]);
}
}
}
void Rmq_Query(int l,int r)
{
int k=log2(r-l+);
curmi=min(mi[l][k],mi[r-(<<k)+][k]);
curma=max(ma[l][k],ma[r-(<<k)+][k]);
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&va);
mi[i][]=ma[i][]=va;
}
Rmq_Precede();
scanf("%d",&q);
while(q--){
scanf("%d%d",&l,&r);
Rmq_Query(l,r);
if(curma-curmi==r-l) puts("YES");
else puts("NO");
}
}