E2-D Who can I see

题目描述

Thiamine 班上现在要体检，全班 n(1≤n≤3×105)n(1≤n≤3×10^5) 位同学排成了一队，第 ii 位同学身高为 ai(1≤ai≤109)a_i(1≤a_i≤10^9) ，正如世界上没有两朵雪花一样，也没有两个同学身高一样。

因为大家还不是很熟悉，每个人都在前后看自己的同学是谁。每个人想知道自己都能看到谁，正如某老师所说，编程是一门体力活，对身体有很大的损伤，同学们的颈椎都受到了损伤，不能抬头，故：

  • 当$ j<i 时，第时，第 i 位同学能看到第位同学能看到第 j $位同学当且仅当 ak≤ai(j≤k≤i)a_k≤a_i(j≤k≤i)

  • 当$ j>i$ 时，第$ i 位同学能看到第位同学能看到第 j $位同学当且仅当 ak≤ai(i≤k≤j)a_k≤a_i(i≤k≤j)

输入

第一个数为数据组数 $T(1≤T≤10) $；

接下来 T 组数据，每组数据包含两行；

第一行一个正整数 n(1≤n≤3×105)n(1≤n≤3×10^5) 代表排队的同学数；

第二行 n 个正整数 $a_i(1≤a_i≤10^9) $代表每个同学的身高。

输出

为减少输出量，对于每组数据，仅输出一个正整数，代表每位同学可以看到的其他同学的数目之和。

输入样例

1
2
3
1
4
1 4 2 3

输出样例

1
4

hint

对样例做出如下解释，第1位同学看不到其他任何同学，第2位同学能看到第1，3，4位同学，第3位同学看不到其他任何同学，第4位同学能看到第3位同学，故答案为1+3=4。

本题读入量较大，请至少使用不劣于 scanf 的读入方式！

题目分析

此题需要求出每位同学左边第一个比自己高的同学位置和右边第一个比自己高的位置。可以考虑左边和右边分开求，即使用两次循环。如果每位同学都从自己开始往前遍历很容易超时，所以需要对上一位同学遍历后的结果进行处理。假设第ii位同学往前能看到jj，第jj位同学往前能看到kk，则有ai<=aj<=aka_i<=a_j<=a_k，发现对于i+1i+1来说有两种情况：

  1. 大于aia_i，此时对于i，ji，j之前的元素无需判断一定能看到，与jj比较后，如果大于aja_j则同理继续向前从kk开始；如果小于则能看到的人数即为i−ji-j；
  2. 小于aia_i，此时能看到的人数为0；

以左边为例，0号同学先入栈，从1号开始遍历，如果比0号同学高则0号出栈，自己入栈，对应答案加上**1−01-0**；如果比0号同学矮则自己直接入栈。如果2号同学比栈顶同学高则执行出栈操作，直到遇见比自己高的或者栈为空，自己入栈。对应答案加上selfIndex−topIndexselfIndex-topIndex

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int students[n];
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &students[i]);
        }

        int s[n];
        long long int ans = 0;
        int top = -1;
        for (int i = 0; i < n; i++)
        {
            while (top != -1 && students[i] >= students[s[top]])
            {
                top--;
            }
            if (top == -1)
            {
                ans += i * 1LL;
            }
            else
            {
                ans += i * 1LL - s[top] - 1;
            }
            s[++top] = i;
        }

        top = -1;
        for (int i = n - 1; i >= 0; i--)
        {
            while (top != -1 && students[i] >= students[s[top]])
            {
                top--;
            }
            if (top == -1)
            {
                ans += (n - i - 1) * 1LL;
            }
            else
            {
                ans += s[top] - i * 1LL - 1;
            }
            s[++top] = i;
        }

        cout << ans << endl;
    }

    return 0;
}