問題
回文のレベルを以下のように定める(正確には問題ページ参照)
文字列 $S$ と整数 $K$ が与えられる
$S$ を、いくつかの文字を書き換えることでちょうどレベル $K$ の文字列にできるか判定し、できる場合は書き換える必要のある最小の文字数を求めよ
$0 \le K \le 5 \times 10^5$
$1 \le |S| \le 5 \times 10^5$
解法
レベル1の回文で同じにならないといけない文字を考えると、以下のようになる。
|S| = 18 とすると、同じ高さになったindexの文字は同じである必要がある
0 17
1 16
2 15
3 14
4 13
5 12
6 11
7 10
8 9
レベル2の回文では、さらに以下の文字が同じである必要がある。
0 8 9 17
1 7 10 16
2 6 11 15
3 5 12 14
4 13
レベル3では
0 3 5 8 9 12 14 17
1 2 6 7 10 11 15 16
4 13
レベル4……と思いきや、これはレベル5
0 1 2 3 5 6 7 8 9 10 11 12 14 15 16 17
4 13
各表現は、最初の折り返し直前までの文字列(レベル1なら 012345678
、レベル2なら 0123
、レベル3なら 01
)がレベル0である(回文でない)ことを前提としているが、
レベル4のように折り返し直前までの文字列が1文字だけになったら、これはレベル1の文字列となってしまう。
よってその場合のみ、レベルが1ずれる。レベル4の文字列は作るのが不可能となる。またレベル6以上も長さ18の $S$ では作るのが不可能とわかる。
一般に、$|S|$ を2で割っていって、「1以外の、0になるまでのレベル」を作ることができる。
レベル 0 1 2 3 4 5 6 7
18 9 4 2 1 0
作れる o o o o x o x x ...
このように同じにならなければならない箇所は $S$ の中身によらず、$K$ と $|S|$ のみから決まるので、まずそれを求める。
(考えるのが面倒だったのでUnion-Find木を使ったが、多分ちゃんと計算すれば $O(|S|)$ で求められるはず)
そして、同じグループごとに $S$ から文字の出現回数を数えて、元からあるのが一番多い文字にそろえるのが、変更が一番小さくなる。
しかし、「ちょうど」レベル $K$ にしなければいけない。
レベルが過剰になってしまうというのは、たとえば上記の例でレベル2にしたいのに、
一番多い文字を採用すると $S_{0~3}$ が回文になってしまうようなケース。その場合レベル3以上となってしまう。
そのため、各グループ「何の文字に変更したか」「1番目でなく2番目に出現回数の多い文字を採用した場合、書き換える必要のある文字数は1番目を採用した場合から何文字増えるかの差分」を記録する。
回文となってはいけない場所が、変更の結果、回文となってしまっていないか確認し、
なっているなら差分のうち一番小さいものを2番目の文字に書き換えて回文を崩す。
そうするとちょうどレベル $K$ が保証される。
Python3
from collections import defaultdict, Counter
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def root(self, x):
stack = []
tbl = self.table
while tbl[x] >= 0:
stack.append(x)
x = tbl[x]
for y in stack:
tbl[y] = x
return x
def find(self, x, y):
return self.root(x) == self.root(y)
def unite(self, x, y):
r1 = self.root(x)
r2 = self.root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
else:
self.table[r1] = r2
self.table[r2] += d1
def get_size(self, x):
return -self.table[self.root(x)]
k = int(input())
s = input()
r = len(s)
uft = UnionFind(len(s))
for _ in range(k):
if r == 0:
print('impossible')
exit()
for i in range(r // 2):
uft.unite(i, r - i - 1)
r >>= 1
if r == 1:
print('impossible')
exit()
rrr = defaultdict(set)
for i in range(len(s)):
rrr[uft.root(i)].add(i)
ans = 0
ccc = {}
for t, grp in rrr.items():
cnt = Counter(map(s.__getitem__, grp))
a = cnt.most_common(2)
if len(a) == 1:
ccc[t] = [a[0][0], len(grp)]
else:
ccc[t] = [a[0][0], a[0][1] - a[1][1]]
ans += len(grp) - a[0][1]
if r == 0:
print(ans)
exit()
ng = True
replace = 1 << 60
for i in range(r // 2):
r1 = uft.root(i)
r2 = uft.root(r - i - 1)
if ccc[r1][0] != ccc[r2][0]:
ng = False
break
replace = min(replace, ccc[r1][1], ccc[r2][1])
if ng:
ans += replace
print(ans)
問題
長さ $N$ の数列 $a$ と、長さ $M$ の数列 $b$ がある
最初、$a,b$ の要素は全て $0$
$Q$ 個のクエリを処理する。$i$ 個目のクエリでは $T_i,X_i,Y_i$ が与えられる
$T_i=1$ のとき、$a_{Xi}$ を $Y_i$ に置き換える
$T_i=2$ のとき、$b_{Xi}$ を $Y_i$ に置き換える
毎回のクエリの処理直後に $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \max(a_i,b_j)$ の値を出力する
$1 \le N,M \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$1 \le Y_i \le 10^8$
解法
最初、全要素が0なので答えは言うまでも無く0。
たとえば $a$ の1個 $a_i$ を $5$ から $10$ に変えたときに、全体の答えがどうなるか考えると、
これで全て。
なので、差分だけ更新していくことで、クエリに高速に答えられそう。
なお、$10$ から $5$ に変わるなど値が減少するときは、3つめの増加と減少が逆転する。
範囲の個数や総和を求めたいので、セグメント木やFenwick Treeで管理すればよい。
「$a$ 用、$b$ 用」「個数用、総和用」で合計4つ、必要になる。
$Y_i$ の取り得る範囲が $10^8$ と大きいので、座標圧縮の必要がある。
今回は「$a_i$ を $Y_{old}$ から $Y_{new}$ に変えるとき、この間の個数や総和」が求まればよい、つまり $Y_i$ の大小関係さえ保たれていれば範囲指定できるので、
$Y_i$ として出てくる値をソートして小さい順に $0,1,2,...$ に対応させれば、$Q$ の長さ $2 \times 10^5$ として扱うことができる。
範囲の境界(以下なのか未満なのか、など)に注意。
どちらでもよいが、$a_i=b_j$ となる $b_j$ があり、今まで $\max(a_i,b_j)=b_j$ だった場合、それを「$\max(a_i,b_j)=a_i$ に変わったと見なし、更新対象に含めるのか(同じ値が引かれ、足されるので実質は変化ない)」「変化無しとして更新対象に含めないのか」は、3種類の更新の中で統一しておく必要がある。
Python3
from operator import add
class FenwickTreeInjectable:
def __init__(self, n, identity_factory, func):
self.size = n
self.tree = [identity_factory() for _ in range(n + 1)]
self.func = func
self.idf = identity_factory
self.depth = n.bit_length()
def add(self, i, x):
i += 1
tree = self.tree
func = self.func
while i <= self.size:
tree[i] = func(tree[i], x)
i += i & -i
def sum(self, i):
i += 1
s = self.idf()
tree = self.tree
func = self.func
while i > 0:
s = func(s, tree[i])
i -= i & -i
return s
n, m, q = map(int, input().split())
y_appear = set()
queries = []
for _ in range(q):
t, x, y = map(int, input().split())
y_appear.add(y)
queries.append((t - 1, x - 1, y))
compress = {y: i + 1 for i, y in enumerate(sorted(y_appear))}
compress[0] = 0
fwt = [
{
'count': FenwickTreeInjectable(len(compress) + 5, int, add),
'total': FenwickTreeInjectable(len(compress) + 5, int, add),
},
{
'count': FenwickTreeInjectable(len(compress) + 5, int, add),
'total': FenwickTreeInjectable(len(compress) + 5, int, add),
},
]
fwt[0]['count'].add(0, n)
fwt[1]['count'].add(0, m)
current = [[0] * n, [0] * m]
buf = []
ans = 0
for t, x, y in queries:
i = compress[y]
z = current[t][x]
j = compress[z]
get = fwt[t ^ 1]['count'].sum(i) * y
loss1 = fwt[t ^ 1]['count'].sum(j - 1) * z
loss2 = fwt[t ^ 1]['total'].sum(i) - fwt[t ^ 1]['total'].sum(j - 1)
ans += get - loss1 - loss2
fwt[t]['count'].add(i, 1)
fwt[t]['count'].add(j, -1)
fwt[t]['total'].add(i, y)
fwt[t]['total'].add(j, -z)
current[t][x] = y
buf.append(ans)
print('\n'.join(map(str, buf)))