【题目大意】
求全部数对(i,j)满足随意a[k]<=a[i]且a[k]<=a[j]。
形象地说,就是有一群人站成一列。每一个人有一定的身高,然后问有多少对人能够互相看得到。
把数对(i,j)简单地称之为看得到的数对。
【解析】单调栈
先借用一下曾经做的题:[Vijos]1926 紫色的手链。求随意区间最大值异或次大值的最大值。
回想一下单调栈,就是存储从高到低递减的单调数据的栈。
求全部数对(i,j)满足随意a[k]<=a[i]且a[k]<=a[j]。
形象地说,就是有一群人站成一列。每一个人有一定的身高,然后问有多少对人能够互相看得到。
把数对(i,j)简单地称之为看得到的数对。
【解析】单调栈
先借用一下曾经做的题:[Vijos]1926 紫色的手链。求随意区间最大值异或次大值的最大值。
回想一下单调栈,就是存储从高到低递减的单调数据的栈。
借用曾经的做法,求出来的东西相对于全部看得到的数对,对于全部a[i]相等的看得见的数对,仅仅算了一次。
于是事实上每次高过别人的时候操作仅仅要加上s(a[i]),第一次比别人矮的时候加上1而不是s(a[i])。
把栈内的东西给扩充,不仅存元素。还存个数,这样就攻克了。
单调栈代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N=500001;
struct Stack
{
int w,c;
}stk[N];
int size;
int n,w[N],cnt;
inline int read(void)
{
int s=0,f=1; char c=getchar();
for (;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;
for (;'0'<=c&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
return s*f;
}
int main(void)
{
n=read();
for (int i=1;i<=n;i++) w[i]=read();
for (int i=1;i<=n;i++)
{
for (;size&&stk[size].w<w[i];size--)
{
cnt+=stk[size].c;
stk[size].w=stk[size].c=0;
}
if (size&&stk[size].w==w[i])
{
cnt+=stk[size].c;
stk[size].c++;
if (size-1) cnt++;
}
else
{
if (size) cnt++;
stk[++size].w=w[i];
stk[size].c=1;
}
}
printf("%d\n",cnt);
return 0;
}