目录

1.1270、数列区间最大值 - AcWing题库

2.1215、小朋友排队 - AcWing题库

3.797、差分 - AcWing题库

4.二维差分

1.1270、数列区间最大值 - AcWing题库

python日常超时

def pushup(u): tree[u][0]=max(tree[u<<1][0],tree[u<<1|1][0]) returndef build(u,l,r): if l==r: tree[u]=[w[l],l,r] else: tree[u]=[0,l,r] mid=l+r>>1 build(u<<1,l,mid) build(u<<1|1,mid+1,r) pushup(u) returndef query(u,l,r): if tree[u][1]>=l and tree[u][2]<=r: return tree[u][0] else: maxium=0 mid=tree[u][1]+tree[u][2]>>1 if l<=mid: maxium=max(maxium,query(u<<1,l,r)) if r>mid: maxium=max(maxium,query(u<<1|1,l,r)) return maxiumN=10004n,m=map(int,input().split())w=[0]+list(map(int,input().split()))tree=[[]for i in range(4*N)]build(1,1,n)for _ in range(m): x,y=map(int,input().split()) print(query(1,x,y))

2.1215、小朋友排队 - AcWing题库

N=1000005def lowbit(x): return x&-xdef add(x,v): i=x while i0: sums+=tree[i] i-=lowbit(i) return sumsn=int(input())a=[0]+list(map(int,input().split()))a=list(map(lambda x:x+1,a))tree=[0 for i in range(N+1)]sums=[0 for i in range(n+1)]for i in range(1,n+1): sums[i]=query(N-1)-query(a[i]) add(a[i],1)tree=[0 for i in range(N+1)]for i in range(n,0,-1): sums[i]+=query(a[i]-1) add(a[i],1)ans=0for i in range(1,n+1): ans+=sums[i]*(sums[i]+1)//2print(ans)

3.797、差分 - AcWing题库

def add(l,r,v): b[l]+=v if r+1<=n: b[r+1]-=v returnn,m=map(int,input().split())a=[0]+list(map(int,input().split()))b=[0 for i in range(n+1)]for i in range(1,n+1): add(i,i,a[i])for _ in range(m): l,r,c=map(int,input().split()) add(l,r,c)for i in range(1,n+1): b[i]+=b[i-1] print(b[i])

4.二维差分

二维差分的核心代码

def add(x1,y1,x2,y2,v): b[x1][y1]+=v b[x2+1][y2+1]+=v b[x2+1][y1]-=v b[x1][y2+1]-=v