题面
P6510 奶牛排队
题目描述
奶牛在熊大妈的带领下排成了一条直队。
显然，不同的奶牛身高不一定相同……
现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 A 是最矮的，最右边的 B 是最高的，且 B 高于 A 奶牛。中间如果存在奶牛，则身高不能和 A,B 奶牛相同。问这样的奶牛最多会有多少头？
从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 0,2，但不会是 $1$）。
输入格式
第一行一个正整数 N，表示奶牛的头数。
接下来 N 行，每行一个正整数，从上到下表示从左到右奶牛的身高 h_i。
输出格式
一行一个整数，表示最多奶牛数。
输入输出样例 #1
输入 #1
5
1
2
3
4
1
输出 #1
4
说明/提示
样例解释
取第 1 头到第 4 头奶牛，满足条件且为最多。
数据范围
对于全部的数据，满足 2 \le N \le 10^5，1 \le h_i <2^{31}。
TLE0分求条啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100005],l,r,st[100005][20],sb[100005][20],ans=0;
int ma(int x,int y)
{
if(a[x]>a[y]||(a[x]==a[y]&&x>y))return x;
return y;
}
int mi(int x,int y)
{
if(a[x]>a[y]||(a[x]==a[y]&&x>y))return x;
return y;
}
void init()
{
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int i=1;i<=n;i++)sb[i][0]=a[i];
int k=log2(n);
for(int j=1;j<=k;j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=ma(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int j=1;j<=k;j++)for(int i=1;i+(1<<j)-1<=n;i++)sb[i][j]=mi(sb[i][j-1],sb[i+(1<<(j-1))][j-1]);
}
// int query_max(int l,int r)
// {
// int len=r-l+1;
// int k=log2(len);
// return max(st[l][k],st[r-(1<<k)+1][k]);
// }
// int query_min(int l,int r)
// {
// int len=r-l+1;
// int k=log2(len);
// return min(sb[l][k],sb[r-(1<<k)+1][k]);
// }
int f(int l,int r)
{
if(l>=r||ans>=r-l+1)return 0;
int k=log2(r-l+1);
int h=1<<k;
int ls=mi(sb[l][k],sb[r-h+1][k]);
int rs=ma(st[l][k],st[r-h+1][k]);
if(rs-ls+1==r-l+1)
{
ans=max(ans,r-l+1);
return 0;
}
if(rs==ls)
{
f(l,l+h-1);
f(l+h,r);
}
else if(rs<ls)
{
ans=max(ans,rs-ls+1);
}
else return 0LL;
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
init();
cout<<f(1,n)<<endl;
return 0LL;
}