Loading... # ACWing 241 楼兰图腾 题解 ## 题目描述 在完成了分配任务之后，西部$314$来到了楼兰古城的西部。 相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(`V`)，一个部落崇拜铁锹(`∧`)，他们分别用 `V` 和 `∧` 的形状来代表各自部落的图腾。 西部$314$在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了$n$个点，经测量发现这$n$个点的水平位置和竖直位置是两两不同的。 西部$314$认为这幅壁画所包含的信息与这$n$个点的相对位置有关，因此不妨设坐标分别为 $(1,y_1),(2,y_2),…,(n,y_n)$，其中$y_1∼y_n$是$1$到$n$的一个排列。 西部$314$打算研究这幅壁画中包含着多少个图腾。 如果三个点$(i,y_i),(j,y_j),(k,y_k)$满足$1\leq i< j < k\leq n$ 且$y_i>y_j,y_j<y_k$，则称这三个点构成 `V` 图腾; 如果三个点$(i,y_i),(j,y_j),(k,y_k)$满足$1≤i<j<k≤n$ 且$y_i<y_j,y_j>y_k$，则称这三个点构成 `∧` 图腾; 西部$314$想知道，这$n$个点中两个部落图腾的数目。 因此，你需要编写一个程序来求出 `V` 的个数和 `∧` 的个数。 ## 输入 第一行一个数$n$。 第二行是$n$个数，分别代表$y_1，y_2,\cdots,y_n$。 ## 输出 两个数，中间用空格隔开，依次为 `V` 的个数和 `∧` 的个数。 ## 解题思路 为了解决这道问题， 首先我们应该定义如何去计算 `V` 和 `∧` 的个数, 一个显然且简单的方式是通过尖端的位置去计算二者。 为此， 以计算`∧` 的个数为例， 为了计算$x_i$位置上所有`∧` 的个数， 我需要知道$j < i \wedge x_j < x_i$的$j$的数量， 同理， 我还需要了解$k > i \wedge x_k < x_i$的$k$的数量 因此我需要先维护一个前缀数组`pre`， 存储纵坐标小于等于$y_i$的点的数量， 并利用前缀数组动态更新数组`L`， 用以维护从左到右遍历到当前点的时候， 该点的左侧纵坐标小于该点的数量`L[yi]` 接着， 同理维护一个后缀数组`suf`， 存储纵坐标小于等于$y_i$的点的数量，动态维护 该点的右侧纵坐标小于该点的数量`suf[yi]` 最后， $x_i$位置上所有`∧` 的个数为`L[yi] * suf[yi]` 分析时间复杂度可得， 插入操作的时间复杂度为$O(1)$, 区间求和的时间复杂度为$O(n)$， 因此总体的时间复杂度为$O(n^2)$， 在$n=200,000$的情况下一定会超时。因此可以考虑使用树状数组优化时间复杂度， 树状数组的插入和删除的时间复杂度均为$O(log n)$， 因此总的时间复杂度为$O(nlogn)$ ## AC代码 ```cpp #include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N = 2e5 + 10; int n; int a[N]; int tr[N]; int G[N], L[N]; int lowbit(int x) { return x & -x; } void add(int x, int c) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += c; } int sum(int x) { int res = 0; for(int i = x; i > 0; i -= lowbit(i)) res += tr[i]; return res; } int main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> a[i]; for(int i = 1; i <= n; i ++) { G[i] = sum(n) - sum(a[i]); L[i] = sum(a[i] - 1); add(a[i], 1); } memset(tr, 0, sizeof tr); long long ans1 = 0, ans2 = 0; for(int i = n; i >= 1; i --) { ans1 += 1ll * G[i] * (sum(n) - sum(a[i])); ans2 += 1ll * L[i] * sum(a[i] - 1); add(a[i], 1); } cout << ans1 << ' ' << ans2 << endl; } ``` 最后修改：2025 年 04 月 17 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏