kmjp's blog

競技プログラミング参加記です

Codeforces #260 Div1 D. Serega and Fun

本番Hack狙いに行ってDは避けたのだけど、これなら解けたかもな。
http://codeforces.com/contest/455/problem/D

問題

N要素の数列A[i]がある。
ここに対し以下のクエリQ個に答えよ。

  1. l,rに対してA[l]~A[r]をシフトし、A[r],A[l],A[l+1],...,A[r-1]と並べ替える。
  2. 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でも間に合うかな…?