C++ 代码
//1.对于序列中的每个数a[i],我们可以分别求出a[i]的右侧和左侧比a[i]的大的数各有多少个,用r[i]和l[i]记录
//2.然后我们枚举每个点作为中心点,以该点为中心的“V”或“^” 显然有r[i] * l[i]个,所以最终的答案就是∑(1 <= l <= r)r[i] * l[i]的总和
//3.这道题的数据范围很大,所以我们可以用树状数组来做,创建一个数组 t,t[val] 保存数值 val 在集合中出现的次数, 那么数组 t 在[l, r]
//上的区间和(即∑(l <= i <= r)t[i])就表示集合 a 中范围在[l, r]内的数有多少个;
//4.倒序扫描给定的序列a,对于每个数 a[i]:
// (1).在树状数组中查询前缀和 [1, a[i] - 1], 并用r[i]记录
// (2).执行增加操作,即把位置a[i] 上的数 + 1(即t[a[i]]++), 同时正确维护 t 的前缀和, 表示数值a[i]又出现了一次
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll c[N], r[N], l[N];
int a[N];
int n;
int lowbit(int x)
{
return x & -x;
}
int ask(int x) //这里表示范围1 ~ x 在序列中出现的次数
{
int ans = 0;
while(x){
ans += c[x];
x -= lowbit(x);
}
return ans;
}
void add(int x, int y)
{
while(x <= n){
c[x]++;
x += lowbit(x);
}
}
int main()
{
ll sum1 = 0, sum2 = 0;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = n; i >= 1; i--){
r[i] = ask(n) - ask(a[i]); //统计a[i]的右侧比a[i]大的数有多少个
add(a[i], 1);
}
memset(c, 0, sizeof c);
for(int i = 1; i <= n; i++){
l[i] = ask(n) - ask(a[i]);//统计a[i]的左侧比a[i]大的数有多少个
add(a[i], 1);
}
for(int i = 1; i <= n; i++){ //得到“V”字形的答案
sum1 += l[i] * r[i];
}
memset(l, 0, sizeof l);
memset(r, 0, sizeof r);
memset(c, 0, sizeof c);
for(int i = n; i >= 1; i--){ //统计a[i]的右侧比a[i]小的数有多少个
r[i] = ask(a[i] - 1);
add(a[i], 1);
}
memset(c, 0, sizeof c);
for(int i = 1; i <= n; i++){ //统计a[i]的左侧比a[i]大的数有多少个
l[i] = ask(a[i] - 1);
add(a[i], 1);
}
for(int i = 1; i <= n; i++) //得到“^”字形的答案
sum2 += l[i] * r[i];
cout << sum1 << ' ' << sum2 << endl;
return 0;
}
老哥 写错了 add里面应该是+y , 这是我弄懂的第一道树状数组题目·hah