首页 > 代码库 > 小Z爱序列(NOIP信(sang)心(bin)赛)From Fall_Dream(粗制单调队列&单调栈的算法解析)

小Z爱序列(NOIP信(sang)心(bin)赛)From Fall_Dream(粗制单调队列&单调栈的算法解析)

原题:

小Z最擅长解决序列问题啦,什么最长公共上升然后下降然后上升的子序列,小Z都是轻松解决的呢。

       但是小Z不擅长出序列问题啊,所以它给了你一道签到题。

       给定一个n个数的序列ai,你要求出满足下述条件的点对的数量。

假设点对是(i , j),max(l,r)是[l,r]当中最大的ai的值。

这个点对满足条件当且仅当i+1<j 且 ai < max(i+1,j-1) < aj

为了简单,保证输入的是一个1-n的排列。相信你已经会做了吧?

输入/输出格式

输入数据第一行有一个数字n,然后第二行有n个数。

       输出仅包含一个数,表示满足条件的数对的数量。 

样例输入/输出    

       Input:

       5

       1 2 3 4 5

       Output:

       6

样例解释

       满足条件的分别是(1,3),(1,4),(1,5),(2,4),(2,5),(3,5)

数据范围与约定

      对于50%的数据,满足n<=300

       对于95%的数据,满足n<=10000

       对于100%的数据,满足n<=1000000

好吧,我承认。

这次考试所有的数据结构我都没学。(蒟蒻瑟瑟发抖。。)

首先看到题目n<=1000000

所以要O(N)算法

然而不论是线段树还是其他的算法维护max都是O(nlogn)(TLE 95分)

所以。。。

我们需要新的数据结构!

学长说这道题,水的很。。

单调栈来一个就搞过了。。(没学过。。。)

然后赶紧大补特补。。

单调栈就像一个简化版本的单调队列。

不过head是1,且队头指针永远不变

很显然,如果我们从n往1搜,a[i]对题目有贡献当且仅当a[i]右侧有2个比a[i]大的数

而它对答案的贡献就是右侧比它-2(点对条件看题目。。)

所以。。

就很简单啦。。(虽然我根本在考场上没写出来。。)

下面普及一下单调队列和单调栈的实现

首先我们先了解一下单调队列以及单调栈的操作

1、将一个元素插入队列。

2、将比这个元素大或等于这个元素的元素踢出队列

1的代码实现:que[++tail]=a[i];

2的代码实现:while(head<=tail&&que[tail]>=a[i])tail--;

当然有的题目还需要将队头向前移动:while(条件)head++;

然后我们将2个操作结合,就是单调队列啦、

在查询的时候我们只需要输出que[head]即可。(如果是单调栈,则输出que[1]);

由于每一个元素都进队一次,出队一次

复杂度均摊O(N)查询O(1);

所以很快QAQ

那为什么我们要用单调栈呢?

这个,,自己理解题意。。维护区间最小值、、

为什么要从N往1搜呢?(搞了好久才懂)

因为这道题求得是区间MAX,所以若从1往n搜,我们只能维护区间最小值,而队列中的元素会被后来的元素挤掉(无法统计答案),因为单调队列无法插入,只能用tail指针删除。所以要从N到1啦QAQ

Orz zxyer(1小时AK)

下面贴代码

#include<iostream>
#include<cstdio>
using namespace std;
int t,n;
unsigned long long ans;
int a[1000001];
int que[1000001];
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=n;i>=1;i--)
    {
        while((t)&&(que[t]<a[i])){t--;}
        que[++t]=a[i]; 
        if(t-2>0)
            ans+=t-2ll;
    }    
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
} 

 

小Z爱序列(NOIP信(sang)心(bin)赛)From Fall_Dream(粗制单调队列&单调栈的算法解析)