HDU 4123（两种方法-RMQ，单调队列）-白红宇

HDU 4123（两种方法-RMQ，单调队列）

阅读量：5086 次

发布时间：2019-06-13

本文共 2366 字，大约阅读时间需要 7 分钟。

题意：50000个点的树，每个点有一个人，每个人会跑到离自己初始点距离最远的点上，这个距离为distance[i]。给你500个查询，对于每个查询Q，找一段连续编号的人，比如[left,right]，满足 max( distance[i] i∈[left,right] ) – min( distance[i] i∈[left,right] ) ≤ Q，并且使得length=right-left+1要最大，求这个最大的length

法一：关键是O(1)的RMQ。。。。

分析：求distance[i]数组（代码中的d），可以用搜边的方法来解决，然后线性维护一个队列，使得队列中的最大值 – 最小值 ≤ Q，之后，会有一个新的distance[i]插到队列的头部，这样会打破“最大值 – 最小值 ≤ Q”的规则，此时要从队列末尾弹出元素，直到重新满足规则。很明显，维护队列的时候要不断查询某一区间的最大值和最小值，这个可以用RMQ来解决。对于每个distance[i]，最多进队列和出队列一次，所以总复杂度为O(nlogn+mn)，这貌似有点大啊。

此题还必须有一个极端的优化（当时赛后才想到这个，悲剧。）：由于维护队列的时候要不断查询某一区间的最大值和最小值，而log函数慢的一比，所以，要预处理log数组。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #define tree int o,int l,int r#define lson o<<1,l,mid#define rson o<<1|1,mid+1,r#define lo o<<1#define ro o<<1|1#define pb push_back#define mp make_pair#define ULL unsigned long long#define LL long long#define inf 0x7fffffff#define eps 1e-7#define N 50009using namespace std;int m,n,T,t,x,y,z;vector
                  
                   
                     >g[N];int f[N],s[N],sub[N];int minv[N][17],maxv[N][17];int lg[N];void init(){ for (int i=0; i<=n; ++i ) g[i].clear();}void dfs1(int u,int fa){ f[u]=s[u]=0; for(int i=0; i
                    
                     q) { j++; int xiao=rmqx(j,i);//O(1) int da=rmqd(j,i); while(da-xiao>q)//j==i时会停 { j++; xiao=rmqx(j,i); da=rmqd(j,i); } d=da;/// x=xiao; } ans=max(ans,i-j+1); } printf("%d\n",ans); } } return 0;}

View Code

法二：两个单调队列（一个维护最大，一个维护最小）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  #define tree int o,int l,int r#define lson o<<1,l,mid#define rson o<<1|1,mid+1,r#define lo o<<1#define ro o<<1|1#define pb push_back#define mp make_pair#define ULL unsigned long long#define LL long long#define inf 0x7fffffff#define eps 1e-7#define N 50009using namespace std;int m,n,T,t,x,y,z;vector
                  
                   
                     >g[N];int f[N],s[N],sub[N];int qs[N],qj[N];void init(){ for (int i=0; i<=n; ++i ) g[i].clear();}void dfs1(int u,int fa){ f[u]=s[u]=0; for(int i=0; i
                    
                     =f[i])sr--; while(jl
                     
                      <=f[i])jr--; qs[sr++]=i; qj[jr++]=i; while(f[qj[jl]]-f[qs[sl]]>q)//对于右区间i，找到左区间！ { if(qj[jl]

View Code

转载于:https://www.cnblogs.com/sbaof/p/3384782.html

你可能感兴趣的文章