程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5172 RMQ

hdu 5172 RMQ

編輯:關於C++

題意: 給出一個數組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<
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved