题目

略

警告

本题比较抽象，难理解，本人花了半天时间才明白【也有可能是我太蠢了–！】

思路

如何构成V

1. 以V字形举例，某个数字$i$能够成V字形的充要条件是：每个数字的左右两边都有大与$i$的数
2. 某个数字i为中间能够成的V对的数目为，该数字左边大于i的数目乘上右边大于i的数目

如何找到V的数目

比如：

3 5 2 6 4

以2为例，要以2为中间构成V字形，则需要找到左侧大于2的数字【3，5】，和右侧大于2的数字【6，4】，所以2位中间的V字形数目为2*2=4

以此类推，只需要找到每个数字左右两侧大于该数字的数目，然后相乘即可

第二个符号

第二个符号同理，也可以按上面的思路来

已知数组中，重复元素不影响答案，所以可以先进行去重，在数组中没有重复元素的前提下：
某个元素i左侧大于i的个数+左侧小于i的个数=i

所以第二个符号的左右两侧的数目可以由第一个符号的两侧数目直接得出！！

如何找到某个数字左侧小于某个数的元素个数

leetcode 315题【强烈建议先做完这题！！！】

使用树状数组的单点修改和区间求和方法求解

1. 使用稳定排序算法排序【315题中必须使用稳定排序，否则会因为赋值顺序出错，本题中可以去重，所以是否稳定不影响】
2. 从左向右遍历第i个数字，首先对i个数字的索引为下标的进行区间求和【计算左侧小于数字i的个数】
3. 对第i个数字的索引为下标进行单点更新【更新值固定为1】

代码

N = int(input().strip())
nums = list(map(int,input().strip().split()))


def lowbit(x):
    return x&(-x)

def add(p,v,Tree):
    while p <= N:
        Tree[p-1] += v
        p += lowbit(p)

def sum_(p,Tree):
    ans =0
    while p>0:
        ans += Tree[p-1]
        p -= lowbit(p)
    return ans

# 统计每个元素左边、右边 | 大于、小于他的元素个数
# 去重
nums = list(set(nums))

# 排序索引
from operator import itemgetter
idx = [index for index, value in sorted(enumerate(nums), key=itemgetter(1))]
idx_ = [0]*N
for i in range(N):
    idx_[idx[i]] = i
# print(idx_)

Tree_l_m = [0]*N
ans_l_m = [0]*N
for i in range(N-1,-1,-1):
    ans_l_m[i] = sum_(idx_[i],Tree_l_m)
    add(idx_[i]+1,1,Tree_l_m)

# print(ans_l_m) 

Tree_r_m = [0]*N
ans_r_m = [0]*N
for i in range(N):
    ans_r_m[i] = sum_(idx_[i],Tree_r_m)
    add(idx_[i]+1,1,Tree_r_m)

# print(ans_r_m) 

ans1 = 0
for i in range(N):
    ans1+= (i-ans_r_m[i])*(N-1-i-ans_l_m[i])

# 两边小的：
ans2 = 0
for i in range(N):
    ans2+= ans_l_m[i]*ans_r_m[i]

print(ans1,ans2)