hdu 5172 RMQ

題意： 給出一個數組a[n]（1<=a[i]<=n）,可能會有重復，然後m組詢問
每次詢問兩個數：l,r
在區間[l,r]內是否構成一個1,2,..,r-l+1的排列；
分析： 要想構成1,2….r-l+1的排列，首先要滿足區間內的和sum=(1+len)*len/2
然後區間內的每個數都不一樣即可，然後再開一個數組記錄每個數前一次出現的位置pre，如果[l,r]內pre的最大值都小於l,那就行了；
基於線段樹的rmq

/*
    基於線段樹(完美線段樹)的RMQ問題~！
*/

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=1e6+100;
const int INF=-999999;
typedef long long ll;
ll sum[N];

int vis[N];
int pre[N];

int dat[2*N],nn; //線段樹

void init(int n_)  //初始化 O（n）
{
     nn=1;
     while(nn0)
   {
     k=(k-1)/2;
     dat[k]=max(dat[k*2+1],dat[k*2+2]);
   }
}

int query(int a,int b,int k,int l,int r)
{
    if(b<=l || r<=a)return INF; //區間沒有交集
    if(a<=l&&r<=b)return dat[k];
    else
    {
      int v1=query(a,b,k*2+1,l,(l+r)/2);
      int v2=query(a,b,k*2+2,(l+r)/2,r);
      return max(v1,v2);
    }
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
       init(n);
       memset(vis,-1,sizeof(vis));
       for(int i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            sum[i]=sum[i-1]+a;
            if(vis[a]==-1)
            {
                pre[i]=-1;
                vis[a]=i;
            }
            else
            {
                pre[i]=vis[a];
                vis[a]=i;
            }
        }

       for(int i=1;i<=n;i++)
       {
          update(i-1,pre[i]);
       }

       while(m--)
       {
         int l,r;
         scanf("%d%d",&l,&r);
         ll tmp1=(r-l+2)*(r-l+1)/2;
         if(tmp1==(sum[r]-sum[l-1]))
         {
            //cout<