本番Hack狙いに行ってDは避けたのだけど、これなら解けたかもな。
http://codeforces.com/contest/455/problem/D
問題
N要素の数列A[i]がある。
ここに対し以下のクエリQ個に答えよ。
- l,rに対してA[l]~A[r]をシフトし、A[r],A[l],A[l+1],...,A[r-1]と並べ替える。
- l,rに対してA[l]~A[r]中におけるkの数を答える。
解法
平方分割+dequeで解ける。
√N個のdequeを準備し、各dequeにどの数字が何個入っているか累積値を取っておく。
1つ目のクエリに対してはA[l]~A[r]に相当するdequeの中身を1個ずつずらすだけなのでO(√N)で処理できる。
2つ目のクエリに対しても、A[0]~A[r]中のkの数は、A[0]~A[(r/√N)*√N-1]中のkの数はdequeにおける累積値を使ってO(√N)で計算できるので、あとは1個のdequeの中身A[(r/√N)*√N]~A[r]からkを探せばいいのでこちらもO(√N)で済む。
よって全体ではO(Q√N)で済む。
const int SP=300; int N,Q; deque<int> D[500]; int sum[501][100002]; int lastans; void solve() { int f,i,j,k,l,x,y,r; cin>>N; FOR(i,N) { cin>>x; D[i/SP].push_back(x-1); sum[i/SP][x-1]++; } cin>>Q; while(Q--) { cin>>i>>l>>r; l=(l+lastans-1)%N; r=(r+lastans-1)%N; if(l>r) swap(l,r); if(i==1) { j=D[r/SP][r%SP]; sum[r/SP][j]--; D[r/SP].erase(D[r/SP].begin()+r%SP); sum[l/SP][j]++; D[l/SP].insert(D[l/SP].begin()+l%SP,j); FOR(i,500) while(D[i].size()>SP) { j=D[i].back(); D[i].pop_back(); sum[i][j]--; D[i+1].push_front(j); sum[i+1][j]++; } } else { cin>>k; k=(k+lastans-1)%N; r++; lastans=0; FOR(i,500) { if(i<r/SP) lastans+=sum[i][k]; if(i<l/SP) lastans-=sum[i][k]; if(i==r/SP) { FOR(j,r%SP) lastans+=D[i][j]==k; } if(i==l/SP) { FOR(j,l%SP) lastans-=D[i][j]==k; } } cout<<lastans<<endl; } } }
まとめ
dequeがランダムアクセスできるのしらなかった。
平方分割+vectorでも間に合うかな…?