結果

問題 No.3239 Omnibus
ユーザー 沙耶花
提出日時 2025-08-15 22:06:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,551 bytes
コンパイル時間 4,237 ms
コンパイル使用メモリ 261,952 KB
実行使用メモリ 65,224 KB
最終ジャッジ日時 2025-08-15 22:06:37
合計ジャッジ時間 21,676 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 1000000000000000001LL
string s;
map<string,long long> mc[1<<19],mr[1<<19];

void dfs(string s,int pos,int oripos, int add){
	if(pos==0)return;
	mc[pos][s] += add;
	mr[pos][s] += add * oripos;
	if(add < 0){
		if(mc[pos][s]==0){
			mc[pos].erase(s);
		}
		if(mr[pos][s]==0){
			mr[pos].erase(s);
		}
	}
	dfs(s,pos/2,oripos,add);
}

void deal(int pos,int add){
	if(pos < 2)return;
	if(pos >= s.size())return;
	string t = s.substr(pos-2,3);
	dfs(t, pos + (1<<18),pos, add);
}

int main(){
	int n,q;
	cin>>n>>q;
	cin>>s;
	rep(i,n){
		deal(i,1);
	}
	rep(_,q){
		int t;
		cin>>t;
		if(t==1){
			int i;
			char c;
			cin>>i>>c;
			i--;
			rep(j,3){
				deal(i+j,-1);
			}
			s[i] = c;
			rep(j,3){
				deal(i+j,1);
			}
		}
		else{
			int l,r;
			cin>>l>>r;
			l--;
			string a;
			cin>>a;
			if(r-l < 3){
				cout<<0<<endl;
				continue;
			}
			l += 2;
			long long tl = l,tr = r;
			l += 1<<18;
			r += 1<<18;
			long long ans = 0,c = 0;
			while(true){
				if(l&1){
					if(mc[l].count(a)){
						c += mc[l][a];
					}
					if(mr[l].count(a)){
						ans += mr[l][a];
					}
					l++;
				}
				if(r&1){
					r--;
					if(mc[r].count(a)){
						c += mc[r][a];
					}
					if(mr[r].count(a)){
						ans += mr[r][a];
					}
				}
				if(l>=r)break;
				l >>=1;
				r >>= 1;
			}
			ans -= (tl-1) * c;
			cout<<ans<<endl;
		}
	}
}
0