GTY's gay friends

 问题描述

GTY有n个基友，出于某种恶趣味，GTY每天早上会让他的基友们排成一行，每个基友有一个特征值，表示基友有多雄壮或娘炮，你，作为GTY的助手，必须回答GTY的每个询问，GTY每次会问一个区间[l,r][l,r]是否为一个11到r-l+1r−l+1的排列。

输入描述

多组数据（约3组），每组数据的第一行有两个数n,m(1 \leq n,m \leq 100000)n,m(1≤n,m≤100000) 表示初始基友数量和询问个数，第二行包含nn个数a_i (1 \leq a_i \leq n)ai(1≤ai≤n)表示基友的特征值，接下来mm行每行两个数l,rl,r表示询问[l,r][l,r]是否为一个排列。

输出描述

对于每个询问，若它是一个排列，输出”YES”,否则输出”NO”

输入样例

8 52 1 3 4 5 2 3 11 31 12 24 81 53 21 1 11 11 2

输出样例

YESNOYESYESYESYESNO

 如果区间（l，r）是一个排列，那么必须满足两个条件

 1.区间之中的数之和等于len*（len+1）/2 自然数之和公式

 2.区间中没有重复的数

 第一个条件用前缀和进行判断，第二个条件利用pre数组进行判断，pre代表数ai上次出现的位置

如果这个区间中最大的pre都小于l，那么这个区间内就一定没有重复的数，反之则一定有重复的数

使用线段树进行求rmq，建树O（n），查询O（logn）

 

 

#include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int Max=1e6+10;LL sum[Max];int maxv[Max*4];int map[Max];int pre[Max];//标记传递void PushUp(int root){    maxv[root]=max(maxv[root<<1],maxv[root<<1|1]);}//建立线段树void Build(int l,int r,int root){    if(l==r) maxv[root]=pre[l];    else    {        int mid=(l+r)>>1;        Build(l,mid,root<<1);        Build(mid+1,r,root<<1|1);        PushUp(root);    }}//查询int Query(int ql,int qr,int l,int r,int root){    if(ql<=l&&qr>=r) return maxv[root];    int mid=(l+r)>>1;    int ans=-1;    if(ql<=mid) ans=max(ans,Query(ql,qr,l,mid,root<<1));    if(qr>mid)  ans=max(ans,Query(ql,qr,mid+1,r,root<<1|1));    return ans;}int main(){    int n,m,x,l,r;    while(~scanf("%d%d",&n,&m))    {        memset(map,-1,sizeof(map));        for(int i=1;i<=n;i++)        {            scanf("%d",&x);            i==1?sum[i]=x:sum[i]=sum[i-1]+x;            pre[i]=map[x];            map[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)            {                puts("NO");                continue;            }            if(Query(l,r,1,n,1)