题解：P8251 [NOI Online 2022 提高组] 丹钓战
丹钓战，顾名思义单调栈。
首先是 $\texttt{15 pts}$ 做法，对于每个询问的区间，进行一次单调栈的模拟。时间复杂度 $O(nq)$。
然后可以稍微的优化一下，我们可以进行 $n$ 次单调栈来维护以第 $i$ 个数为起点的区间的答案。时间复杂度 $O(n^2)$，预计得分 $\texttt{30 pts}$。
数据点 $11-15$，针对的是序列的一些特殊性质，与最终算法可能关系不大，在此不赘述。接下来讲正解。
一个二元组如果是“成功的”，那么会有一个明显的特征，就是该二元组可以弹出所有入栈的二元组，并成为唯一的二元组被压入栈。当然，栈为空时将其压入栈便是一种特殊的情况，因此可以说是仍然满足该特征。所以我们可以定义 pre[i] 表示第 $i$ 个二元组可以弹出的最早的二元组所对应的编号，显然初始化有 pre[i] = i。询问一段区间中有多少个二元组符合题意，也就是求出该区间中的 pre[i] 满足小于等于区间左端点的个数。举个例子，区间 $[2,4]$ 对应的 pre[i] 的值为 $1,2,3$，则编号为 $2,3$ 的二元组符合题意。所以说，对于一个 pre[i]，它会对区间 [pre[i],i] 均产生贡献。那么，我们只需要按编号从小打大扫描一遍后分别求出询问左端点对应的答案即可。
那么如何求 pre[i] 的值呢，联系题目名称，不禁再次想到单调栈。当栈顶被弹出时，同时更新 pre[i] 的值为 pre[s.top ()] 即可。维护产生的贡献，不难看出是区间加的操作，当求解时，又是单点询问，于是树状数组变成了本题的首选（码量大，常数大的线段树默默靠边）。最后需要注意的一点时，因在扫描时的顺序为编号从小到大，而询问无序，因此我们需要对询问进行处理，以右端点为下标，记录左端点，这样在求解时左端点的答案就已经被计算出来了。总时间复杂度为 $O(n \log n)$。
代码如下：
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
#include <vector>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
vector <int> point[MAX];
stack <int> s;
int n,q,a[MAX],b[MAX],c[MAX],pre[MAX];
struct node
{
int l,r,ans;
} query[MAX];
void add (int x,int y);
int ask (int x);
int main ()
{
n = read ();q = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
for (int i = 1;i <= n;++i) b[i] = read ();
for (int i = 1;i <= q;++i)
{
query[i].l = read (),query[i].r = read ();
point[query[i].r].push_back (i);
}
for (int i = 1;i <= n;++i)
{
pre[i] = i;
while (!s.empty () && (a[s.top ()] == a[i] || b[s.top ()] <= b[i])) pre[i] = pre[s.top ()],s.pop ();
s.push (i);
}
for (int i = 1;i <= n;++i)
{
add (pre[i],1);add (i + 1,-1);
for (int j = 0;j < point[i].size ();++j) query[point[i][j]].ans = ask (query[point[i][j]].l);
}
for (int i = 1;i <= q;++i)
printf ("%d\n",query[i].ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void add (int x,int y)
{
for (int i = x;i <= n;i += (i & (-i))) c[i] += y;
}
int ask (int x)
{
int sum = 0;
for (int i = x;i;i -= (i & (-i))) sum += c[i];
return sum;
}
|
