[ABC331] F - Palindrome Query
考察
0. 回文を高速に判定する技あるかな？何も思いつかない。トリッキーな工夫の余地がないように見える。
ものすごく単純に「文字列Sの切り出しと、逆さ文字列Tの切り出しが同一か比較する」を回答する。この方法を軸に高速化できないか考える。
int main() {
ll N, Q;
string S, T;
cin >> N >> Q >> S;
T = S;
reverse(all(T));
ll q, x, L, R;
char c;
while(Q--){
cin >> q;
if (q == 1){
cin >> x >> c;
--x;
S[x] = c;
T[N - x - 1] = c;
}
else{
cin >> L >> R;
--L; --R;
// 文字列の切り出しと、逆さ文字列の切り出しが同一か比較する
string s = S.substr(L, R - L + 1);
string t = T.substr(N - R - 1, R - L + 1);
if (s == t){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
}
}
}解説を見ると、クエリ2がきたときに、回文かどうかの判定を1文字ずつ比較しないようだ。文字列を数値として扱い、O(1)で判定できるらしい。RollingHashという。ロリハしていこうと思う。
1. 文字列Sに対して、逆さにした文字列Tを用意する。
2. 文字列をhash化する。
S = "a b c"とすると、
a = 'a' * 2^0
b = 'b' * 2^1
c = 'c' * 2^2
といったように、indexによって次元を分けて、BITに格納する。
このとき、文字列とhashの対応は累積和をとればよくて
memo["abc"] = 'a' * 2^0 + 'b' * 2^1 + 'c' * 2^2
memo["ac"] = 'a' * 2^0 + 'c' * 2^2
のような対応になる。
Q. 文字がずれている場合は？
S="abac"
T="caba"
とあった場合。abaで回文判定をしたい。
このとき、Tで得られた"aba"のhashを<<1すれば、Sで得られた"aba"のhashと一致する。
A. 累積和なので、全部の値をbaseでかけたり割ったりすれば、補正できる。3. クエリ1がきたときに文字を変更する。このときhashは高速に再計算できる必要がある。BITで管理し、累積和を求めるようにしてhashを生成すればよさそう。遅延セグ木でも可能だと思う。
4. 正確性が問題になる。Hashの衝突をさけるには、どれくらい値に余裕が必要？
MODに対してroot(MOD)くらいの値までなら、衝突をほぼ避けられるらしい。
リスクを下げるために2つのバリエーションをもたせる必要がある。素数となるMODと、baseの2種類だ。
N=1e6なので、MOD=1e12をとりたい。
しかし、計算過程で掛け算が生じるので、longlongでオーバーフローしないように、MOD=1e9程度におさえたい。
MOD=1e9を2パターン計算し、MOD^2=1e18ほどの精度に上げる方法をとる。
バリエーションについて、MODだけだと十分ではないので注意。baseも変動させる必要がある。
[ref] baseを2に固定した場合、1WA。
https://atcoder.jp/contests/abc331/submissions/48169446
そもそもの話、RollingHashは完全に安全な回答ではないようだ。
5. MODとbaseを変更した2パターンでsolve()を行い、いずれでも回文と判定できたものについて"Yes"として扱えば盤石になりそう
実装
/////////////////////////// Bit
template <ll BT>
struct Bit {
mint dat[BT + 10]{};
void add(ll i, mint x) {
++i;
for (; i < BT; i += i & -i) dat[i] += x;
}
mint sum(ll i) { // [0, i]
if (i < 0) return 0;
if (i >= BT - 1) i = BT - 2;
++i;
mint res = 0;
for (; i > 0; i -= i & -i) res += dat[i];
return res;
}
mint rangesum(ll L, ll R) { // [L, R]
return sum(R) - sum(L - 1);
}
};
/////////////////////////// Main
Bit<1000010> bit[4];
vector<mint> pows(1000010, 1);
int main() {
cincout();
ll N, Q;
string S, T;
cin >> N >> Q >> S;
T = S;
reverse(all(T));
vector<tll> query;
rep(q, Q) {
ll a, x, L, R;
char c;
cin >> a;
if (a == 1) {
cin >> x >> c;
query.emplace_back(a, x, c);
} else {
cin >> L >> R;
query.emplace_back(a, L, R);
}
}
// 2種類のMODとbaseで回文の判定をする。両方がtrueの場合にYes
vector<bool> ans(Q, true);
auto solve = [&](ll mod, ll p, Bit<1000010>& bit0, Bit<1000010>& bit1, string S,
string T) {
// MODとbaseの設定
MOD = mod;
rep(i, N) pows[i + 1] = pows[i] * p;
rep(i, N) {
mint s = S[i] - 'a';
mint t = T[i] - 'a';
bit0.add(i, s * pows[i]);
bit1.add(i, t * pows[i]);
}
// query処理
rep(q, Q) {
auto [a, b, _c] = query[q];
if (a == 1) {
ll x = b - 1;
char c = _c;
mint s = S[x] - 'a';
mint t = T[N - x - 1] - 'a';
bit0.add(x, -s * pows[x]);
bit1.add(N - x - 1, -t * pows[N - x - 1]);
S[x] = c;
T[N - x - 1] = c;
s = c - 'a';
t = c - 'a';
bit0.add(x, s * pows[x]);
bit1.add(N - x - 1, t * pows[N - x - 1]);
} else {
ll L = b, R = _c;
--L, --R;
mint s = bit0.rangesum(L, R);
mint t = bit1.rangesum(N - R - 1, N - L - 1);
// 補正
if (N - R - 1 > L) {
s *= pows[(N - R - 1) - L];
} else {
t *= pows[L - (N - R - 1)];
}
ans[q] = (s == t) & ans[q];
}
}
};
// 2種類のMODとbase
solve(1212121217, rand() % 1212121217, bit[0], bit[1], S, T);
solve(1212121219, rand() % 1212121219, bit[2], bit[3], S, T);
rep(q, Q) {
auto [a, b, c] = query[q];
if (a == 1) continue;
if (a == 2) {
if (ans[q])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}
https://atcoder.jp/contests/abc331/submissions/48172490