AcWing 1236. 递增三元组(前缀和 Python)
原题链接
中等
作者:
乖乖二号
,
2021-04-08 18:34:07
,
所有人可见
,
阅读 402
n = int(input())
a = list(map(lambda x:x + 1,map(int,input().split())))
b = list(map(lambda x:x + 1,map(int,input().split())))
c = list(map(lambda x:x + 1,map(int,input().split())))
#对cnt进行初始化,cnt[i]表示i出现的次数
cnt = [0] * (n+100000)
s = [0] * (n+100000)
#ass和css分别表示a和c的前缀和
As = [0] * n #As表示a中有多少个数小于b[i]
Cs = [0] * n
for i in range(n): cnt[a[i]] += 1
#预处理前缀和
for i in range(1,n+100000): s[i] = s[i-1] + cnt[i]
for i in range(n): As[i] = s[b[i] - 1]
cnt = [0] * (n+100000)
s = [0] * (n+100000)
for i in range(n): cnt[c[i]] += 1
for i in range(1,n+100000): s[i] = s[i-1] + cnt[i]
for i in range(n): Cs[i] = s[-1] - s[b[i]]
res = 0
for i in range(n):
res += As[i] * Cs[i]
print(res)