P1823 [COI2007] Patrik 音乐会的等待
题解：维护一个单调不递增的栈
首先说明一下：由于一个人左边可以看到一些人，右边可以看到一些人，可以我们仅从一边考虑，对于一个人，我们考虑它的左边能看到多少个。两边都考虑会导致重复计算。
tot是当前栈元素的个数
对于新加入单调栈的一个元素，我们分三种情况讨论：
1、新元素比栈顶小：直接加入栈，ans加1
2、新元素与栈顶元素相等：ans加栈中与新元素相等的数的个数，同时若tot不为0，ans还应再加1
3、新元素比栈顶大：不断弹出元素，每弹一个ans加一，一直弹到新元素<=栈顶元素，再同情况2进行判断即可。
我们想想这个为什么是对的，两个人可以相互看见只有它们间没有人比他们高，对于加入栈的新元素，由于栈是不递增的。如果该元素比栈顶小，我们是从左边考虑，那么该元素仅能看到它的左边的第一个元素，也即是栈顶，栈顶左边的人都比栈顶高，这个新元素看不见。
如果新元素和栈顶相等，那么我们就去寻找栈里面有多少和该元素相等的数，找到一个答案就加1，因为相等的元素能够相互看见，对答案的贡献就是1。如果找到最后，tot不为0，那么答案再加1，因为它俩也可以相互看见 比如说
栈内有5 2 2，再加入一个2，答案增加3，因为新加入的2 和 5也可以相互看见
如果新元素比栈顶大，那么就不断弹出元素，直到新元素<=栈顶元素，弹出一个，答案加1，因为弹出的元素比新元素小，因此新元素可以看见它的左边比它小的元素，有些人可能疑惑元素弹出以后对后面的计数有没有什么影响呢，答案是没有。
新元素的身高比弹出的元素的身高大，也就是这些弹出的元素与新元素后面的元素之间不满足能相互看见，新元素的后面任何一个元素都不会看见这些弹出的元素。 到新元素<=栈顶元素时，再考虑新元素是否等于栈顶，这时就回到了情况2
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+5; int s[maxn],tot,n,tmp,ans; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>tmp; if(tmp<s[tot]) ans++,s[++tot]=tmp; else //这里情况2和3可以放在一起处理 { int t=0; while(tot&&tmp>s[tot]) ans++,tot--; while(tot&&tmp==s[tot]) ans++,tot--,t++; if(tot) ans++; tot+=t;//恢复栈中相同的元素 s[++tot]=tmp; } } cout<<ans; return 0; }
这个代码交上去以后最后三个测试点超时了，可以考虑优化，对于元素相同的情况，我们重复的计算栈内相同元素的个数，所以我们可以用一个数组来记录这个相同元素的个数。
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int maxn=5e5+5; int s[maxn],w[maxn],tot,n,tmp; long long ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&tmp); if(tmp<s[tot]) ans+=1LL,s[++tot]=tmp,w[tot]=1; else { int width=0; while(tot&&tmp>s[tot]) ans+=1LL*w[tot],tot--; while(tot&&tmp==s[tot]) ans+=1LL*w[tot],width+=w[tot],tot--; if(tot) ans+=1LL; s[++tot]=tmp; w[tot]=width+1; } } printf("%lld",ans); return 0; }
还有就是答案一定要用long long，不然最后三个会WA