楼兰图腾
-
这道题很容易想到其朴素做法。从左往右扫一遍,每次扫到一个数字的时候将其左边以及右边再扫一遍,统计出其两边能和他组成
V
或者倒V的数字的个数,然后通过乘法原理乘起来。这样做的时间复杂度是 $O(n^2)$ 。但是我们很容易想到如果第一次扫的时候把左边大于他的数用树状数组记录下来,然后扫到这个元素的时候直接求出小于其的元素的个数之和,然后右边也是这样扫一遍,就能优化到 $0(nlogn)$ 的时间复杂度。因为扫一遍的时间复杂度是 $O(n)$ ,而在树状数组中求区间和的时间复杂度是 $O(logn)$ 。 -
这里还要注意在更新
res
的时候要先转换为long long
然后再加。因为如果不这样的话会先乘了再转换为long long
。在乘的时候可能就会爆int
。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x) & (-(x)))
const int N = 200010;
int a[N], tr[N];
int gt[N], lower[N];
int n;
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int sum(int x)
{
int res = 0;
for (int i = x; i; 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 ++ )
{
int y = a[i];
gt[i] = sum(n) - sum(y);
lower[i] = sum(y - 1);
add(y, 1);
}
memset(tr, 0, sizeof tr);
ll res1 = 0, res2 = 0;
for (int i = n; i > 0; i -- )
{
int y = a[i];
res1 += ((ll)gt[i] * ((ll)sum(n) - (ll)sum(y)));
res2 += (lower[i] * (ll)sum(y - 1));
add(y, 1);
}
cout << res1 << " " << res2;
return 0;
}