欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

51nod 1272【二分+RMQ】

程序员文章站 2022-05-11 15:42:11
...

思路:
这题不能说是长见识,倒是第一次写这么富有套路的题,倒着来,二分区间嘛,这个很简单啊,二分的条件查询一个当前区间的最小值是不是比那个特定的值小,一步步缩小,这就是二分嘛,然后查询用线段树的RMQ写法搞,logn。
二分的模型是0000000111111111这个,窝还是照着自己的两篇小博客写的,一个是线段树,一个是二分。。。然后过的///希望熟能生巧吧

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;

const int N=5e4+10;

struct asd{
    int left;
    int right;
    int w;
};
asd q[N*4];
int a[N];

void Build(int num,int L,int R)
{
    q[num].left=L;
    q[num].right=R;
    if(L==R)
    {
        q[num].w=a[L];
        return;
    }
    Build(2*num,L,(L+R)/2);
    Build(2*num+1,(L+R)/2+1,R);
    q[num].w=min(q[2*num].w,q[2*num+1].w);
}

int Query(int num,int s,int t)
{
    if(q[num].left>=s&&q[num].right<=t)
        return q[num].w;
    if(q[num].left==q[num].right)
        return q[num].w;
    int mid=(q[num].left+q[num].right)/2;
    int ans=1e9;
    if(mid>=t)
        ans=min(ans,Query(2*num,s,t));
    else if(mid<s)
        ans=min(ans,Query(2*num+1,s,t));
    else
    {
        ans=min(ans,Query(2*num,s,(s+t)/2));
        ans=min(ans,Query(2*num+1,(s+t)/2+1,t));
    }
    return ans;
}

int get_mina(int s,int t,int num)
{
    if(s<=q[num].left&&t>=q[num].right)
        return q[num].w;
    if(s>q[num].right||t<q[num].left)
        return 1000000000;
    int a,b;
    a=get_mina(s,t,2*num);
    b=get_mina(s,t,2*num+1);
    return min(a,b);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    Build(1,1,n);
//二分 0000001111111111
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int left=1,right=i;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(get_mina(left,mid,1)<=a[i])
                right=mid;
            else
                left=mid+1;
        }
        ans=max(ans,i-left);
    }
    printf("%d\n",ans);
    return 0;
}