题意：判断区间[l,r]内的数字是否符合1~len（r-l+1）的一个全排列。
分析：pos[i]记录数字i出现的最大位置，pre[i]记录在位置i的数字a[i]出现的最大位置，然后每次判断区间内数字全不同且区间和为（len+1）*len就是一个全排列了。
至于求区间内相同数字出现的最大位置，用线段树维护区间最值即可。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 100000000 #define inf 0x3f3f3f3f #define eps 1e-6 #define N 1000010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PII pair<int,int> using namespace std; int pos[N],pre[N],a[N],mx[N<<2]; LL sum[N]; void Pushup(int rt) { int ls=rt<<1,rs=ls|1; mx[rt]=max(mx[ls],mx[rs]); } void build(int l,int r,int rt) { if(l==r) { mx[rt]=pre[l]; return; } int m=(l+r)>>1; build(lson); build(rson); Pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return mx[rt]; int m=(l+r)>>1; int res=0; if(L<=m)res=max(res,query(L,R,lson)); if(m<R)res=max(res,query(L,R,rson)); return res; } int main() { int n,m,x,l,r; while(scanf("%d%d",&n,&m)>0) { FILL(pos,0); for(int i=1;i<=n;i++) { scanf("%d",&x); sum[i]=sum[i-1]+x; pre[i]=pos[x]; pos[x]=i; } build(1,n,1); while(m--) { scanf("%d%d",&l,&r); LL len=r-l+1; if(sum[r]-sum[l-1]==len*(len+1)/2&&query(l,r,1,n,1)<l) puts("YES"); else puts("NO"); } } }