T706110 学习小组
题意简述
给定长度为 n（n≤2×105）的序列 s，统计满足下标严格递增且
si<sj<sk或si>sj>sk
的三元组 (i,j,k) 的数量。
算法思路
将三元组问题转化为“中间人”问题：
对于每个位置 j，统计：
- 前面比 sj 小的数量：preLess[j]
- 前面比 sj 大的数量：preGreater[j]
- 后面比 sj 小的数量：postLess[j]
- 后面比 sj 大的数量：postGreater[j]
则每个位置 j 的贡献为：
preLess[j]×postGreater[j]+preGreater[j]×postLess[j]
总答案为所有位置贡献之和。
实现方法
- 离散化：将值域映射到连续区间，方便树状数组处理。
- 树状数组：两次扫描（正序 + 倒序）统计前后关系。
- 累加贡献：线性统计每个位置的贡献。
复杂度分析
- 时间复杂度：O(nlogn)
- 空间复杂度：O(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
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int n, s[N], tmp[N], m;
ll preL[N], preG[N], postL[N], postG[N], ans;
int c[N];
inline void add(int x, int v = 1) {
for (; x <= m; x += x & -x) c[x] += v;
}
inline int ask(int x) {
int s = 0;
for (; x; x -= x & -x) s += c[x];
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
tmp[i] = s[i];
}
sort(tmp + 1, tmp + n + 1);
m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
for (int i = 1; i <= n; ++i) {
int r = lower_bound(tmp + 1, tmp + m + 1, s[i]) - tmp;
preL[i] = ask(r - 1);
preG[i] = ask(m) - ask(r);
add(r);
}
memset(c, 0, sizeof(c));
for (int i = n; i >= 1; --i) {
int r = lower_bound(tmp + 1, tmp + m + 1, s[i]) - tmp;
postL[i] = ask(r - 1);
postG[i] = ask(m) - ask(r);
add(r);
}
for (int i = 1; i <= n; ++i)
ans += preL[i] * postG[i] + preG[i] * postL[i];
cout << ans << '\n';
return 0;
}
|
提示
- 树状数组常数较小，可直接通过。
- 注意离散化时处理重复值。