import sys input = sys.stdin.readline # class化 class Bit_indexed_tree(): def __init__(self, LEN): self.BIT = [0]*(LEN+1) # 1-indexedなtree. 配列BITの長さはLEN+1にしていることに注意。 self.LEN = LEN def update(self,v,w): # index vにwを加える while v<=self.LEN: self.BIT[v]+=w v+=(v&(-v)) # v&(-v)で、最も下の立っているビット. 自分を含む大きなノードへ. たとえばv=3→v=4 def getvalue(self,v): # [1,v]の区間の和を求める ANS=0 while v!=0: ANS+=self.BIT[v] v-=(v&(-v)) # 自分より小さい自分の和を構成するノードへ. たとえばv=14→v=12へ return ANS def bisect_on_BIT(self,x): # [1,ind]の和がはじめてx以上になるindexを探す if x<=0: return 0 ANS=0 h=1<<((self.LEN).bit_length()-1) # LEN以下の最小の2ベキ while h>0: if ANS+h<=self.LEN and self.BIT[ANS+h]=const0: LIST2[i]=Bit_indexed_tree(N+100) LIST3[i]=Bit_indexed_tree(N+100) for x in LIST[i]: LIST2[i].update(x+1,x) LIST3[i].update(x+1,1) for tests in range(Q): L=input().split() if len(L)==3: i,x=L[1],L[2] i=int(i)-1 if i-2>=0: a=tm(i-2) if LIST2[a]: LIST2[a].update(i-2+1,-(i-2)) LIST3[a].update(i-2+1,-1) else: LIST[a].remove(i-2) if i-1>=0 and i+1=0: a=tm(i-2) if LIST2[a]: LIST2[a].update(i-2+1,i-2) LIST3[a].update(i-2+1,1) else: LIST[a].add(i-2) if len(LIST[a])>=const0: LIST2[a]=Bit_indexed_tree(N+100) for x in LIST[a]: LIST2[a].update(x+1,x) LIST3[a].update(x+1,1) if i-1>=0 and i+1=const0: LIST2[a]=Bit_indexed_tree(N+100) for x in LIST[a]: LIST2[a].update(x+1,x) LIST3[a].update(x+1,1) if i+2=const0: LIST2[a]=Bit_indexed_tree(N+100) for x in LIST[a]: LIST2[a].update(x+1,x) LIST3[a].update(x+1,1) else: l,r,s=L[1],L[2],L[3] l=int(l)-1 r=int(r)-1 a=tm2(s,0) ANS=0 if LIST2[a]: cc=LIST2[a].getvalue(r-2+1)-LIST2[a].getvalue(l) dd=LIST3[a].getvalue(r-2+1)-LIST3[a].getvalue(l) ANS=cc-(l-1)*dd print(ANS) else: for x in LIST[a]: if l<=x<=r-2: ANS+=x-l+1 print(ANS)