为什么没有题解把左右大小值都分开求解捏?
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n;
int nums[N];
int tr[N]; //构建树状数组维护某数出现次数
int left_upper[N];
int left_lower[N];
int right_upper[N];
int right_lower[N];
int ans1,ans2;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k)
{
while(x<=n)
{
tr[x] += k;
x += lowbit(x);
}
}
int ask(int x)
{
int res = 0;
while(x > 0)
{
res += tr[x];
x -= lowbit(x) ;
}
return res;
}
signed main()
{
cin >> n ;
for(int i=1;i<=n;i++) cin >> nums[i] ;
for(int i=1;i<=n;i++)//从左往右读一遍 找左边比其大/小的数
{
int x = nums[i];
left_upper[i] = ask(n) - ask(x);
left_lower[i] = ask(x-1) ;
add(x,1);
}
//现在属于是从左到右填了一遍树状数组 我们考虑再清空之后从右向左填写
memset(tr,0,sizeof(tr));
for(int i=n;i>=1;i--)
{
int x = nums[i];
right_upper[i] = ask(n) - ask(x);
right_lower[i] = ask(x-1) ;
add(x,1);
}
for(int i=1;i<=n;i++)
{
ans1+=left_upper[i]*right_upper[i];
ans2+=left_lower[i]*right_lower[i];
}
cout << ans1 << " " << ans2 << endl;
return 0;
}