from copy import * def init(N,node,A,unit,func): n=1 while n1: y=y>>1 node[y-1]=node[-3](node[(y<<1)-1],node[y<<1]) def query(node,l,r): x,y=l,r z=node[-1]-1 rr=deepcopy(node[-2]) rl=deepcopy(node[-2]) while True: if x==y: return node[-3](rl,rr) if x&1: rl=node[-3](rl,node[x+z]) x+=1 if y&1: rr=node[-3](node[y+z-1],rr) if z==0: return node[-3](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