浙江理工大学新生赛 B 巴比伦花园（RMQ）(二分)

太过爱你忘了你带给我的痛 2022-07-14 08:39 95阅读 0赞

题目链接：[点击打开链接][Link 1]

首先，这题居然是zstu新生题....强!

这题一眼看下去，线段树肯定能写。不过这题还有另外的解法。就是RMQ+二分。

先预处理一下，预处理每个点最能够到达的最远距离，然后RMQ存一下区间内点能到达的最远距离，然后在查询的时候，二分查询(L,R)区间能够到达的超过或等于R的第一个点的位置，然后L到这个位置-1这段区间，RMQ查询其最远距离，然后这两者取max就是答案了。完全可以RMQ离线查询啊。 因为要最长，所以如果F(i)为阶梯的起点，那么把F(i)加工成高度1时肯定是最优的。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int maxn=100010;
    ll n,k,q;
    ll dp[maxn],a[maxn][20];
    void rmq()
    {
        ll i,j;
        for(j=1; j<=n; j++)
            a[j][0]=dp[j]-j+1;
        int k=floor(log((double)n)/log(2.0)); 
        for(i=1; i<=k; i++)
        for(j=1;j<=n;j++)
            //for(j=n;j>=1;--j)
                if(j+(1<<i)-1<=n)
                    a[j][i]=max(a[j][i-1],a[j+(1<<(i-1))][i-1]);
    }
    int RMQ(int x,int max_end)
    {
    	ll temp=(ll)(log(max_end-x)/log(2));
        return max(a[x][temp],a[max_end-(1<<temp)][temp]);  
    }
    int main()
    {
        ll t;
        scanf("%lld",&t);
        while(t--)
        {
            ll i;
            scanf("%lld%lld%lld",&n,&k,&q);
            for(i=1; i<=n; i++)  scanf("%lld",&a[i][0]);
            
            ll tt=1,p=1,x,y;
            for(i=2; i<=n; i++,p+=k)  //点 i 为阶梯的起点，所能加工出的最长阶梯的最右端的位置
            {
                while(a[i][0]<p+k)
                {
    				dp[tt++]=i-1;
    				p-=k;
    			} 
                    
            }
            for(i=tt; i<=n; i++) dp[i]=n;
            rmq();
            while(q--)
            {
                scanf("%lld%lld",&x,&y);
                ll max_end=upper_bound(dp+x,dp+y,y-1)-dp;  //max_end表示能够到达y的点的第一个下标
                ll dis=0;
                if(x<max_end)
                {
                    dis=RMQ(x,max_end);//dis表示的是没有能到达y的点里面的最长距离
                }
                printf("%lld\n",max(dis,y-max_end+1));
            }
        }
        return 0;
    }

[Link 1]: http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4239