Bad Hair Day [POJ3250] [单调栈 或 二分+RMQ]

题意
Farmer John的奶牛在风中凌乱了它们的发型……
每只奶牛都有一个身高hi(1 ≤ hi ≤ 1,000,000,000),现在在这里有一排全部面向右方的奶牛,一共有N只(1 ≤ N ≤ 80,000)。对于奶牛i来说,如果奶牛i+1,i+2,……,N这些奶牛的身高严格小于奶牛i,则奶牛i可以看到它们凌乱的发型。

输入
第一行 奶牛数量N
第二到 N+1行:第i+1行输入奶牛i的身高

输出
第一行:一个整数即c1到cN的和

样例输入
6
10
3
7
4
12
2

样例输出
5

分析
方法一
对于i,我们知道,令j∈[i+1,n],s=max(hi+1....hj)是具有单调性的(感性理解,j越大数字越多,同时j更小时的数也没有丢掉),所以如果s<=h[i]时,就可以继续向右扩张。使用二分查找,RMQ查询。RMQ可以使用ST达到O(1)的查询。

方法二
一头牛看到多少牛不好做,但可以被多少牛看到可解。只要在左边形成一个递减的数列,且最后一个大于当前的牛即可,数列大小即为当前牛的答案。可以用单调栈维护。

代码(法一)

 #include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register ll
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll unsigned long long
#define inf (1<<29)
#define maxn 80005
#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid ((t[pos].l+t[pos].r)>>1)
using namespace std;
ll n,ANS;
ll num[maxn],mx[maxn][];
inline ll read()
{
ll x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
/*
void build(ll pos,ll l,ll r)
{
t[pos].l=l,t[pos].r=r;
if(l==r) {t[pos].mx=num[l];return;}
build(ls,l,mid);build(rs,mid+1,r);
t[pos].mx=max(t[ls].mx,t[rs].mx);
} ll query(ll pos,ll l,ll r)
{
if(l<=t[pos].l&&t[pos].r<=r) return t[pos].mx;
ll ans=0;
if(l<=mid) ans=query(ls,l,r);
if(r>mid) ans=max(ans,query(rs,l,r));
return ans;
}
*/ void ST()
{
rep(i,,n) mx[i][]=num[i];
rep(j,,)
rep(i,,n)
if(i+(<<j)-<=n)
mx[i][j]=max(mx[i][j-],mx[i+(<<(j-))][j-]);
} int query(int l,int r)
{
int len=log(r-l+)/log();
return max(mx[l][len],mx[r-(<<len)+][len]);
} int main()
{
n=read();
rep(i,,n) num[i]=read();
//build(1,1,n);
ST();
rep(i,,n)
{
RG l=i+,r=n,ans=i,md;
while(l<=r)
{
md=(l+r)>>;
if(query(i+,md)<num[i]) ans=md,l=md+;
else r=md-;
}
ANS+=ans-i;
}
cout<<ANS;
return ;
}
上一篇:elasticsearch配置详解


下一篇:51nod_1677:treecnt