HDu 5172 GTY's gay friends(区間最値)

GTYにはn人の友人が一列に並んでいて、それぞれの友人に1つの値a[i](1<=a[i]<=n)があり、mの質問があり、区間[L,R]内の数値が1からR-L+1までの全配列であるかどうかを尋ねる.
 
まず、区間[L,R]内の和が1~R-L+1の全配列の和に等しいか否かを判断し、プレフィックスとして実現する.等しい場合、数値が等しい可能性があるため、区間内の要素を判定する必要があります.
どうやって重さを判断しますか?前回出現した位置をpre[i]で記録し、区間[L,R]内の各数についてpreがLよりも小さいか否かを判断する.ここでセグメントツリーで区間内preの最大値をクエリーし、Lより小さいかどうかを確認します.
 
 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1000005
#define lson i<<1,l,m
#define rson i<<1|1,m+1,r
int Max[maxn<<2],a[maxn],sum[maxn],last[maxn],pre[maxn];
void PushUp(int i)
{
    Max[i]=max(Max[i<<1],Max[i<<1|1]);
}
void build(int i,int l,int r)
{
    if(l==r)
    {
        Max[i]=pre[l];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(i);
}
int query(int L,int R,int i,int l,int r)
{
    if(L<=l&&r<=R) return Max[i];
    int m=(l+r)>>1;
    int ans=0;
    if(L<=m) ans=max(ans,query(L,R,lson));
    if(R>m) ans=max(ans,query(L,R,rson));
    return ans;
}
int main()
{
    int n,m,i;
    while(~scanf("%d%d",&n,&m))
    {
        sum[0]=0;
        memset(last,0,sizeof(last));
        for(i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            pre[i]=last[a[i]];
            last[a[i]]=i;
            sum[i]=sum[i-1]+a[i];
        }
        build(1,1,n);
        while(m--)
        {
            int L,R;
            scanf("%d%d",&L,&R);
            if(sum[R]-sum[L-1]==(R-L+2)*(R-L+1)/2&&query(L,R,1,1,n)<L) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}