HDU 5875 Function(ST表+二分)

forever97 posted @ 2016年9月12日 14:39 in 数据结构-ST表 with tags 二分 ST表 , 397 阅读

 

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5875

 

【题目大意】

     给出一个数列,同时给出多个询问,每个询问给出一个区间,要求算出区间从左边开始不断对下一个数取模之后的结果。

 

【题解】

   考虑取模的递减性质,最多取模logn次,因此如何快速找出下一个取模的位置是解决这道题的关键,首先利用ST表预处理区间最小值,之后我们每次二分取模起点到终点这个区段,每次优先查询左区间(类似于线段树上的路径查询),这样子就能logn找到取模的位置,然后直接取模就好。

 

【代码】

#include <cstdio>  
#include <cstring>  
#include <algorithm> 
using namespace std;  
const int N=200010;    
int d[N][30],f[N][30],a[N],lg2[N];   
int T,n,m,l,r,q;  
void rmq_init(int n){  
    for(int i=2;i<=n;i++)lg2[i]=lg2[i/2]+1;
    for(int i=1;i<=n;i++)scanf("%d",&f[i][0]);
    for(int j=1;(1<<j)<=n;j++){  
        for(int i=1;i+(1<<j)-1<=n;i++){  
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }  
    }  
} 
int rmq_min(int l,int r){int k=lg2[r-l+1];return min(f[l][k],f[r-(1<<k)+1][k]);}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        rmq_init(n);
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&l,&r);
            if(l==r){
            	  printf("%d\n",f[l][0]);
            	  continue;
            }
            int flag=1,ans=f[l][0],L=l+1,R=r;
            while(flag){
                while(L<R){
                    int mid=(L+R)>>1;
                    if(rmq_min(L,mid)<=ans)R=mid;
                    else{
                        if(rmq_min(mid+1,R)<=ans)L=mid+1;
                        else{flag=0;break;}
                    }
                }if(flag)ans=ans%f[L][0];
                if(L==r)break; 
				        L++; R=r;
            }printf("%d\n",ans);
        }
    }return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter