洛谷P1823 [COI2007] Patrik 音乐会的等待(单调栈+二分查找)

标签：题解

阅读体验：

这个题不是很难，但是没有转过来还是难想的

可以先去做一下这个题：

蒟蒻发现很多题解都是错的呀，复杂度比较玄学吧

介绍一种标准的\(O(nlogn)\)的方法

单调栈

我们对于一个人作为方案中右边那个人时我们算答案（为了不算重）

有哪些人我们看不到呢，无非是被它右边的人挡住了是吧

那么从左往右维护一个单调递减的单调栈，单调栈中的人不会出现被挡住的情况（只有\(i\)看不到的情况后面会讲）

自己想一下这里很简单

二分查找

考虑肯定只有单调栈中的人会被\(i\)算入答案是吧

并且很容易发现一定是个连续的区间\([x,i-1]\)（这不废话吗）

那么我们在单调栈中二分这个区间的左端点，显然左端点就是\(i\)左边第一个比\(i\)高的数

这不就是上面那个的题目了吗

计入答案的就是区间长度啦

代码极其简单。。。

#include
    
     #define il inline#define rg register#define ldb double#define lst long long#define rgt register int#define N 500050using namespace std;const int Inf=1e9;il int read(){    int s=0,m=0;char ch=getchar();    while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}    while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();    return m?-s:s;}int n,top;lst Ans;int H[N],stk[N];il void Calc(rgt x){    rgt le=0,ri=top,mid,ret=0;    while(le<=ri)    {        mid=(le+ri)>>1;        if(H[stk[mid]]>x)ret=mid,le=mid+1;        else ri=mid-1;    }    if(!ret)Ans+=top;    else Ans+=top-ret+1;}int main(){    n=read();    for(rgt i=1;i<=n;++i)H[i]=read();    for(rgt i=1;i<=n;++i)    {        Calc(H[i]);        while(top>0&&H[i]>H[stk[top]])--top;        stk[++top]=i;    }return printf("%lld\n",Ans),0;}