题解 P1823 【[COI2007] Patrik 音乐会的等待】

· · 题解

都是单调栈，都是单调栈！就没有人想到用堆这种傻傻的数据结构去做吗？？？qwq

可能思想和单调栈相近吧。。。反正我不知道单调栈是什么东西

具体实现方法：小根堆 + 链表

（ Warning：以下内容将会把“数”,“身高”,“人”混为一谈，前自行理解）

对于两个人：他们可以看到彼此，当且仅当中间的人没有比他们高的人。这也就是说，我们从这个人开始往右，往左寻找，如果有比他大的，说明它们之间一定能看到，组数+1

也就是说，我们可以依次枚举每个人，如果他左边有人比他高，组数+1，如果右边有人比他高，组数+1，及时退出即可

但是，这显然不够，这样就变O(n^2)了，这并不是我们想要的。也就是说，对于一个数，我们需要快速检测它的右边或左边是否有比它大的数！

这很好办！我们可以用一个链表和一个小根堆来解决它：由于我们从小的数开始取，因此我们之前检索过的数，都比当前检索的数小，所以检索完一个数后，我们就把他从链表中删去即可，如果他左边或右边没有数了，组数就不再+1，这个实现，思路都应该较为简单，不再赘述。

没问题，但是这样就连样例也过不了

这是因为：我们没有考虑到两个数相等的情况，如：

4 2 1 2 5

我们会分别检索a[2]，a[3]，而组数+4而不是+5。其实a[2],a[5]可以看到彼此，但我们并没有把它们统计起来，因为我们默认2的左边或右边至多有一个人可以看到他，如果这样，数列中就不会有相等的数了

其实这个问题也很容易就能解决：两个身高相等的人能看到彼此，说明他们在目前的链表中是相邻的，如果不相邻，就意味这他们中间有比他们高的人，所以才看不到。

这就好了，每次我们取数时，在取最小的数的前提下，把相邻的数全部取完即可，若取了n个，容易知道，产生组数就是(n-1) * n/2 。当然，如果这些数的左边不为空，说明这些人的左边一定有比他们高的，这样又会产生n组能够互相看到的人了，右边也是一样的

这样就可以写了：

#include <bits/stdc++.h>//我不喜欢压行

using namespace std;

priority_queue < pair < int , int >  > q;
int n[550000],i,j,m,xx,hc;
long long ans;
int beginn;

struct list{
    int l,r;
}a[550000];

int main(){
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&n[i]);
        q.push(make_pair(-n[i],-i));//这里把下标取反，就能保证身高一样时，下标是从小到大开始取的，对于链表，就能保证他是从左到右取而非从右到左取
        a[i].l=i-1;//链表初始化
        a[i].r=i+1;
    }
    while(!q.empty())
    {
        xx=-q.top().second;

        q.pop();
        a[a[xx].r].l=a[xx].l;//删数
        a[a[xx].l].r=a[xx].r;//删数

        if(n[xx]==n[a[xx].r])//一次性取完所有相同的数
        {
            beginn=xx;
            hc=0;
            while(n[xx]==n[a[xx].r]&&(!q.empty()))
            {
                hc++;
                ans+=hc;//原来取了n个数，每多取1个，就会新产生n个组数，同时n++;
                xx=-q.top().second;
                q.pop();

                a[a[xx].r].l=a[xx].l;//删数
                a[a[xx].l].r=a[xx].r;//删数
            }
            if(a[beginn].l!=0)//如果左边有比他们高的，加上
            ans+=hc+1;
            if(a[xx].r!=m+1)//如果右边有比他们高的，加上
            ans+=hc+1;
            continue;
        }

        if(a[xx].l!=0)//左边有比他高的，加上
        ans++;
        if(a[xx].r!=m+1)//右边有比他高的，加上
        ans++;
    }
    printf("%lld",ans);
    return 0;
}

管理员大大给过qwq