题目描述
https://www.luogu.com.cn/problem/CF1175F
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求有多少子区间 $[l,r]$ 满足 $[1,r-l+1]$ 中的所有数都出现一次
$n\le 3\times 10^5$
Solution
首先转换一下子排列的定义：
- 没有重复数字
- 最大值为 $r-l+1$
我们考虑按照每个数作为最大值的区间来构建笛卡尔树
然后我们对于每个数，枚举小的那一半，知道左端点就能得到右端点
注意到这里枚举小的那一半的时间复杂度仅为 $O(n\log n)$，类似于启发式合并
至于如何判断没有重复数字，我们可以用最简单的方法，查询区间 $pre$ 的最大值
只要满足区间 $pre$ 的最大值小于 $l$ 就一定不存在重复数字
我们使用 $st$ 表做到 $O(1)$ 询问区间最值，这样总的复杂的就是 $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
| #include <iostream>
#include <cstdio>
#include <stack>
#define maxn 300010
#define INF 1000000000
using namespace std;
int n, a[maxn];
int l[maxn], r[maxn]; stack<int> S;
int pre[maxn], vis[maxn], st[maxn][21], Log[maxn];
void init_st() { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = pre[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r) {
int k = Log[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
S.push(0); a[0] = INF;
for (int i = 1; i <= n; ++i) {
while (a[S.top()] < a[i]) S.pop();
l[i] = S.top() + 1; S.push(i);
}
while (!S.empty()) S.pop();
S.push(n + 1); a[n + 1] = INF;
for (int i = n; i; --i) {
while (a[S.top()] < a[i]) S.pop();
r[i] = S.top() - 1; S.push(i);
}
for (int i = 1; i <= n; ++i) {
pre[i] = vis[a[i]];
vis[a[i]] = i;
} init_st(); int ans = 0;
for (int i = 1; i <= n; ++i)
if (i - l[i] <= r[i] - i) {
for (int j = l[i]; j <= i; ++j) {
int k = j + a[i] - 1;
if (i <= k && k <= r[i] && query(j, k) < j) ++ans;
}
}
else {
for (int j = i; j <= r[i]; ++j) {
int k = j - a[i] + 1;
if (l[i] <= k && k <= i && query(k, j) < k) ++ans;
}
}
cout << ans << "\n";
return 0;
}
|