# ref # 実装は基本的に[2],[3]を参照。ただし0-indexedにしているところとidentityの指定を不要にしているところだけ少し違う # [1]https://qiita.com/R_olldIce/items/32cbf5bc3ffb2f84a898 # [2]https://maspypy.com/segment-tree-%E3%81%AE%E3%81%8A%E5%8B%89%E5%BC%B71 # [3]https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf # テストケース。以下はぜんぶ通しました。 # [t1]https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A&lang=jp # [t2]https://atcoder.jp/contests/arc033/tasks/arc033_3 # [t3]https://judge.yosupo.jp/problem/staticrmq # [t4]https://yukicoder.me/problems/no/875 # [t5]https://yukicoder.me/problems/no/877 # 実装上の工夫： # 非再帰（パフォーマンス（メモリ、時間ともに）上微妙にいい、stackで書いたものとかではない） # nodeの数を2のべきにしない（微妙にメモリ節約。あと無駄なものを持たなくていいので微妙に気持ちがいい） # またnodeの数を2のべきにしなくていいと、identityの指定が不要になり、うれしい（ただしidentityの指定を不要にするとqueryの実装はちょっとだけ複雑になる）。 # 交換法則は仮定しない（ただし結合法則は仮定される、例えば引き算や割り算は結合法則が満たされないためだめ、行列の積とかはいける） # 0-indexed（[3]に0-indexedだと親子の添字を求めるのが面倒とあるがそんなことはない。ただbitシフトだけではできないのでかすかにパフォーマンスが下がる可能性はある） # よく使うoperatorと単位元のリスト。 """ 最小値 operator=min, identity=float('inf') 最大値 operator=max, identity = -float('inf') 区間和 operator=lambda x, y: x + y,identity = 0 区間積 operator=lambda x, y: x * y, identity = 1 最大公約数 operator=math.gcd, identity = 0 """ # セグメント木のクラス。構築O(N),update O(log(N)),query O(log(N)) class SegmentTree: # O(N) # 初期化です。デフォルトはRMQにしてあります。適切なoperatorを指定してください。 def __init__(self, A, operator=min): """ A:いま扱う配列 operator:いま考える二項間演算子。交換法則は仮定しない identity:operatorに対応する単位元 """ # ちなみに0-indexでnode iの親:(i-1)//2,左の子:2*i+1,右の子:2*i+2です。 # ほとんど意味はないと思うが、bit演算のほうがかすかに速いきがするので、親:(i-1)>>1,左の子:i<<1|1,右の子(i<<1)+2と書くことにする。 # セグメント木は完全二分木ですから、リストで木の要素を管理することができます。 # 要素数 self.N = len(A) # operator self.operator = operator # 木を成すサイズ2N-1の配列を作る。このときidentityで初期化する self.tree = [None] * (2 * self.N) # 初期化は葉、すなわちtreeの後ろからN個の部分にAの値を配置する。 for i, a in enumerate(A, self.N): self.tree[i] = a # たつの子にoperatorを作用したものを親にするという操作を繰り返す。ここでindexの大きい方からやっていけば葉から上にたどることができる。 for i in range(self.N - 1, 0, -1): # [0,N-2]の逆順ループ。親の値をふたつの子のoperatorから決めます。ここで左右という順番でいれないとだめなことには注意ね。 self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1|1]) # O(log(N)) # Aのk番目の値をxに変更します。 def update(self, k, x): # A[k]に対応するのはtree[k+self.N-1]ですので、そこから初めてrootに到達するまで親に向かいます k += self.N # 更新 self.tree[k] = x # rootはk=0ですので正である間ループすればOKです while k > 1: # 親のindex。 k>>=1 # 親の値を書き直す self.tree[k] = self.operator(self.tree[k << 1], self.tree[k << 1|1]) # O(log(N)) # 半開区間[left,right)において、operatorで指定された演算の値を返します。 def query(self, left, right): # left,rightに対応するtreeのindex left += self.N right += self.N # 左右の値 vl = None vr = None # 非再帰の実装ではleaf側からrootに向かっていくのがポイントです。[2]の図がわかりやすいです。 # [left,right)の外側から値を確定させていくイメージ。どんどん内側によせていき、leftとrightが重なったら終わり while left < right: if left & 1: # leftが偶数なら、その区間を確定させる if vl is None: # 何もなければその値自体を入れる vl = self.tree[left] else: # あればもとの値と演算 vl = self.operator(vl, self.tree[left]) # 次は右の親に移動するのでLを足しておく left += 1 if right & 1: # rightが偶数なら、-1してから確定させる right -= 1 if vr is None: vr = self.tree[right] else: # 積の順番には注意ね vr = self.operator(self.tree[right], vr) # 親を見る left >>=1 right >>=1 # 最後にvlとvrの演算を返す。ただしどちらもNoneなら、区間が空集合になっているのでNoneを返す。片側がNoneならNoneじゃないほうを返すことにする。 if vl is None and vr is None: return None elif vl is None: return vr elif vr is None: return vl else: # ここでも演算の順番に注意 return self.operator(vl, vr) # O(1) # A[k]と同じ。もとのAのk番目の値を取得します。 def get(self, k): return self.tree[k + self.N] ############################################################ ################以下はテスト用のコード######################## ############################################################ # 隣接行列を入力することで出力します。ただしweightがTrueのときはweightを出力します。 def visualize(edges, dir, weight=False, root=0, labels=None, idx_perm=(0, 1)): """ edges: 隣接リスト。ただしweight=Trueのときは[weight,node]という風に入っている必要がある dir: 有向グラフかどうか weight:グラフの重みを出力するかどうか root:木構造のときにはrootで設定したnodeがrootになるように出力します。ただし無向グラフのときのみ意味を持つ labels:大きさNの配列で各node番号に対してこのリストの名前で表示される。指定しない場合はnode番号がそのまま表示される idx_perm:隣接リストに[weight,node]という順番で入っているなら(0,1)にして逆なら(1,0)にします。その他の場合にもidx_perm[0]をweightのindex,idx_perm[1]をnode番号のidxにします。 """ # importを函数内で実行することで、visualize函数を書いたまま提出してもREがでなくなります。もちろん実行したらREになります。 import graphviz # dirをみてDigraphかGraphかを決める if dir: G = graphviz.Digraph(format='png') else: G = graphviz.Graph(format='png') # labelsがNoneなら if labels is None: labels = [str(i) for i in range(len(edges))] # nodeの形状を決めちゃう。 G.attr('node', style='filled', color='orange') # nodeを作る。edgeを作ればかってにできるが、labelsをいれるために必要。 for i, label in enumerate(labels): G.node(str(i), label=label) w_idx, n_idx = idx_perm # edgeを作る。nodeはedgeを作ると自動的に生成されるので明示的に作る必要はない if dir: # 有向グラフ if weight: # このときは[weight,node]というふうに入っている前提です for u, edge in enumerate(edges): for e in edge: weight, v = e[w_idx], e[n_idx] # uからvにひく G.edge(str(u), str(v), label=str(weight)) else: # このときは[node]と入っているか[weight]と入っているかは区別分岐させます。 for u, edge in enumerate(edges): for v in edge: if isinstance(v, (list, tuple)): # このときはnodeのほうを取ります v = v[n_idx] G.edge(str(u), str(v)) else: # 無効グラフの場合はu,vとv,uがどっちも隣接リストに入っているので、二回入れないように気をつけます seen = [False] * len(edges) # rootから深さ優先で下っていくような感じでedgeにいれていく必要があります。そうしないと表示が綺麗な木にならないので def dfs(n): seen[n] = True for next in edges[n]: if weight: # 重みも出力する場合です if not seen[next[n_idx]]: G.edge(str(n), str(next), label=str(next[w_idx])) # 再帰実行 dfs(next[n_idx]) else: # 重みは出さない場合です。 if isinstance(next, (list, tuple)): next = next[n_idx] if not seen[next]: # n->nextとedgeを作る必要がある G.edge(str(n), str(next)) # 再帰実行 dfs(next) # rootから実行 dfs(root) # 間違えてこのまま提出しないように print("debug mode") # 表示 G.view() # visualizeを使うためにtreeからedgesとlabelsを求めるメソッドです。graphvizだと先にいれたほうが左の個になるので、そうなるようにする def tree_to_edges(tree): edges = [[] for _ in range(len(tree))] for i in range((len(tree) + 1) // 2 - 1): left, right = 2 * i + 1, 2 * i + 2 edges[i].append(left) edges[i].append(right) labels = [str(t) for t in tree] return edges, labels # 以下のようにvisualizeできます #edges, labels = tree_to_edges(st.tree) #visualize(edges, dir=False,labels=labels) ############################################## # テストの実行 ############################################## # [t1] # n,q=map(int,input().split()) # query=[] # for _ in range(q): # query.append(list(map(int,input().split()))) # A=[2**31-1]*n # st=SegmentTree(A,operator=min) # for com,x,y in query: # if com==0: # st.update(x,y) # else: # print(st.query(x,y+1)) # [t2] #Q = int(input()) #query = [] # for _ in range(Q): # query.append(tuple(map(int, input().split()))) # 累積和のセグメント木を考えます # SにXを追加することをupdate(X,1)とします。するとSにある数字でX番目に小さい数は二分探索でも求まります。 # なぜならx番目に小さい数字はst.query(0,i)をiの配列と思ったときにxをbisect_left的に二分探索して、そのときのiが答えになっているからです # 最初は[0]の配列をいれておく #st=SegmentTree([0]*200001,operator=lambda x,y:x+y) # for t,x in query: # if t==1: # st.update(x,1) # else: # left=0 # right=200001 # while left+1=x: # #このときは左による # right=mid # else: # left=mid # #leftの削除も必要です。いまの場合削除とは0にすることにほかならないので # st.update(left,0) # print(left) # [t3] # N,Q=map(int,input().split()) # a=list(map(int,input().split())) # query=[] # for _ in range(Q): # query.append(tuple(map(int,input().split()))) # st=SegmentTree(a,min) # for l,r in query: # print(st.query(l,r)) # [t4] # N,Q=map(int,input().split()) # A=list(map(int,input().split())) # query=[] # for _ in range(Q): # query.append(tuple(map(lambda x:int(x)-1,input().split()))) # aはすべて異なるので、ある数字の場所を別に覚えておけばいい # pos={} # for i,a in enumerate(A): # pos[a]=i # セグメント木 # st=SegmentTree(A,operator=min) # for flag,l,r in query: # if flag==0: # #このときl,rを交換する。posも交換しないといけないことに注意 # pos[st.get(l)],pos[st.get(r)]=pos[st.get(r)],pos[st.get(l)] # #セグメント木でも交換する # work=st.get(l) # st.update(l,st.get(r)) # st.update(r,work) # else: # #最小値は # print(pos[st.query(l,r+1)]+1) #[t5] #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) ##区間和のセグメント木と区間の要素数のセグメント木をどちらも用意します #sumst=SegmentTree([0]*N,operator=lambda x,y:x+y) #numst=SegmentTree([0]*N,operator=lambda x,y:x+y) #les=[] #for q in query: # if len(q)==4: # x,l,r,i=q # #このとき区間の和を求める。和から要素数*xを引きます # les.append([i,sumst.query(l-1,r)-x*numst.query(l-1,r)]) # else: # a,i=q # #このときはセグメント木をupdate # sumst.update(i,a) # numst.update(i,1) #les.sort() #for _,d in les: # print(d) #[t5_2] #t5の別解です。ふたつセグメント木を用意しないで、nodeにリストをもたせる。 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) #リストの加算を定義する def sumvec(A,B): return [A[0]+B[0],A[1]+B[1]] #リストを要素として初期化し、operatorにはsumvecをセットする。[0]を要素のvalueで[1]を要素数のカウントのために使うやつだとする。 st=SegmentTree([[0,0] for _ in range(N)],operator=sumvec) les=[] for q in query: if len(q)==4: x,l,r,i=q #このとき区間の和を求める。和から要素数*xを引きます sumv,cntv=st.query(l-1,r) les.append([i,sumv-x*cntv]) else: a,i=q #このときはセグメント木をupdate st.update(i,[a,1]) les.sort() for _,d in les: print(d)