题目链接:CH4201
对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.
"^"同理.
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
#define maxn 200005
typedef long long ll;
typedef unsigned long long ull;
int c[maxn];
int a[maxn];
int Right1[maxn];
int Left1[maxn];
int Right2[maxn];
int Left2[maxn];
int n;
int ask(int x){
int ans=0;
for(;x;x-=x&-x) ans+=c[x];
return ans;
}
void add(int x,int y){
for(;x<=n;x+=x&-x) c[x]+=y;
}
int main() {
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=n;i>0;--i){
Right1[i]=n-i-ask(a[i]);
Right2[i]=ask(a[i]-1);
add(a[i],1);
}
memset(c,0,sizeof(c));
for(int i=1;i<=n;++i){
Left1[i]=i-1-ask(a[i]);
Left2[i]=ask(a[i]-1);
add(a[i],1);
}
ll ans1=0,ans2=0;
for(int i=1;i<=n;++i){
ans1+=(ll)Left1[i]*Right1[i];
ans2+=(ll)Left2[i]*Right2[i];
}
cout<<ans1<<" "<<ans2<<endl;
return 0;
}