「Codeforces 1156E」Special Segments of Permutation
题目传送门
题意
给定一个长度为 \(n\) 的排列 \(a\)，求有多少区间 \([l,r]\) 满足 \(a_l+a_r=\max\limits_{i=l}^{r}a_i\)。
\(n\le 200\,000\)
题解
用单调栈对每一个 \(a_i\) 求出 \(l_i=j+1\)，\(j\) 是从 \(i\) 向左第一个满足 \(a_j>a_i\) 的位置，\(r_i\) 同理。
那么题目变为对于每个 \(i\) 求在 \([l_i,i-1]\) 和 \([i+1,r_i]\) 中各选出一个数使得这两个数之和为 \(a_i\) 的方案数。
结论是，我们只要枚举这两个区间中短的那个区间的每个数 \(a_j\)，然后在另一个区间中查询 \(a_i-a_j\) 是否存在即可。
看起来是 \(O(n^2)\)，其实是 \(O(n\log n)\) 的，因为每个数最多会被枚举到 \(\log n\) 次。假设某个数被枚举到的所有区间 \([l_i,r_i]\) 中，最大的区间长度为 \(m\)，那么由于枚举的是短的区间，短的区间长度不会超过 \(\frac{m}{2}\)。而如果这个数要被另一个区间枚举到，这个区间一定被之前那个短的区间包含，所以这个区间总长度不会超过 \(\frac{m}{2}\)，而且又是短的区间，所以变成了 \(\frac{m}{4}\)……感性理解一下，每个数枚举到的次数不会超过 \(\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
| #include <cstdio>
#include <algorithm>
#define N 200005
int n, a[N], p[N], l[N], r[N], top, sta[N], ans;
bool in(int x, int l, int r){
return l <= p[x] && p[x] <= r;
}
int main(){
scanf("%d", &n);
for (register int i = 1; i <= n; ++i) scanf("%d", a + i), p[a[i]] = i;
for (register int i = 1; i <= n; ++i){
while (top > 0 && a[i] > a[sta[top]]) --top;
l[i] = sta[top] + 1;
sta[++top] = i;
}
sta[top = 0] = n + 1;
for (register int i = n; i; --i){
while (top > 0 && a[i] > a[sta[top]]) --top;
r[i] = sta[top] - 1;
sta[++top] = i;
}
for (register int i = 1; i <= n; ++i){
int l1 = l[i], r1 = i - 1, l2 = i + 1, r2 = r[i];
if (r1 - l1 > r2 - l2) std :: swap(l1, l2), std :: swap(r1, r2);
for (register int j = l1; j <= r1; ++j)
if (in(a[i] - a[j], l2, r2)) ++ans;
}
printf("%d\n", ans);
}
|
