kmjp's blog

競技プログラミング参加記です

Codeforces #337 Div2 E. Alphabet Permutations

こっちも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処理ライブラリ作ろうかな…。