xxyQwQ
0%

【题解】ACMOJ 1485 单调栈

发表于 分类于

题目描述

ACMOJ - 1485 - 纯真丁一郎

给出一列 $n$ 个互不相同的数字 $a_1,a_2,\dots ,a_n$，定义一对 $i,j$ 满足性质当且仅当 $a_i,a_j$ 大于它们之间的所有数字 $a_{i+1},a_{i+2},\dots ,a_{j-1}$

子问题1：试求满足性质的数对总数

子问题2：给出 $m$ 次询问，每次限定 $i$ 范围为 $[l,r]$，但 $j$ 不限，求此时满足性质的数对总数

时间复杂度要求

虽然 $n,m\leq 10^6$ ，但要求实现 $O(n+m)$ 的算法

问题分析

时间复杂度要求已经明示线性解法了，我们大胆猜测本题正解是单调队列/单调栈

线性复杂度表明，对于每次询问我们要实现 $O(1)$ 查询，那么方案数一定满足可加性，所以要想办法求出：对于每个取定的位置 $i$ ，有多少相应的 $j\in[1,n]$ ，使得 $i,j$ 满足性质（记为 $v[i]$)

现在考虑 $v[i]$ 数组的求解，我们不妨先考虑 $a_i$ 的左侧，$a_1,a_2,\dots ,a_{i-1}$ 中哪些数与 $a_i$ 满足性质，不难发现以下特征：

  • $a_i$ 以左第一个比它大的数 $a_p$ 会“遮挡”住所有 $a_p$ 左侧的数，即 $a_1,a_2,\dots ,a_{p-1}$ 不会对方案数产生贡献
  • 若 $a_i$ 左侧两数 $a_m,a_n$ 满足 $m<n$ 且 $a_m<a_n$，则 $a_n$ 会“遮挡”住 $a_m$，换言之，对于单调增加的子列 $a_s,a_{s+1},\dots ,a_t$，只有最右边的 $a_t$ 产生贡献

以上两个特征对于问题求解的简化至关重要，它告诉我们计算 $v[i]$ 时，不考虑：

  • “过大”的数，即 $a_p$ 以左的数
  • “过小”的数，即已经被自身右侧其他数“遮挡”的数

于是我们只需要维护一个单调栈，它满足从栈底到栈顶的元素单调递减，算法流程如下：

  • 让 $i$ 遍历 $1,2,\dots ,n$
  • 把栈顶部所有小于 $a[i]$ 的数全部弹出，每弹出一个数，$v[i]+1$ （这些数都会产生贡献)
  • 如果栈仍然非空，贡献再 $+1$（左侧第一个大于 $a[i]$ 的元素也会产生贡献）
  • 将 $a[i]$ 压入栈中

完成上述算法后，$v[i]$ 中已经得到了 $a_i$ 左侧能与之满足性质的匹配数

对于右侧，我们从右至左，完全对称地执行上述算法，即可得到相应的匹配数

正确求解 $v[i]$ 数组后，我们计算其前缀和 $r[i]$，对于每次询问 $x,y$ ，答案即为 $\sum \limits _{k=x}^y v[k]=r[y]-r[x-1]$，即可实现 $O(1)$ 查询

一些细节

  1. 题目允许 $i=j$ ，因此 $a_i$ 与自身的匹配也要计算一次贡献
  2. 前缀和数组类型应当为long long，避免求和时溢出int范围
  3. 完成左侧方案数的计算后应当将栈清空
  4. 对栈操作时刻注意判空
  5. 请学会高效的读入方式，cin容易直接超时

思考

为什么上述算法流程包含两重循环，但复杂度是 $O(n)$ 呢？

我们注意到对于每个 $a_i$，至多只会发生一次入栈，一次出栈，因此第二重循环的操作次数上限为 $2n$，请读者仔细体会

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <cstdio>
const int SIZE = 1000005;

// ---------- 以下为链表栈的实现，可以忽略 ----------
template <typename ElementType>
class Stack
{
public:
    virtual ~Stack() {}
    virtual bool empty() const = 0;
    virtual void push(const ElementType &element) = 0;
    virtual ElementType pop() = 0;
    virtual ElementType top() const = 0;
    virtual void clear() = 0;
};

template <typename ElementType>
class LinkedStack : public Stack<ElementType>
{
private:
    struct StackNode
    {
        ElementType data;
        StackNode *next;
        StackNode() : next(nullptr) {}
        StackNode(const ElementType &_data, StackNode *_next = nullptr) : data(_data), next(_next) {}
        ~StackNode() {}
    };
    StackNode *head;

public:
    LinkedStack();
    ~LinkedStack();
    bool empty() const;
    void push(const ElementType &element);
    ElementType pop();
    ElementType top() const;
    void clear();
};

template <typename ElementType>
LinkedStack<ElementType>::LinkedStack()
{
    head = nullptr;
}

template <typename ElementType>
LinkedStack<ElementType>::~LinkedStack()
{
    clear();
}

template <typename ElementType>
bool LinkedStack<ElementType>::empty() const
{
    return head == nullptr;
}

template <typename ElementType>
void LinkedStack<ElementType>::push(const ElementType &element)
{
    head = new StackNode(element, head);
}

template <typename ElementType>
ElementType LinkedStack<ElementType>::pop()
{
    if (head == nullptr)
        throw Stack is already empty!;
    StackNode *temp = head;
    ElementType value = temp->data;
    head = head->next;
    delete temp;
    return value;
}

template <typename ElementType>
ElementType LinkedStack<ElementType>::top() const
{
    if (head == nullptr)
        throw Stack is already empty!;
    return head->data;
}

template <typename ElementType>
void LinkedStack<ElementType>::clear()
{
    StackNode *temp;
    while (head != nullptr)
    {
        temp = head;
        head = head->next;
        delete temp;
    }
}
// ---------- 以上为链表栈的实现，可以忽略 ----------

LinkedStack<int> s;
long long r[SIZE]; // Notice the summary can exceed range of int
int v[SIZE], h[SIZE], n, m;

int main()
{
    scanf(%d%d, &n, &m);
    for (int i = 1; i <= n; i++)
    {
        v[i] = 1; // Stand at the same position
        scanf(%d, &h[i]);
    }
    s.push(1);
    for (int i = 2; i <= n; i++) // Count on the left side
    {
        while (!s.empty() && h[s.top()] < h[i])
        {
            s.pop();
            v[i]++;
        }
        if (!s.empty())
            v[i]++;
        s.push(i);
    }
    while (!s.empty()) // Clear stack for next direction
        s.pop();
    s.push(n);
    for (int i = n - 1; i; i--) // Count on the right side
    {
        while (!s.empty() && h[s.top()] < h[i])
        {
            s.pop();
            v[i]++;
        }
        if (!s.empty())
            v[i]++;
        s.push(i);
    }
    for (int i = 1; i <= n; i++) // Calculate prefix summary to accelerate
        r[i] = r[i - 1] + v[i];
    printf(%lld\n, r[n]); // r[n] is the total summary
    while (m--)
    {
        int x, y;
        scanf(%d%d, &x, &y);
        printf(%lld\n, r[y] - r[x - 1]); // Summary from v[x] to v[y] is r[y] - r[x - 1]
    }
    return 0;
}