E.Simple String Queries
難易度 : 1443
考察
type1 は 一点更新、type2は 区間取得 問題です。したがって、このクエリを高速に処理するためには Segment Tree を利用するのが良さそうです。
あとは、区間に登場するアルファベットの種類をどうやって管理するかを考えます。これにはいくつかの手段があります。
解法➀ アルファベットごとにセグ木を持つ
欲張って全てのアルファベットについて同時に考えようとするから状況が難しくなっています。
それよりも、アルファベットごとに独立に考えるほうが簡単です。つまり、区間 $[l,r)$ 内に対象のアルファベットが含まれるか(存在するか) を求めることにします。
そのためにはアルファベットごとに管理仕分ける必要があるので、26本のセグメントツリーを作成します。
$S[i] = a $ なら $a$ に対応するセグメント木の $i$ 番目の位置に $1$ をたてて存在を表現します。更新関数を $max()$ , 単位元を $0$ とすれば、その区間の内部に $a$ が存在すれば $1$ 、そうでなければ $0$ が返るようになります。これをアルファベットごとに足し合わせることで、その区間に含まれる種類を求めることができるようになりました。
計算量は全体で $O(NlogN + Q×(26×logN))$ で十分高速です。
コード
pypy3
880ms / 2000ms
# 単位元
def e():
return 0
# 更新関数
def op(a,b):
return max(a,b)
ここにセグ木クラス書く
if __name__ == "__main__":
N=int(input())
S=input()
Q=int(input())
# アルファベットごとにセグメントツリーを作成。i文字目がそのアルファベットかを 0,1 で表現する
STs=[]
for _ in range(26):
ST=SegTree(op, e, N,[0]*(N))
STs.append(ST)
# 初期 S でセグメントツリーを更新
for i in range(N):
x=ord(S[i])-ord("a")
STs[x].set(i,1)
Snow=[]
for s in S:
Snow.append(s)
for _ in range(Q):
Q=[q for q in input().split()]
if Q[0]=="1":
i,c=int(Q[1]),Q[2]
i-=1
# S[i] ⇒ c に変更
x1=ord(Snow[i])-ord("a")
STs[x1].set(i,0)
x2=ord(c)-ord("a")
STs[x2].set(i,1)
# Sを更新
Snow[i]=c
else:
l,r=int(Q[1]),int(Q[2])
l-=1
ans=0
# [l,r) 区間の種類数を求めるために、全てのセグメントツリーを調べる
for i in range(26):
ans+=STs[i].prod(l, r)
print(ans)
解法➁ bit で種類を表現
素直に種類を集合で管理すると、和集合で区間に含まれる種類を更新していくことになりますが、この場合計算量は全体で $O(N×(26×logN) + Q×(26×logN))$ になってしまいます。定数倍部分が重くて間に合うか微妙です。※1
そこで、アルファベットの種類を 26桁の2進数で表現することにします。例えば、$1010(2) ⇔$ { $\ d,b$ } , $1(2)$ ⇔ {$\ a\ $} といった具合です。
bit 和をとることで種類を更新できるので、更新関数は bit和 , 単位元 は $0$ とすればよいです。
これであれば解法➀ と同じ計算量になって十分高速です。
コード
pypy
292ms / 2000ms
# 単位元
def e():
return 0
# 更新関数
def op(a,b):
return a|b
ここにセグ木クラスを書く
if __name__ == "__main__":
N=int(input())
S=input()
Q=int(input())
ST=SegTree(op, e, N,[0]*(N))
# 初期 S でセグメントツリーを更新
for i in range(N):
x=ord(S[i])-ord("a")
ST.set(i,1<<x)
for _ in range(Q):
Q=[q for q in input().split()]
if Q[0]=="1":
i,c=int(Q[1]),Q[2]
i-=1
x=ord(c)-ord("a")
ST.set(i, 1<<x)
else:
l,r=int(Q[1]),int(Q[2])
l-=1
bit=ST.prod(l, r)
ans=0
for i in range(26):
if bit>>i & 1:
ans+=1
print(ans)
セグ木クラス
# 最下層は (0 + 最下層サイズ)-indexed
class SegTree:
def __init__(self, op, e, n, v=None):
self._n=n
# 演算関数
self._op = op
# 単位元
self._e = e
# n ≦ 2^x を満たす最小のx
self._log = len(f"{(self._n)-1:b}")
# 最下層頂点数 = 2^(桁数)
self._size = 1 << self._log
# テーブルサイズ (全頂点数は 2×サイズ であるが、1-indexdedのための調整で +1する)
# 単位元で初期化
self._d = [self._e()] * (2 * self._size)
if v is not None:
# 最下層の初期化
for i in range(self._n):
self._d[self._size + i] = v[i]
# 上の階層の初期化(親の更新)
for i in range(self._size - 1, 0, -1):
self._d[i] = self._op(self._d[i << 1], self._d[i << 1 | 1])
# 一点更新
def set(self, p, x):
p += self._size
self._d[p] = x
while p:
self._d[p >> 1] = self._op(self._d[p], self._d[p ^ 1])
p >>= 1
# 区間取得
# l,r は0-indexed
def prod(self, l, r):
tmp_l, tmp_r = self._e(), self._e()
l += self._size
r += self._size
while l < r:
# 現在頂点を含める必要がない場合はスルーしても OK (親を使えばよいから)
# そうでない場合は現在頂点を区間に含めて、より内側の親へ移動させる
# ➀ 左端 (左の子なら)
if l & 1:
tmp_l = self._op(tmp_l, self._d[l])
# 内側へ移動
l += 1
# ➁ 右端 (右の子なら) (区間の右端が左の子ならば内側に移動するが、これは r が右の子の場合である)
if r & 1:
# r は区間に含まれない
r -= 1
tmp_r = self._op(self._d[r], tmp_r)
# 親へ移動
l >>= 1
r >>= 1
return self._op(tmp_l, tmp_r)
# 全区間 = 根
def all_prod(self):
return self._d[1]
# 最下層の値を取得
def get(self, p):
return self._d[p + self._size]
補足
-
Segment Tree
【Segtree編】AtCoder Library 解読 〜Pythonでの実装まで〜
コードの Segment Tree クラスはこの記事で紹介されているものをほぼ丸パクリしているので、わからないところはこちらで調べてください。めちゃくちゃ丁寧でわかりやすいです。Segment Tree のお勉強(1)
わかりやすい図によって、操作を視覚的に理解することができます。こちらもおすすめです。 -
解法➁
公式 Twitter 解説 -
※1
筆者は TLE しました
終わり
基本的には A問題からまとめて記事にするつもりですが、気分でこのように単体でも記事にします。
質問やご指摘はこちらまで
Twitter : Waaa1471