結果
| 問題 | No.3638 Itsuki |
| コンテスト | |
| ユーザー |
 あるふぁ
|
| 提出日時 | 2026-08-26 11:27:35 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 7,075 bytes |
| 記録 | |
| コンパイル時間 | 3,883 ms |
| コンパイル使用メモリ | 365,980 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-08-26 11:27:50 |
| 合計ジャッジ時間 | 11,738 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 2 |
| 小課題1 | 10 % | AC * 5 |
| 小課題2 | 50 % | TLE * 1 -- * 5 |
| 小課題3 | 40 % | AC * 7 TLE * 1 -- * 10 |
| 合計 | 10 点 |
ソースコード
#define YUKICODER
// #define CODEFORCES
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pob pop_back
#define eb emplace_back
#define nall(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define accu accumulate
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#ifdef CODEFORCES
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define yesno(a) cout<<(a?"YES\n":"NO\n")
#define yesnoout(a, b) cout<<(a?"YES\n":"NO")<<(a?b:"")<<"\n"
#else
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yesno(a) cout<<(a?"Yes\n":"No\n")
#define yesnoout(a, b) cout<<(a?"Yes\n":"No")<<(a?b:"")<<"\n"
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec = vector<T>;
template<class T> using vv = vector<vector<T>>;
template<class T> using vvv = vector<vv<T>>;
const ll MOD = 998244353ll;
// const ll MOD = 1000000007ll;
// template
namespace tree{
template<class T> class segtree{
private:
int n, size;
vector<T> seg;
T e;
function<T(T, T)> op;
public:
segtree(const vector<T>& A, function<T(T, T)> op, T id) : e(id), op(op){
n = A.size();
size = 1;
while (size < n) size <<= 1;
seg.assign(2*size, e);
for (int i = 0; i < n; i++) seg[size+i] = A[i];
for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
}
segtree(int sz, function<T(T, T)> op, T id) : e(id), op(op){
n = sz;
size = 1;
while (size < n) size <<= 1;
seg.assign(2*size, e);
for (int i = 0; i < n; i++) seg[size+i] = e;
for (int i = size-1; i > 0; i--) seg[i] = op(seg[i<<1], seg[i<<1|1]);
}
void set(int i, T val){
i += size;
seg[i] = val;
while (i >>= 1) seg[i] = op(seg[i<<1], seg[i<<1|1]);
}
T all_prod() const{
return seg[1];
}
T prod(int l, int r) const{
T L = e, R = e;
for (l += size, r += size; l < r; l >>= 1, r >>= 1){
if (l&1) L = op(L, seg[l++]);
if (r&1) R = op(seg[--r], R);
}
return op(L, R);
}
T get(int i) const{
return seg[size+i];
}
const T& operator [] (int i) const{
return seg[size+i];
}
void add(int i, T val){
set(i, get(i)+val);
}
template<class F> int max_right(int l, F f) const{
if (l == n) return n;
l += size;
T sm = e;
do{
while ((l & 1) == 0) l >>= 1;
if (!f(op(sm, seg[l]))){
while (l < size){
l <<= 1;
if (f(op(sm, seg[l]))){
sm = op(sm, seg[l]);
l++;
}
}
return l-size;
}
sm = op(sm, seg[l]);
l++;
}while((l&-l) != l);
return n;
}
template<class F> int min_left(int r, F f) const{
if (r == 0) return 0;
r += size;
T sm = e;
do{
r--;
while (r > 1 && (r&1)) r >>= 1;
if (!f(op(seg[r], sm))){
while (r < size){
r = r<<1|1;
if (f(op(seg[r], sm))){
sm = op(seg[r], sm);
r--;
}
}
return r+1-size;
}
sm = op(seg[r], sm);
}while((r&-r) != r);
return 0;
}
};
}
class rollinghash{
private:
const array<ll, 5> mod = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
const ll base = 100;
vector<array<ll, 5>> hash, power;
public:
rollinghash(const string& S){
int N = S.size();
hash.resize(N+1);
power.resize(N+1);
power[0] = {1, 1, 1, 1, 1};
hash[0] = {0, 0, 0, 0, 0};
for (int i = 0; i < N; i++) for (int j = 0; j < 5; j++){
power[i+1][j] = (power[i][j]*base)%mod[j];
}
for (int i = 0; i < N; i++) for (int j = 0; j < 5; j++){
hash[i+1][j] = (hash[i][j]*base+S[i])%mod[j];
}
}
array<ll, 5> get(int l, int r){
array<ll, 5> res;
for (int i = 0; i < 5; i++){
ll num = hash[r][i]-(hash[l][i]*power[r-l][i])%mod[i];
if (num < 0) num += mod[i];
res[i] = num;
}
return res;
}
};
struct segtree_rollinghash{
struct node {
array<ll, 5> h;
int len;
};
template<class T> using segtree = tree::segtree<T>;
const array<ll, 5> mod = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
const ll base = 100;
vector<array<ll, 5>> power;
function<node(node, node)> op;
node e = {{0, 0, 0, 0, 0}, 0};
segtree<node> seg;
segtree_rollinghash(const string& s) : power(s.size()+1), op(nullptr), seg(build_init(s), [&](node a, node b){ return a; }, e){
int n = s.size();
build_power(n);
op = [&](node a, node b){
if (a.len == 0) return b;
if (b.len == 0) return a;
node res;
res.len = a.len+b.len;
for (int i = 0; i < 5; i++){
res.h[i] = (a.h[i]*power[b.len][i]+b.h[i])%mod[i];
}
return res;
};
seg = segtree<node>(build_init(s), op, e);
}
void build_power(int n){
power.resize(n+1);
power[0] = {1, 1, 1, 1, 1};
for (int i = 0; i < n; i++) for (int j = 0; j < 5; j++){
power[i+1][j] = power[i][j]*base%mod[j];
}
}
vector<node> build_init(const string& s){
int n = s.size();
vector<node> v(n);
for (int i = 0; i < n; i++){
v[i].len = 1;
for (int j = 0; j < 5; j++) v[i].h[j] = s[i];
}
return v;
}
void set(int pos, char c){
node x;
x.len = 1;
for (int j = 0; j < 5; j++) x.h[j] = c;
seg.set(pos, x);
}
node get(int l, int r){
return seg.prod(l, r);
}
};
void solve();
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
unsigned T = 1;
// cin >> T;
cout << fixed << setprecision(20);
while (T--) solve();
return 0;
}
void solve(){
int N, Q;
string S;
cin >> N >> Q >> S;
segtree_rollinghash RH(S);
while (Q--){
int t;
cin >> t;
if (t == 1){
int i;
char c;
cin >> i >> c, i--;
RH.set(i, c);
}
else{
string t;
cin >> t;
rollinghash rh(t);
bool ok = false;
rep(i, N-t.size()+1){
if (rh.get(0, t.size()) == RH.get(i, i+t.size()).h) ok = true;
}
yesno(ok);
}
}
}