?pid=5172
官方题解 一个区间是排列只需要区间和为len(len+1)2(len为区间长度),且互不相同,对于第一个问题我们用前缀和解决,对于第二个问题,预处理每个数的上次出现位置,记它为pre,互不相同即区间中pre的最大值小于左端点,使用线段树或Sparse Table即可在O(n)/O(nlogn)的预处理后 O(logn)/O(1)回答每个询问.不过我们还有更简单的hash做法,对于[1..n]中的每一个数随机一个64位无符号整型作为它的hash值,一个集合的hash值为元素的异或和,预处理[1..n]的排列的hash和原序列的前缀hash异或和,就可以做到线性预处理,O(1)回答询问.
前缀和+线段树 1419MS 25360K 1368 B
maxn=1100000;;int n,m;ll c[maxn];int head[maxn],pre[maxn];void addnode(int p,int x){pre[p]=head[x];head[x]=p;}int mx[maxn<<2];void push_up(int rt){mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);}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);push_up(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 vmax=-1;if(L<=m) vmax=max(vmax,query(L,R,lson));if(m<R) vmax=max(vmax,query(L,R,rson));return vmax;}int main(){while(scanf(“%d%d”,&n,&m)!=EOF){c[0]=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;++i){scanf(“%I64d”,&c[i]);addnode(i,c[i]);c[i]+=c[i-1];}build(1,n,1);int l,r;while(m–){scanf(“%d%d”,&l,&r);ll ans=c[r]-c[l-1];ll len=r-l+1;if(ans==len*(len+1)/2&&query(l,r,1,n,1)<l) printf(“YES\n”);else printf(“NO\n”);}}return 0;}
，人的不幸缘于欲望，所以知足者长乐。
