def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
def B(N, S):
S = "0" + S
for i in range(1, N):
for k in range(1, N - i + 1):
if S[k] == S[k + i]:
break
else:
print(k)
continue
print(k - 1)B(6, "abcbac")
# 5
# 1
# 2
# 0
# 1
from string import ascii_uppercase
def C(S):
ans = 0
for i, c in enumerate(S[::-1]):
ans += len(ascii_uppercase) ** i * (ascii_uppercase.index(c) + 1)
print(ans)C("AB") # 28
C("C") # 3
C("BRUTMHYHIIZP") # 10000000000000000
from collections import deque
def D(N, ST):
edge = {}
for s, t in ST:
edge[s] = t
while edge:
a, b = edge.popitem()
passed = set([a, b])
q = deque([b])
while q:
now = q.popleft()
if now not in edge:
continue
nxt = edge.pop(now)
if nxt in passed:
return "No"
else:
q.append(nxt)
passed.add(nxt)
return "Yes"test_all(D)
from collections import defaultdict
class DSU():
def __init__(self, n=None):
self.dsu = defaultdict(lambda: -1)
if n:
for i in range(n): self.dsu[i]
def leader(self, i):
if self.dsu[i] < 0: return i
self.dsu[i] = self.leader(self.dsu[i])
return self.dsu[i]
def merge(self, i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
if i == j: return
x = self.leader(i)
y = self.leader(j)
if x == y: return
if self.dsu[x] > self.dsu[y]: x, y = y, x
self.dsu[x] += self.dsu[y]
self.dsu[y] = x
def members(self, i):
l = self.leader(i)
return [k for k, v in self.dsu.items() if self.leader(k) == l]
def __len__(self):
return len([1 for v in self.dsu.values() if v < 0])from itertools import chain
def D(N, ST):
mapper = {name: i for i, name in enumerate(set(chain.from_iterable(ST)))}
dsu = DSU()
for s, t in ST:
if dsu.leader(mapper[s]) == dsu.leader(mapper[t]):
return "No"
dsu.merge(mapper[s], mapper[t])
return "Yes"
test_all(D)
from itertools import accumulate
def E(N, A):
A = [0] + A
*B, = accumulate(A[(i + 1) // 2] for i in range(N + 1))
dp = [[-1] * (N + 1) for _ in range(N + 1)]
dp[1][0] = 0
for i in range(1, N):
for j in range(N + 1):
if dp[i][j] < 0: continue
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + B[j])
res = 0
for i in range(N):
res = max(res, dp[N][i] + B[i])
return restest_all(E)
from itertools import accumulate
def E(N, A):
A = [0] + A
*B, = accumulate(A[(i + 1) // 2] for i in range(N + 1))
dp = [0]
for i in range(1, N + 1):
dp = [max(d + b for d, b in zip(dp, B))] + dp
return dp[0]test_all(E)
from itertools import accumulate
def E_debug(N, A, debug=False):
A = [0] + A
*B, = accumulate(A[(i + 1) // 2] for i in range(N + 1))
print(f"{B=}")
dp = [0]
for i in range(1, N + 1):
dp = [max(d + b for d, b in zip(dp, B))] + dp
print(i, dp)
return dp[0]E_debug(*test_dataE[0]["in"])
class BIT:
def __init__(self, a):
if hasattr(a, "__iter__"):
self.size = len(a)
self.data = [0] * self.size
self.bit = [0] * (self.size + 1)
for i, j in enumerate(a):
self.add(i, j)
elif isinstance(a, int):
self.size = a
self.data = [0] * a
self.bit = [0] * (a + 1)
else:
raise TypeError()
def add(self, i, x):
self.data[i] += x
i += 1
while i <= self.size:
self.bit[i] += x
i += i & -i
def sum(self, i):
'''Get sum of data[:i]
'''
total = 0
while i > 0:
total += self.bit[i]
i -= i & -i
return total
def get(self, x):
res = 0
i = 1
while i < (self.size + 1) / 2: i <<= 1
while i > 0:
if res + i < self.size and self.bit[res + i] < x:
x -= self.bit[res + i]
res += i
i >>= 1
res += 1
return res if res >= x else -1
def __getitem__(self, key):
return self.data[key]
def __setitem__(self, key, value):
self.add(key, value - self[key])
self.data[key] = value
def __len__(self):
return self.size
def __repr__(self):
return self.data.__repr__()
def __iter__(self):
return self.data.__iter__()from collections import defaultdict
from string import ascii_lowercase
def next_c(c):
return chr(ord(c) + 1)
def F(N, S, Q, queries):
S = list(S)
# S内に各文字が何個あるかを保持
num = defaultdict(int)
# S[i]時点で各文字のS[0]からの合計をBITで管理
abc = defaultdict(lambda: BIT(N))
# Sの任意区間が昇順かを判断するための情報を管理
## S[i-1]とS[i]が昇順であればS[i]=0、そうでなければS[i]=1
## is_sorted.sum(l + 1) == is_sorted.sum(r + 1) ならS[l:r+1]は昇順
is_sorted = BIT(N)
# 前処理
for i, c in enumerate(S):
num[c] += 1
abc[c][i] = 1
if i > 0 and S[i - 1] > c:
is_sorted[i] = 1
for q in queries:
type, *args = q.split()
if type == "1":
x = int(args[0]) - 1
c = args[1]
# 置き換えられる文字の処理
num[S[x]] -= 1
abc[S[x]][x] = 0
# 置き換える文字の処理
S[x] = c
abc[c][x] = 1
num[c] += 1
if x > 0: is_sorted[x] = 0 if S[x - 1] <= c else 1
if x < N - 1: is_sorted[x + 1] = 0 if S[x + 1] >= c else 1
else:
l, r = map(lambda x: int(x) - 1, args)
# 前処理
c_max = "a"
c_min = "z"
num_lr = defaultdict(int)
for c in ascii_lowercase:
num_lr[c] = abc[c].sum(r + 1) - abc[c].sum(l)
if num_lr[c] > 0:
c_max = max(c_max, c)
c_min = min(c_min, c)
# 昇順？
if is_sorted.sum(r + 1) == is_sorted.sum(l + 1):
# 部分文字列？
c = next_c(c_min)
while c < c_max:
if num_lr[c] != num[c]:
break
c = chr(ord(c) + 1)
else:
print("Yes")
continue
print("No")test_all(F)
AtCoder Inc.
