题目来源：https://www.acwing.com/activity/content/2869/

楼兰图腾

题意

https://www.acwing.com/problem/content/243/

思路

按照中间的点将答案划分为不重不漏的N个集合，依次计算每个集合中的个数，使用树状数组优化

树状数组注意下标从1开始

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
n = int(input())
tr = [0 for i in range(n+2)]
big = [0 for i in range(n+2)] # 下标为i的数左边比它大的个数
sm = [0 for i in range(n+2)]

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

def add(i,c):
    while i<=n:
        tr[i]+=c
        i += lowbit(i)

def sum(idx):
    res = 0
    while idx:
        res += tr[idx]
        idx -= lowbit(idx)
    return res

a = list(map(int,input().strip().split(" ")))
a = [0]+a

for i in range(1,n+1):
    big[i] = sum(n) - sum(a[i])
    sm[i] = sum(a[i]-1)
    add(a[i],1)
    
res1,res2 = 0,0
del(tr)
tr = [0 for i in range(n+2)]

for i in range(n,0,-1):
    res1 += (sum(n) - sum(a[i]))*big[i]
    res2 += (sum(a[i]-1))*sm[i]
    add(a[i],1)

print(res1,res2)

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1

楼兰图腾

题意

思路

代码

1