• \(1\) 文字目から \(|S|\) 文字目を \(0\) ブロック目
• \(|S|+1\) 文字目から \(2 \times |S|\) 文字目を \(1\) ブロック目
• \(2 \times |S|+1\) 文字目から \(3 \times |S|\) 文字目を \(2\) ブロック目
• \(\dots\)

と呼ぶことにします。すると、操作後にできる文字列のうち

• \(0\) ブロック目は \(S\)
• \(1\) ブロック目は \(S\) の大小文字を反転したもの
• \(2\) ブロック目は \(S\) の大小文字を反転したもの
• \(3\) ブロック目は \(S\)
• \(4\) ブロック目は \(S\) の大小文字を反転したもの
• \(5\) ブロック目は \(S\)
• \(6\) ブロック目は \(S\)
• \(7\) ブロック目は \(S\) の大小文字を反転したもの
• \(\dots\)

となることが分かります。

\(S\) の \(1\) ブロックから始めて、「全体の大小文字を反転したものを後ろにつける」という操作を繰り返していることになります。この操作を \(k\) 回繰り返すと、全体は \(2^k\) ブロックになります。

このことから、次が成立します。

• \(B\) ブロック目の文字を特定したいとする。 \(B\) を \(2\) 進表記した際、最も上位にある \(1\) が \(2^k\) の位であるとき、 \(B\) ブロック目は \(B-2^k\) ブロック目の大小文字を反転したものになる。

これを \(B=0\) になるまで辿ることでもこの問題に正解できますが、その過程を考えると次が成立します。

• \(B\) を \(2\) 進表記した際の各桁に含まれる \(1\) の数が偶数なら、 \(B\) ブロック目は \(S\)
• \(B\) を \(2\) 進表記した際の各桁に含まれる \(1\) の数が奇数なら、 \(B\) ブロック目は \(S\) の大小文字を反転したもの

よって、 \(K_i\) 文字目が何ブロック目の何文字目かを特定し、そのブロックの番号を \(2\) 進表記した際に各桁にいくつ \(1\) が含まれるか求めればこの問題に正解できます。
\(2\) 進表記した際の \(1\) の数はループ等を用いて数えても良ければ、 popcount のような \(2\) 進表記において立っている bit の個数を数える関数を利用しても良いです。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

char flip(char c){
  if('a'<=c && c<='z'){
    return (c-'a')+'A';
  }
  else{
    return (c-'A')+'a';
  }
}

int main(){
  string s;
  cin >> s;
  int q;
  cin >> q;
  for(int i=0;i<q;i++){
    if(i){cout << " ";}
    long long k;
    cin >> k;
    k--;
    long long blk=k/s.size();
    long long pt=k%s.size();
    if(popcount((unsigned long long)blk)%2){
    // if(__builtin_popcountll(blk)%2){
    // if(__builtin_parityll(blk)){
      cout << flip(s[pt]);
    }
    else{
      cout << s[pt];
    }
  }cout << "\n";
  return 0;
}