# 0-indexed binary indexed tree class BIT: def __init__(self, n): self.n = n self.data = [0]*(n+1) self.el = [0]*(n+1) # sum of [0,i) sum(a[:i]) def sum(self, i): if i==0:return 0 s = 0 while i > 0: s += self.data[i] i -= i & -i return s def add(self, i, x): i+=1 self.el[i] += x while i <= self.n: self.data[i] += x i += i & -i # sum of [l,r) sum(a[l:r]) def sumlr(self, i, j): return self.sum(j) - self.sum(i) # a[i] def get(self,i): i+=1 return self.el[i] def main0(n,s,t,sary,tary,query): ret=[] for tmp in query: c,x,y=tmp.split() x=int(x) y=int(y) if c=="S": s-=pow(10,n-x)*sary[x-1] s+=pow(10,n-x)*y sary[x-1]=y else: t-=pow(10,n-x)*tary[x-1] t+=pow(10,n-x)*y tary[x-1]=y #print(s,t) if s>t: ret.append(">") elif s==t: ret.append("=") else: ret.append("<") return ret def main1(n,s,t,sary,tary,query): dary=[abs(x-y) for x,y in zip(sary,tary)] bit=BIT(n) for i,x in enumerate(dary): bit.add(i,x) ret=[] for tmp in query: c,x,y=tmp.split() x=int(x) y=int(y) pre=dary[x-1] if c=="S": sary[x-1]=y else: tary[x-1]=y dary[x-1]=abs(sary[x-1]-tary[x-1]) bit.add(x-1,-pre+dary[x-1]) l,r=0,n+1 while r-l>1: x=(r+l)//2 if bit.sum(x)!=0: l,r=l,x else: l,r=x,r #print(*sary,sep="") #print(*tary,sep="") #print(*dary,sep="") #print(l) ans="=" for j in range(l-2,l+2): if j<1:continue if n