問題概要
英小文字からなる文字列 $S$ が与えられる.$S$ に対し,以下の操作を十分大きい回数繰り返し適用する:
- $S$ の大文字・小文字を反転した文字列を $T$ とする.
- $S \leftarrow S + T$ とする.
$q$ 個の整数 $K_1, K_2, \dots, K_q$ が与えられる.各 $K_i$ に対し,$S_k$ を求めよ.
制約
- $|S| \leq 2 \times 10^5$
- $1 \leq q \leq 2 \times 10^5$
- $1 \leq K_i \leq 10^{ 18 }$
解法
各 $K_i$ について独立に答えが定まるため,着目している $K_i$ を $k$ と書きます.
入力で与えられた時点での $S$ の長さを $l$ とします.$k \leq l$ であれば,$S_k$ がそのまま答えとなります.そうでない場合,$k$ が初めて「確実に有効な $S$ の添字」となる反復が存在するはずです(具体的には $k \leq l2^x$ となる最小の $x$ について $x$ 回目の反復).そのときの $S, T$ を考えると,
- $k \leq |S|$ のとき,$S_k$ が答え.
- $|S| < k$ のとき,$S_{ k - |S| }$ を反転したものが答え.
として,反復操作を巻き戻せます.このとき,$k$ の上界と「その反復での $S, T$」の長さは半分になっていくので,$O( \log k )$ 回の巻き戻しでベースケースに辿り着きます.
上記は基本的な演算のみで実装できるため,各 $K_i$ ついて適用することで $O( q \log \max K )$ 時間のアルゴリズムとなります.
実装についての小話としては,ASCII コードにおける大文字・小文字の反転は,文字コードの $6$ ビット目を反転することで行えます.
コード
int main() { IN( string, S ); IN( int, Q ); VLL K( Q ); cin >> K; const int L = SZ( S ); vector< char > res; FOR( k, K ) { LL l = L; for ( ; l < k; l *= 2 ); int flip = 0; while ( L < k ) { if ( l / 2 < k ) { k -= l / 2; flip ^= 1; } l /= 2; } res.PB( S[ k - 1 ] ^ ( flip << 5 ) ); } cout << res << endl; return 0; }