# ref # [1]蟻本 # [2]http://hos.ac/slides/20140319_bit.pdf # テストケース # [t1]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=jp # [t2]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp # [t3]https://atcoder.jp/contests/abc241/tasks/abc241_d # [t4]https://yukicoder.me/problems/no/877 # [t5]https://atcoder.jp/contests/arc033/tasks/arc033_3 # [t6]https://yukicoder.me/problems/no/877 # BinaryIndexedTreeです。 # 区間和をO(log(N))で求めることができます。また数列に要素を加算することができます。 # 同じことがセグメント木でもできますが、こっちのほうが速いので、区間和を求めたいときはこっちを使いましょう。updateも実はできて、updateしたいときでもセグメント木よりかなりはやいです。 class BinaryIndexedTree: # O(N*log(N)) # 実は初期化はセグメント木より遅い（0じゃない値で初期化する場合には） # ただしAを全部0にすることもでき、その場合にはO(N)で初期化できるように実装してあります。ただしNのループは回るので定数倍だけ[0]で初期化するよりも遅くなりますが……。 def __init__(self, A): """ A: 初期化する配列 """ # 要素数 self.N = len(A) # BITを管理する木、1-indexedにするので要素数はN+1 self.tree = [0] * (self.N + 1) # Aでtreeを初期化します。このとき0ではaddを実行しないようにします。これにより配列が全部0ならO(N)で初期化できます。 for k, a in enumerate(A): if a != 0: self.add(k, a) # 半開区間[0,i)の和を求めます def _sum(self, i): # 半開区間であることと0-indexedであることがうまく相殺して蟻本と完全に同じ実装になる。 # sumです s = 0 while i > 0: s += self.tree[i] i -= i & -i return s # O(log(N)) # a[k]にxを加算します、すなわちa[k]+=xと同じ操作 def add(self, k, x): # self.treeは1-indexedなので1を足しておく必要がある k += 1 while k <= self.N: self.tree[k] += x k += k & -k #O(log(N)) #a[k]をxに変更します。a[k]=x def update(self,k,x): #BITだとストレートにupdateできないが、getしてからaddするという方法でできる。#いまのxを打ち消すような値を追加する self.add(k,x-self.get(k)) # O(log(N)) # 半開区間[left,right)の和を求めます。ただし、区間が空集合のときはErrorを吐きます # ただしleft,rightにNoneを入力すると、例えばleft=Noneにするといまありうる一番左を指定します def sum(self, left, right): # Noneなら持ち変える if left is None: left = 0 if right is None: right = self.N if 0 <= left <= right <= self.N: return self._sum(right) - self._sum(left) else: raise ValueError( "半開区間[{},{})が空集合、もしくはIndex out of rangeです。".format( left, right)) # O(log(N)) # セグメント木と違って定数オーダーではないので注意してください。もとの全部の要素を持ってないので、sumで取り出す必要があるからです。 # これを何回も使う場合はセグメント木を使うべきである。 def get(self, k): return self.sum(k, k + 1) # [t1] """ n,q=map(int,input().split()) query=[] for _ in range(q): query.append(list(map(int,input().split()))) bit=BinaryIndexedTree([0]*n) for com,x,y in query: if com==0: bit.add(x-1,y) else: print(bit.sum(x-1,y)) """ # [t2] """ N=int(input()) a=list(map(int,input().split())) #数列の反転数がBITを用いてO(N*log(N))で求められることは暗記しておきましょう。 #いまmax(a[i])が大きく、そのサイズのbitを用意できないので、座標圧縮する def coordinate_comp(A, comp_to_original=False): if not comp_to_original: return {a: c for c, a in enumerate(sorted(set(A)))} else: comp_to_A, A_to_comp = {}, {} for c, a in enumerate(sorted(set(A))): comp_to_A[c]=a A_to_comp[a]=c return A_to_comp,comp_to_A a2comp=coordinate_comp(a) a=[a2comp[ai] for ai in a] #bitは[min(a),max(a)]の範囲を用意する。いまは座標圧縮したので[0,len(a)] bit=BinaryIndexedTree([0]*N) #転倒数 les=0 for j in range(N): les+=j-bit.sum(None,a[j]) bit.add(a[j],1) print(les) """ # [t3] """ Q=int(input()) queries=[] X=[] for _ in range(Q): q=tuple(map(int,input().split())) queries.append(q) X.append(q[1]) #座標圧縮 def coordinate_comp(A, comp_to_original=False): if not comp_to_original: return {a: c for c, a in enumerate(sorted(set(A)))} else: comp_to_A, A_to_comp = {}, {} for c, a in enumerate(sorted(set(A))): comp_to_A[c]=a A_to_comp[a]=c return A_to_comp,comp_to_A x2comp,comp2x=coordinate_comp(X,comp_to_original=True) bit=BinaryIndexedTree([0]*(len(x2comp)+1)) #セグメント木の言葉でいうと、まず全要素のうちk番目に小さい要素とは、区間和[0,i]がkになるような最小のiということになります。 #なのでx以上の要素のうち大きい方からk番目の値とは区間和[x,i]がkになるようなiのうち最小の値となります。 for query in queries: if query[0]==1: bit.add(x2comp[query[1]],1) elif query[0]==2: _,x,k=query x=x2comp[x] #区間和[i,x+1)がkになるようなiのうち最大のiを求める if bit.sum(None,x+1)=k: left=mid else: right=mid #leftが答えです print(comp2x[left]) else: _,x,k=query x=x2comp[x] #区間和[x,i]がkになるような最小のiを二分探索します if bit.sum(x,None)=k: #このときは左による right=mid else: left=mid #leftが答えです print(comp2x[left]) """ # [t4] """ N,Q=map(int,input().split()) a=list(map(int,input().split())) query=[] for i in range(Q): #ソートの関係で順番はちょっとかわっている _,l,r,x=map(int,input().split()) query.append((x,l,r,i)) #a[i]がxよりも小さいならそれは和に寄与しないので、入れておく必要がありません。よってa,xを同時に大きい順にソートして答えればいい。 #クエリにaもいれる for i in range(N): query.append((a[i],i)) #ソート query.sort(reverse=True) sumbit=BinaryIndexedTree([0]*N) cntbit=BinaryIndexedTree([0]*N) les=[] for q in query: if len(q)==4: x,l,r,i=q #このとき区間の和を求める。和から要素数*xを引きます sumv,cntv=sumbit.sum(l-1,r),cntbit.sum(l-1,r) les.append([i,sumv-x*cntv]) else: a,i=q #このときはセグメント木をadd。iはユニークなのでaddでもupdateでもいい sumbit.add(i,a) cntbit.add(i,1) les.sort() for _,d in les: print(d) """ #[t5] """ Q = int(input()) query = [] for _ in range(Q): query.append(tuple(map(int, input().split()))) bit=BinaryIndexedTree([0]*200001) for t,x in query: if t==1: #なぜかupdateでも通ったけどaddにするのがただしいと思う bit.add(x,1) else: left=0 right=200001 while left+1=x: #このときは左による right=mid else: left=mid #leftの削除も必要です。いまの場合削除とは0にすることにほかならないので bit.update(left,0) print(left) """ #[t6] N,Q=map(int,input().split()) a=list(map(int,input().split())) query=[] for i in range(Q): #ソートの関係で順番はちょっとかわっている _,l,r,x=map(int,input().split()) query.append((x,l,r,i)) #a[i]がxよりも小さいならそれは和に寄与しないので、入れておく必要がありません。よってa,xを同時に大きい順にソートして答えればいい。 #クエリにaもいれる for i in range(N): query.append((a[i],i)) #ソート query.sort(reverse=True) # 区間和のセグメント木と区間の要素数のセグメント木をどちらも用意します sumbit=BinaryIndexedTree([0]*N) numbit=BinaryIndexedTree([0]*N) les=[] for q in query: if len(q)==4: x,l,r,i=q #このとき区間の和を求める。和から要素数*xを引きます les.append([i,sumbit.sum(l-1,r)-x*numbit.sum(l-1,r)]) else: a,i=q #このときはセグメント木をupdate sumbit.update(i,a) numbit.update(i,1) les.sort() for _,d in les: print(d)