平方分割はサイズ設定が割と難しい。
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e
問題
M個のN文字の文字列が与えられる。
また文字列におけるローリングハッシュの計算式が与えられる。
以下のクエリに順次答えよ。
- 2つの文字列において、同じ位置の部分文字列をswapする
- 指定された文字列の部分文字列のハッシュ値を答える。
解法
いわゆる平方分割で解く。
文字列をD文字ずつのブロックに分け、ブロック毎のハッシュ値を計算しておこう。
前者のクエリに対し、ブロック全体がswap対象となる部分は文字列だけでなくブロックのハッシュ値もswapすればいいので、ハッシュ値の再計算はO(D)で済む。
後者のハッシュ値計算もO(D+N/D)で済むので、Dを300~500程度にしておくとどうにか解ける。
const int DI=300; int N,M,Q; string S[21][700]; ll phash[21][700]; ll p10[201010]; ll mo=1000000007; void update(int cur,int id) { ll ret=0; for(int i=(int)S[cur][id].size()-1;i>=0;i--) ret=(ret*1000000+S[cur][id][i])%mo; phash[cur][id]=ret; } void solve() { int i,j,k,l,r,x,y; string s; p10[0]=1; FOR(i,200010) p10[i+1]=p10[i]*1000000%mo; cin>>N>>M; FOR(i,M) { cin>>s; FOR(x,N) S[i][x/DI].push_back(s[x]-'a'+1); FOR(x,N/DI+2) update(i,x); } cin>>Q; while(Q--) { int T,X,Y,L,R; cin>>T>>X>>Y>>L>>R; X--,Y--,L--; if(T==1) { if(L%DI) { while(L%DI && L<R) swap(S[X][L/DI][L%DI],S[Y][L/DI][L%DI]), L++; update(X,(L-1)/DI); update(Y,(L-1)/DI); } if(R%DI) { while(R%DI && L<R) R--, swap(S[X][R/DI][R%DI],S[Y][R/DI][R%DI]); update(X,R/DI); update(Y,R/DI); } while(L<R) { swap(S[X][L/DI],S[Y][L/DI]); swap(phash[X][L/DI],phash[Y][L/DI]); L+=DI; } } else { ll ret=0; int len=0; while(L%DI && L<R) (ret+=p10[len]*S[X][L/DI][L%DI])%=mo, len++, L++; while(L+DI<=R) (ret+=p10[len]*phash[X][L/DI])%=mo, len+=DI, L+=DI; while(L<R) (ret+=p10[len]*S[X][L/DI][L%DI])%=mo, len++, L++; cout<<ret<<endl; } } }
まとめ
5秒かかったので割と怖い。