POJ3250「Bad Hair Day」

1. 题目

题目链接：POJ3250「Bad Hair Day」 。

Description

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height h_i (1 ≤ h_i ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow ican see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

        =
=       =
=   =   =         Cows facing right -->
=   =   =
= = = = =
= = = = = =
1 2 3 4 5 6 

• Cow#1 can see the hairstyle of cows #2, 3, 4
• Cow#2 can see no cow’s hairstyle
• Cow#3 can see the hairstyle of cow #4
• Cow#4 can see no cow’s hairstyle
• Cow#5 can see the hairstyle of cow 6
• Cow#6 can see no cows at all!

Let c_i​ denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c_1through c_N​. For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5

Input

Line 1: The number of cows, N. Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

Output

Line 1: A single integer that is the sum of c_1​ through c_N​.

Sample Input

6
10
3
7
4
12
2

Sample Output

5

2. 题解

分析

题目是要求出所有牛可以看到的其他牛发型的总数，等价于求出所有牛被其他牛看到的次数总和。即对于当前牛 i 来说，看到 i 发型的牛应该是 i 牛左边的且满足高度从右到左严格递增且大于 i 的高度的那些牛，而且该递增高度序列相对于 i 来说是从右到左的首递增序列（即第一个严格递增序列）。

首递增序列 对于序列 a_1,a_2,\cdots,a_N，定义从左往右 a_i 的首递增序列为 a_{b_0}=a_i,a_{b_1},a_{b_2},\cdots,a_{b_m}​​，满足\forall j \in (0, m] ，都有 \forall 1 \leq k \lt b_j, a_{b_{j-1}} \geq a_k \wedge a_k \lt a_{b_j}

对于首递增序列，我们可以利用单调栈轻松解决。单调递增栈就是用来保存当前栈顶元素的首递增序列的，其满足栈顶元素到栈底元素形成的序列为栈顶元素在原序列中的首递增序列。由于我们从左往右处理数据且栈满足后进先出的性质，故形成的首递增序列是栈顶元素从右往左的首递增序列。

【注】N \leq 80000，故 {N(N-1) \over 2} 会超出 int 的表示范围，所以答案需要用 long long 型表示。

代码

#include <stdio.h>
#include <stdlib.h>
#include <iostream>

// #include <bits/stdc++.h>
using namespace std;

// 比较元素
template < typename T >
struct Compare {
    bool operator () (const T & a, const T & b) {
        return a > b;
    }
};
// 单调栈
template < typename T, typename F = Compare<T> >
struct MStack{
    #ifndef _MSTACK_
    #define ll int
    #define MAXN 100005
    #endif
    ll depth;       // 栈深
    T stack[MAXN];  // 单增栈
    F cmp;
    MStack():depth(0) {}
    // 二分查找
    ll find(T x, ll l, ll r) {
        if(l == r)  return l;
        ll m = (l+r) >> 1;
        if(cmp(stack[m], x)) {
            return find(x, m+1, r);
        } else {
            return find(x, l, m);
        }
    }
    // 压栈
    T push(T x) {
        // // 方法一
        // // 顺序弹栈 O(n)，整体 O(2n)
        // while(depth && !cmp(stack[depth-1], x))   --depth;
        // stack[depth++] = x;
        // return x;

        // 方法二
        // 二分查找 O(lg(n))，整体 O(nlg(n))
        if(!depth || cmp(stack[depth-1], x)) {
            stack[depth++] = x;
            return x;
        }
        ll pos = find(x, 0, depth-1);
        T t = stack[pos];
        stack[pos] = x;
        depth = pos + 1;
        return t;
    }
    // 弹栈
    T pop() {
        return stack[--depth];
    }
};

int main()
{
    ll n;
    ll a[MAXN];
    MStack <ll> ms;
    scanf("%d", &n);
    for(ll i = 0; i < n; ++i) {
        scanf("%d", a+i);
    }
    long long ans = 0;
    for(ll i = 0; i < n; ++i) {
        ms.push(a[i]);
        ans += ms.depth - 1;
    }
    printf("%lld\n", ans);
    return 0;
}