結果
| 問題 |
No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
|
| コンテスト | |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-07 17:27:10 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,006 ms / 5,000 ms |
| コード長 | 19,433 bytes |
| コンパイル時間 | 169 ms |
| コンパイル使用メモリ | 82,360 KB |
| 実行使用メモリ | 128,828 KB |
| 最終ジャッジ日時 | 2024-07-22 12:37:42 |
| 合計ジャッジ時間 | 9,468 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
# ref
# [1]https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b72#toc4
# [2]https://smijake3.hatenablog.com/entry/2018/11/03/100133
# [3]https://ikatakos.com/pot/programming_algorithm/data_structure/segment_tree/lazy_segment_tree
# [4]https://betrue12.hateblo.jp/entry/2020/09/22/194541
# テストケース。以下はテストケースは確認しました。TLEが多いですがどうしようもないです。AOJはpypy3が使えないですが、pypy3が使えるなら通ると思っていいと思います。例えば[t5]は通らないけど同じ問題の[t6]は通っているので。
# [t1]https://atcoder.jp/contests/arc033/tasks/arc033_3 TLE
# [t2]https://yukicoder.me/problems/no/875 TLE
# [t3]https://yukicoder.me/problems/no/877 TLE
# [t4]https://atcoder.jp/contests/abc241/tasks/abc241_d TLE
# 加えて遅延セグ木特有のテストは以下。特にt5はたくさんの基本的問題が含まれていますので、重要です。
# [t5]https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2 TLE
# [t6]https://yukicoder.me/problems/no/1234 AC
# [t7]https://yukicoder.me/problems/no/230 AC
# 実装上の工夫：
# 基本的な実装は普通のセグメント木のときと同じになります。つまり[1]を一番参考にしています。ただ[3],[4]についてもアイデアを参考にしている箇所があります。
# lazyは区間長をかけないで管理しています。すなわちlazy[k]はkが管理する区間のひとマスずつの値が入っています。これをtreeに反映するときにlengthをかけます。treeへの反映はmappingでのみ起こって、lengthはmappingの引数で与えています。これは[3]のアイデアです。
# operatorと単位元は2セットあることに注意してください。すなわち、通常のセグ木におけるoperatorとidentityの組と、作用素lazyの演算及びidentityの組です
# 例えば最小値を求めるクエリで、区間更新が加算の場合には(operator=min,identity=inf),(lazy_operator=足し算,identity=0)となります。
# 演算が三種類あることは重要です。要素をs,作用素をfとする。sはself.treeの要素で、fはself.lazyの要素と思いましょう。
# 1. s間の演算。これはself.operatorで決めたもの
# 2. f間の演算。これは上書きであればfを置き換え、加算であればfの和を求めます。[3]でいうcomposition
# 3. 要素sに作用素fを作用させる演算。これは上書きならsをfで置き換え、加算ならsとfの和を求めます。[3]でいうmapping
# 実装上は1.は引数で与え、2.,3.はメソッドとして定義してあります
# 簡単のために区間加算と区間更新しか定義していないですが、compositionあたりを適切に変えれば他の操作もできるはずです。
# よく使うoperatorと単位元,required_lengthのリスト。
"""
最小値
operator=min, identity=float('inf'),required_length=False
最大値
operator=max, identity = -float('inf'),required_length=False
区間和
operator=lambda x, y: x + y,identity = 0,required_length=True
区間積
operator=lambda x, y: x * y, identity = 1,required_length=True
最大公約数
operator=math.gcd, identity = 0
複数の要素をもたせたいときの区間和。ベクトルの和にする。このときはupdate(k,x)のxにも同じ次元のリストを入れます。
operator=lambda A, B: [a+b for a,b in zip(A,B)]
"""
#区間更新のみ可能な遅延伝搬セグメント木です。区間更新のみが可能な代わりに区間加算と両方できる遅延伝搬セグメント木よりも定数倍高速に動作します。
class OnlyUpdateLazySegmentTree:
# O(N)
# 初期化です。適切なoperatorを指定してください。また遅延伝搬セグメント木ではidentityの指定が必須になります。
def __init__(self, A, operator, identity, required_length):
"""
A:いま扱う配列
operator:いま考える二項間演算子。交換法則は仮定しない
identity:operatorに対応する単位元
required_length:区間更新の際に区間長をかけるかどうか。区間和ならTrue,区間の最小値などならFalseにします。
"""
# 1-indexedで、親:i>>1,左の子:i<<1,右の子i<<1|1です。
# 要素数
self.N = len(A)
# operator,identity
self.operator = operator
self.identity = identity
# 木を成すサイズ2Nの配列を作る。
self.tree = [None] * (self.N + self.N)
# 遅延伝搬用の配列を用意します。treeと同じサイズで、同じindexは対応します。
# またlazyはふたつめに上書きフラグを持ちます。これはupdateが入ったときはTrueにして、addのときはFalseになります。
# つまりlazy[k]=[x,True]なら、kがxになることを意味し、lazy[k]=[x,False]ならkにxが加算されていることを意味する。
self.lazy = [None]*(self.N+self.N)
# 区間長管理専用のリスト。これは__init__で生成されてから今後変更されません。区間長は全部を1にした数列の区間和と考えればよいです。
self.length = [1] * (self.N + self.N)
for i, a in enumerate(A, self.N):
self.tree[i] = a
# ふたつの子にoperatorを作用したものを親にするという操作を繰り返す。ここでindexの大きい方からやっていけば葉から上にたどることができる。
for i in range(self.N - 1, 0, -1):
self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])
# required_lengthがTrueのときは長さをいれて、不要のときはなにもしない（全部1）。
if required_length:
self.length[i] = self.length[i << 1] + self.length[i << 1 | 1]
#mappingは上書きのみ
def _mapping(self, f, s, length_f):
return f * length_f
# f,gの合成。合成順はf->g。gが存在すればgに置き換える。
def _composition(self, f, g):
if g is None:
return f
else:
return g
# kの値を返します。これは上からちゃんと順番に見ていって初めて意味があるので、get(k)とは違うことに注意してください。
def _evaluate_at(self, k):
if self.lazy[k] is None:
return self.tree[k]
else:
return self.lazy[k]*self.length[k]
#return self._mapping(self.lazy[k], self.tree[k], self.length[k])
# iで指定されたnodeの上を見て、lazyを伝搬させてきます。
def _propagate_from_above(self, i):
# i>>hがiの親のindexになります。逆順にして、上から下の順番に計算するようにします。
for h in range(i.bit_length() - 1, 0, -1):
# 逆順ループなのでi>>=1みたいにしてはいけません
k = i >> h
self.tree[k] = self._evaluate_at(k)
# lazyを子に伝搬させる。
self.lazy[k << 1] = self._composition(self.lazy[k << 1], self.lazy[k])
self.lazy[k << 1 | 1] = self._composition(self.lazy[k << 1 | 1], self.lazy[k])
# 反映させたlazyはリセットする。
self.lazy[k] = None
# iの上部を再計算します。
def _recalc_above(self, i):
while i > 1:
i >>= 1
self.tree[i] = self.operator(self._evaluate_at(i << 1), self._evaluate_at(i << 1 | 1))
# O(log(N))
# Aのk番目の値A[k]をxに変更します。
def update(self, k, x):
# updateの場合はしっかりとlazyをおろした上で考える必要があります。
# lazyを経由しないで直接treeを更新すればいいです。
k += self.N
# propagationが必要
self._propagate_from_above(k)
# treeを直接更新
self.tree[k] = x
# 再計算
self._recalc_above(k)
# O(log(N))
# Aのk番目の値A[k]にxを加算します。すなわちA[k]+=xと同じ操作です。
def add(self, k, x):
# 加算の場合はlazyは無視してtreeに直接加算すればいいだけ。
k += self.N
# 加算
self.tree[k] += x
while k > 1:
k >>= 1
self.tree[k] = self.operator(self.tree[k << 1], self.tree[k << 1 | 1])
# O(log(N))
# Aの[left,right)の部分をxに変更します。
def update_range(self, left, right, x):
if left is None:
left = 0
if right is None:
right = self.N
left += self.N
right += self.N
L0 = left // (left & -left)
R0 = right // (right & -right) - 1
# updateクエリでは最初にpropagateが必要です。
self._propagate_from_above(L0)
self._propagate_from_above(R0)
# lazyを更新する。クエリと同じような感じです。
while left < right:
if left & 1:
# print(self.lazy[left])
self.lazy[left] = self._composition(self.lazy[left], x)
left += 1
if right & 1:
right -= 1
self.lazy[right] = self._composition(self.lazy[right], x)
left >>= 1
right >>= 1
# lazyを計算したら上部の再計算が必要です。これは単にL0,R0からスタートして、親に向かって更新していくだけです。
self._recalc_above(L0)
self._recalc_above(R0)
# O(log(N))
# 半開区間[left,right)において、operatorで指定された演算の値を返します。
# ただしleft,rightにNoneを入力すると、例えばleft=Noneにするといまありうる一番左を指定します
def query(self, left, right):
if left is None:
left = 0
if right is None:
right = self.N
# left,rightに対応するtreeのindex
left += self.N
right += self.N
# queryを実行する前に、lazyを上から持ってきます。
self._propagate_from_above(left // (left & -left))
self._propagate_from_above(right // (right & -right) - 1)
# 左右の値
vl = self.identity
vr = self.identity
# 非再帰の実装ではleaf側からrootに向かっていくのがポイントです。[2]の図がわかりやすいです。
# [left,right)の外側から値を確定させていくイメージ。どんどん内側によせていき、leftとrightが重なったら終わり
while left < right:
if left & 1:
# leftが奇数なら、その区間を確定させる。
vl = self.operator(vl, self._evaluate_at(left))
# 次は右の親に移動するのでLを足しておく
left += 1
if right & 1:
# rightが奇数なら、-1してから確定させる
right -= 1
# 順番には注意ね
vr = self.operator(self._evaluate_at(right), vr)
# 親を見る
left >>= 1
right >>= 1
# 最後にvlとvrの演算を返す。ここでも演算の順番に注意
return self.operator(vl, vr)
# O(log(N))
# A[k]と同じ。もとのAのk番目の値を取得します。ふつうのセグメント木と違ってO(log(N))なので注意。
def get(self, k):
# propagateした上でevaluate_atで取得する必要がある。
k += self.N
self._propagate_from_above(k)
return self._evaluate_at(k)
##############################################
# テストの実行
##############################################
# [t1]
"""
Q = int(input())
query = []
for _ in range(Q):
query.append(tuple(map(int, input().split())))
lst=LazySegmentTree([0]*200001,operator=lambda x,y:x+y,identity=0,required_length=True)
for t,x in query:
if t==1:
#なぜかupdateでも通ったけどaddにするのがただしいと思う
lst.add(x,1)
else:
left=0
right=200001
while left+1<right:
mid=left+(right-left)//2
if lst.query(0,mid)>=x:
#このときは左による
right=mid
else:
left=mid
#leftの削除も必要です。いまの場合削除とは0にすることにほかならないので
lst.update(left,0)
print(left)
"""
# [t2]
"""
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())))
pos={}
for i,a in enumerate(A):
pos[a]=i
lst=LazySegmentTree(A,operator=min,identity=float('inf'),required_length=False)
for flag,l,r in query:
if flag==0:
#このときl,rを交換する。posも交換しないといけないことに注意
pos[lst.get(l)],pos[lst.get(r)]=pos[lst.get(r)],pos[lst.get(l)]
#セグメント木でも交換する
work=lst.get(l)
lst.update(l,lst.get(r))
lst.update(r,work)
else:
#最小値は
print(pos[lst.query(l,r+1)]+1)
"""
# [t3]
"""
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)
# 区間和のセグメント木と区間の要素数のセグメント木をどちらも用意します
sumlst=LazySegmentTree([0]*N,operator=lambda x,y:x+y,identity=0,required_length=True)
numlst=LazySegmentTree([0]*N,operator=lambda x,y:x+y,identity=0,required_length=True)
les=[]
for q in query:
if len(q)==4:
x,l,r,i=q
#このとき区間の和を求める。和から要素数*xを引きます
les.append([i,sumlst.query(l-1,r)-x*numlst.query(l-1,r)])
else:
a,i=q
#このときはセグメント木をupdate
sumlst.update(i,a)
numlst.update(i,1)
les.sort()
for _,d in les:
print(d)
"""
# [t4]
"""
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)
lst = LazySegmentTree([0] * (len(x2comp) + 1), operator=lambda x, y: x + y, identity=0, required_length=True)
# セグメント木の言葉でいうと、まず全要素のうちk番目に小さい要素とは、区間和[0,i]がkになるような最小のiということになります。
# なのでx以上の要素のうち大きい方からk番目の値とは区間和[x,i]がkになるようなiのうち最小の値となります。
for query in queries:
if query[0] == 1:
lst.add(x2comp[query[1]], 1)
elif query[0] == 2:
_, x, k = query
x = x2comp[x]
# 区間和[i,x+1)がkになるようなiのうち最大のiを求める
if lst.query(None, x + 1) < k:
print(-1)
else:
left = 0
right = x + 1
while left + 1 < right:
mid = left + (right - left) // 2
if lst.query(mid, x + 1) >= k:
left = mid
else:
right = mid
# leftが答えです
print(comp2x[left])
else:
_, x, k = query
x = x2comp[x]
# 区間和[x,i]がkになるような最小のiを二分探索します
if lst.query(x, None) < k:
# このとき存在しない
print(-1)
else:
left = x
right = len(x2comp) + 1
while left + 1 < right:
mid = left + (right - left) // 2
if lst.query(x, mid) >= k:
# このときは左による
right = mid
else:
left = mid
# leftが答えです
print(comp2x[left])
"""
# [t5]RMQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([(1<<31)-1]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
if q[0]==0:
_,i,x=q
lst.update(i,x)
else:
_,s,t=q
print(lst.query(s,t+1))
"""
# [t5]RSQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
if q[0]==0:
_,i,x=q
lst.add(i-1,x)
else:
_,s,t=q
print(lst.query(s-1,t))
"""
# [t5]RUQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([(1<<31)-1]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
if q[0]==0:
_,s,t,x=q
lst.update_range(s,t+1,x)
else:
_,i=q
print(lst.get(i))
"""
# [t5]RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([0]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
if q[0]==0:
_,s,t,x=q
lst.add_range(s-1,t,x)
else:
_,i=q
print(lst.get(i-1))
"""
# [t5]RMQ and RUQ
"""
n, q = map(int, input().split())
queries = []
for _ in range(q):
queries.append(list(map(int, input().split())))
lst = LazySegmentTree([2**31-1] * n, operator=min, identity=float('inf'),required_length=False)
for q in queries:
if q[0] == 0:
_, s, t, x = q
lst.update_range(s, t + 1, x)
else:
_, s, t = q
print(lst.query(s, t + 1))
"""
# [t5]RSQ and RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
if q[0]==0:
_,s,t,x=q
lst.add_range(s-1,t,x)
else:
_,s,t=q
print(lst.query(s-1,t))
"""
# [t5]RMQ and RAQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([0]*n,operator=min,identity=float('inf'),required_length=False)
for q in queries:
if q[0]==0:
_,s,t,x=q
lst.add_range(s,t+1,x)
else:
_,s,t=q
print(lst.query(s,t+1))
"""
# [t5]RSQ and RUQ
"""
n,q=map(int,input().split())
queries=[]
for _ in range(q):
queries.append(list(map(int,input().split())))
lst=LazySegmentTree([0]*n,operator=lambda x,y:x+y,identity=0,required_length=True)
for q in queries:
if q[0]==0:
_,s,t,x=q
lst.update_range(s,t+1,x)
else:
_,s,t=q
print(lst.query(s,t+1))
"""
# [t6]
"""
N=int(input())
a=list(map(int,input().split()))
Q=int(input())
queries=[]
for _ in range(Q):
queries.append(list(map(int,input().split())))
lst = LazySegmentTree(a, operator=min, identity=float('inf'),required_length=False)
for q in queries:
if q[0]==1:
_,l,r,c=q
lst.add_range(l-1,r,c)
else:
_,l,r,_=q
print(lst.query(l-1,r))
"""
# [t7]
N=int(input())
Q=int(input())
queries=[]
for _ in range(Q):
queries.append(tuple(map(int,input().split())))
#Aを1,Bを-1で更新するセグ木とAを2,Bを-1で更新するセグ木を用意します。すると[left,right)のAの数をこのふたつの差で求めることができます
lst1=OnlyUpdateLazySegmentTree([0]*N,operator=lambda x,y:x+y,identity=0,required_length=True)
lst2=OnlyUpdateLazySegmentTree([0]*N,operator=lambda x,y:x+y,identity=0,required_length=True)
scoreA=0
scoreB=0
for x,l,r in queries:
if x==0:
#ボーナスチャンス
sum1=lst1.query(l,r+1)
sum2=lst2.query(l,r+1)
#区間内のAで塗られた数とBで塗られた数は
cntA=sum2-sum1
cntB=cntA-sum1
if sum1==0:
continue
elif sum1>0:
#このときAのほうが多いのでAにボーナス
scoreA+=max(cntA,cntB)
else:
scoreB+=max(cntA,cntB)
elif x==1:
#Aが塗る
lst1.update_range(l,r+1,1)
lst2.update_range(l,r+1,2)
else:
lst1.update_range(l,r+1,-1)
lst2.update_range(l,r+1,-1)
#ラストスコアの加算
sum1=lst1.query(0,N)
sum2=lst2.query(0,N)
#区間内のAで塗られた数とBで塗られた数は
cntA=sum2-sum1
scoreA+=cntA
scoreB+=cntA-sum1
print(scoreA,scoreB)