\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
ハッシュで部分文字列であるかを高速に判定する． 回文の判定として，通常の文字列と反転した文字列の2種類のハッシュを用意する． 文字列のハッシュを segtree に乗せることで， \(O(log N)\) でハッシュの計算ができる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
const ll p1 = 1000000021;
const ll p2 = 1000000033;
struct mints{
ll d1,d2;
mints(ll val = 0): d1(val), d2(val){}
mints(ll d1, ll d2): d1(d1), d2(d2){}
mints operator + (const mints& a) const{
rep(i,n) t2.set(n-1-i, D(s[i], x));
rep(qi,q){
ll type; cin >> type;
if(type == 1){
ll i; char c;
cin >> i >> c;
--i;
t1.set(i, D(c,x));
t2.set(n-1-i, D(c,x));
}else{
ll l,r;
cin >> l >> r;
--l;
yesno(t1.prod(l,r).h == t2.prod(n-r,n-l).h);
}
}
return 0;
}
*1:d1 + a.d1)%p1, (d2 + a.d2)%p2);
}
mints operator * (const mints& a) const{
return mints((d1 * a.d1)%p1, (d2 * a.d2)%p2);
}
bool operator == (const mints& a) const{
return d1==a.d1 && d2==a.d2;
}
};
struct D{
mints h,c;
D(){}
D(mints h, mints c): h(h), c(c){}
};
D op(D a, D b){
return D(a.h + a.c*b.h, a.c * b.c);
}
D e(){
return D(0,1);
}
int main() {
ll n, q;
cin >> n >> q;
string s; cin >> s;
segtree<D, op, e> t1(n), t2(n);
ll x = rand()%p1;
rep(i,n) t1.set(i, D(s[i], x
