タイプ \(1\) 、タイプ \(2\) のクエリは愚直に行っても時間計算量 \(O(1)\) ですが、タイプ \(3\) のクエリは愚直に行うと \(k\) 回の操作を \(1\) 度にまとめるような工夫をしても \(1\) 回あたり時間計算量 \(O(N)\) 、全体で最悪の場合時間計算量 \(O(NQ)\) となり実行時間制限に間に合いません。
どうにかしてタイプ \(3\) のクエリを高速に対処したいです。どのようにすればよいでしょうか？

この問題を次のように読み替えても、答えは変化しません。

• 数列を 0-indexed として取り扱う。つまり、 \(A=(A_0,A_1,\dots,A_{N-1})\) と添え字を振り直し、 \(p\) を含むクエリについて受け取った直後に \(p\) を \(1\) 減算するものとする。
• 最初、 \({\rm offset} = 0\) とする。
• タイプ \(1\) のクエリを、「 \(A_{(p+{\rm offset})\%N}\) を \(x\) に変更する」と読み替える。
• タイプ \(2\) のクエリを、「 \(A_{(p+{\rm offset})\%N}\) を出力する」と読み替える。
• タイプ \(3\) のクエリを、「 \({\rm offset}\) を \(({\rm offset} + k) \% N\) で置き換える」と読み替える。

但し、 \(p\%q\) で \(p\) を \(q\) で割った余りを表します。

要するに、タイプ \(3\) の本来 \(O(N)\) かかる操作を、 \({\rm offset}\) の値のみを変更するという \(O(1)\) の軽い操作に置き換えることで高速化しています。
\({\rm offset}\) を \(1\) 増やすと元々 \(A_0\) を読むはずだった操作が \(A_1\) を、元々 \(A_1\) を読みはずだった操作が \(A_2\) を、 \(\dots\) 、元々 \(A_{N-1}\) を読むはずだった操作が \(A_0\) を読むようになります。これは、まさに元々のタイプ \(3\) で行いたい置き換えです。

この高速化により全てのクエリへの対処が時間計算量 \(O(1)\) となり、全体で時間計算量 \(O(N+Q)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    A[i]=i+1;
  }
  int offset=0;
  while(Q>0){
    Q--;
    int typ;
    cin >> typ;
    if(typ==1){
      int p,x;
      cin >> p >> x;
      p--;
      A[(p+offset)%N]=x;
    }
    else if(typ==2){
      int p;
      cin >> p;
      p--;
      cout << A[(p+offset)%N] << "\n";
    }
    else{
      int k;
      cin >> k;
      offset+=k;
      offset%=N;
    }
  }
  return 0;
}