[数据结构与算法]Python Bisect

bisect是python内置模块，用于有序序列的插入和查找

• 查找： bisect(array, item)
• import bisect
• 若数组a是升序序列

使用总结:

bisect.bisect(a,c)：返回数组a中最后一个<=c的索引值+1

若c存在于数组a，bisect.bisect_left(a,c)返回数组a中第一个出现c的索引值

若c不存在于数组a，bisect.bisect_left与bisect.bisect等效

若c存在于数组a，bisect.bisect_right(a,c)返回数组a中最后一个等于c的索引值+1

若c不存在于数组a，bisect.bisect_right与bisect.bisect等效

在查询一个有序的数组中有多少个>(<) c的时候，这个函数效率就很高

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
 
a.sort()
c.sort()
 
ans = 0


for i in range(n):
  x=bisect.bisect_left(a,b[i])
  y=len(c)-bisect.bisect_right(c,b[i])
  ans += x*y
print(ans)

这个代码是可以解决蓝桥杯一道真题：三元递增组，相较于用前缀和，代码量大大化简

前缀和代码：

n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
 
ans=[0 for i in range(max(a)+1)]
for i in a:
    ans[i]+=1
 
x=[0 for i in range(max(a)+1)]
x[0]=a.count(0)
for j in range(1,max(a)+1):
    x[j]=x[j-1]+ans[j]
 
 
cns=[0 for i in range(max(c)+1)]
for i in c:
    cns[i]+=1
 
y=[0 for i in range(max(c)+1)]
y[0]=c.count(0)
for j in range(1,max(c)+1):
    y[j]=y[j-1]+cns[j]
 
cnt=0
for k in range(n):
    if b[k]-1>len(x)-1:
        p=x[-1]
    elif b[k]-1<0:
        p=0
    else:
        p=x[b[k]-1]
    if len(y)-1<=b[k]:
        q=0
    else:
        q=y[-1]-y[b[k]]
    cnt+=p*q
print(cnt)

掌握一些内置的高效函数，大有裨益！