CH4201 楼兰图腾(树状数组(顺)逆序对)

题目链接: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;
}