526互联

【rmq】洛谷P7333

发布时间 2023-04-14 13:28:20作者: and3434

题目：P7333 [JRKSJ R1] JFCA - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析：用rmq处理出各个区间长度的最大值，然后在二分区间长度找到答案

（最开始想的是开长度为n的数组，对位置i的数，分别找1-（i-1）和（i+1）-n中的离i最近满足条件的位置，然后更新结果，但一直wa，还没找到问题，存疑吧）

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int,pair<int,ll>> pil;
typedef unsigned long long ULL;
const ll mod = 1e9+7;
const int M=1e5+5;
const int N = 1e5+ 5;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
int n,a[N*3],b[N],f[N];
int dp[N*3][20];
void init()
{
    for(int i=1;i<=3*n;i++) dp[i][0]=a[i];
    for(int j=1;(1<<j)<=3*n;j++)
    {
        for(int i=1;i+(1<<j)-1<=3*n;i++)
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r)
{
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
bool check(int x,int len,int v)
{
    return max(query(x-len,x-1),query(x+1,x+len))>=v;
}
int work(int x,int v)
{
    int l=1,r=n-1,ans=-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(x,mid,v))
        {
            ans=mid;
            r=mid;
        }
        else l=mid+1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
        a[i+n*2]=a[i];
    }
    for(int i=1;i<=n;i++) cin>>b[i];
    init();
    for(int i=1;i<=n;i++)
    {
        f[i]=work(i+n,b[i]);
    }
    for(int i=1;i<=n;i++) cout<<f[i]<<" ";
}

一直wa的代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int,pair<int,ll>> pil;
typedef unsigned long long ULL;
const ll mod = 1e9+7;
const int M=1e5+5;
const int N = 1e5+ 5;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
int n,a[N],b[N],f[N];
int dp[N][20];
// int n,a[N*3],b[N],f[N];
// int dp[N*3][20];
// void init()
// {
//     for(int i=1;i<=3*n;i++) dp[i][0]=a[i];
//     for(int j=1;(1<<j)<=3*n;j++)
//     {
//         for(int i=1;i+(1<<j)-1<=3*n;i++)
//         {
//             dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
//         }
//     }
// }
void init()
{
    for(int i=1;i<=n;i++) dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r)
{
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
bool check(int x,int len,int v)
{
    return max(query(x-len,x-1),query(x+1,x+len))>=v;
}
int work(int x,int v)
{
    int l=1,r=x-1,ans1=-1,ans2=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(query(x-mid,x-1)>=v){
            ans1=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    ans1=min(ans1,n-ans1);
    l=1,r=n-x;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(query(x+1,x+mid)>=v)
        {
            ans2=mid;
            r=mid-1;

        }
        else l=mid+1;
    }
    ans2=min(ans2,n-ans2);
    if(ans1!=-1&&ans2!=-1) return min(ans1,ans2);
    else return max(ans1,ans2);
    // int l=1,r=n-1,ans=-1;
    // while(l<r)
    // {
    //     int mid=(l+r)/2;
    //     if(check(x,mid,v))
    //     {
    //         ans=mid;
    //         r=mid;
    //     }
    //     else l=mid+1;
    // }
    // return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        // a[i+n]=a[i];
        // a[i+n*2]=a[i];
    }
    for(int i=1;i<=n;i++) cin>>b[i];
    init();
    for(int i=1;i<=n;i++)
    {
        f[i]=work(i,b[i]);
    }
    for(int i=1;i<=n;i++) cout<<f[i]<<" ";
}