题目地址：HDU 5172
比赛的时候用一个维护了区间和，区间积，区间最值的线段树水过去了。。赛后数据改回10^6后，就TLE了。。
正解是区间和用前缀和维护就可以。然后维护一个该位上的数上一个出现额位置，那么每次查询，如果每个数的上一个出现的位置都小于l的话，那么就说明没有重复的，如果区间和符合全排列的和，那么就说明肯定是一个全排列了。
代码如下：#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;#define root 1, n, 1#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1int a[1000002], pre[1000002], pos[1000002];int Max[4000000];LL sum[1000002];void PushUp(int rt){Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);}void build(int l, int r, int rt){if(l==r){Max[rt]=pre[l];return ;}int mid=l+r>>1;build(lson);build(rson);PushUp(rt);}int Query(int ll, int rr, int l, int r, int rt){if(ll<=l&&rr>=r){return Max[rt];}int mid=l+r>>1, ans=-1;if(ll<=mid) ans=max(ans,Query(ll,rr,lson));if(rr>mid) ans=max(ans,Query(ll,rr,rson));return ans;}int main(){int n, m, i, j, x, l, r, ans;while(scanf("%d%d",&n,&m)!=EOF){memset(pos,-1,sizeof(pos));sum[0]=0;for(i=1;i<=n;i++){scanf("%d",&x);pre[i]=pos[x];pos[x]=i;sum[i]=sum[i-1]+x;}build(root);while(m–){scanf("%d%d",&l,&r);if(sum[r]-sum[l-1]!=(LL)(r-l+1)*(r-l+2)/2){puts("NO");continue ;}ans=Query(l,r,root);if(ans<l) puts("YES");else puts("NO");}}return 0;}
，一个能从别人的观念来看事情，能了解别人心灵活动的人，永远不必为自己的前途担心。
