こっちもRangeを管理する問題か…。
http://codeforces.com/contest/610/problem/E
問題
先頭K種類のアルファベットで構成される文字列Sがある。
これに対し以下の2種類のクエリを順次処理せよ。
- 整数L,Rと文字Cが与えられるので、S[L..R]をすべてCにする。
- 先頭K個のアルファベットのpermutationである文字列Pが与えられる。このPを何個並べると部分文字列としてSを含むか答える。
解法
まず後者を考えよう。
S[i]とS[i+1]の2つの文字があったとき、それらが同じか、またはPにおいてS[i]よりS[i+1]が後に存在する場合、PがSを複数含むためにはPをもう一つ追加しなければならない。
愚直にそのような数を求めると1回あたりO(|S|)かかるが、連続する2文字の組み合わせそれぞれの登場回数だけを事前に数えてあれば、この値はO(K^2)で求まる。
あとは1番目のクエリに対し、S[i],S[i+1]の組み合わせ数を高速に数え上げよう。
自分は1番目のクエリが同じ文字の連続を生成する点に注目し、文字列を同じ文字の連続の集合と見なし、(開始位置,終了位置,文字)のsetを用いて処理を行った。
SegTreeで解いても間に合うようだ。
int N,M,K; string S; int num[12][12]; set<pair<int,pair<int,char>>> SS; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K; cin>>S; FOR(i,N-1) num[S[i]-'a'][S[i+1]-'a']++; SS.insert({0,{0,10}}); FOR(i,N) SS.insert({i+1,{i+1,S[i]-'a'}}); SS.insert({N+1,{N+1,10}}); while(M--) { cin>>x; if(x==1) { cin>>x>>y>>s; vector<pair<int,pair<int,char>>> toadd; int first=0; toadd.push_back({y,{x,s[0]-'a'}}); while(1) { auto it=SS.lower_bound({x,{0,0}}); if(it->second.first>y) break; if(it->second.first<x) toadd.push_back({x-1,{it->second.first,it->second.second}}); if(y<it->first) toadd.push_back({it->first,{y+1,it->second.second}}); if(first==0) { auto it2=it; it2--; num[it2->second.second][it->second.second]--; first=1; } auto it2=it; it2++; num[it->second.second][it2->second.second]--; num[it->second.second][it->second.second]-=it->first-it->second.first; SS.erase(it); } sort(ALL(toadd)); FOR(i,toadd.size()) { auto r=toadd[i]; num[r.second.second][r.second.second]+=r.first-r.second.first; auto it=SS.insert(r).first; it--; num[it->second.second][r.second.second]++; if(i==toadd.size()-1) { it++; it++; num[r.second.second][it->second.second]++; } } } else { cin>>s; ll ret=1; FOR(y,K) FOR(x,y+1) ret+=num[s[y]-'a'][s[x]-'a']; cout<<ret<<endl; } } }
まとめ
DもEもRangeを処理する問題だった。
いい加減Range処理ライブラリ作ろうかな…。