from copy import * def init(N,node,A,unit,func): while len(node): del node[-1] n=1 while n1: y=y>>1 node[y-1]=node[(y<<1)-1]+node[y<<1] def query(node,l,r): x,y=l,r z=node[-1]-1 rr=node[-2] rl=node[-2] while True: if x==y: return rl+rr if x&1: rl=rl+node[x+z] x+=1 if y&1: rr=node[y+z-1]+rr if z==0: return rl+rr x>>=1 y>>=1 z>>=1 mod=10**9+7 def comp(x): y=sorted(set(x)) d=dict() for i in range(len(y)): d[y[i]]=i return d def solve(A,B): N=len(A) X=[(A[i],B[i]) for i in range(N)] X.sort() Y=[X[i][0]-X[i][1] for i in range(N)] Z=[X[i][0]+X[i][1] for i in range(N)] y,z=comp(Y),comp(Z) ANS=0 segy=[] segz=[] init(N,segy,[],0,lambda x,y:x+y) init(N,segz,[],0,lambda x,y:x+y) c=0 for i in range(N): if i and X[i]==X[i-1]: c+=1 else: c=0 a,b=y[Y[i]],z[Z[i]] ANS=(ANS+X[i][0]*(query(segy,0,a)+query(segz,0,b)-i+c))%mod upd(segy,a,1) upd(segz,b,1) segy=[] segz=[] init(N,segy,[],0,lambda x,y:x+y) init(N,segz,[],0,lambda x,y:x+y) c=0 for i in range(N-1,-1,-1): if i+1