【题目大意】求所有数对(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;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
发现一种久违的感动。
