Codeforces #263 Div1 C. Appleman and a Sheet of Paper

なかなか面白い問題。
http://codeforces.com/contest/461/problem/C

問題

初期状態で縦1×横Nの大きさの紙がある。
ここで以下のクエリQ個を処理せよ。

1. 紙の左端から距離xのところで紙を折り返し。結果、左端から距離xまでの部分の紙は距離x～2xの部分に重なる。
2. 紙の左端から数えて、距離l～rの範囲に含まれる紙が1x1の紙何個分か答えよ。

解法

BITを使い各位置において重なっている紙の量をカウントする。
折り返しの場合、(左端～x)の部分と(x～右端)の部分のうち、小さい方を大きい方に足しこむ。
例えば現在BIT[L]～BIT[R]の部分に紙の量が格納されている場合、座標xで折り返すならBIT[L+x-1]の値をBIT[L+x]、BIT[L+x-2]の値をBIT[L+x+1]…BIT[L]の値をBIT[L+x+(x-1)]に足しこむ。
その後BIT[L+x]～BIT[R]の部分に紙の量がカウントされてるとする。

xが大きく、折り返し地点が右端に近い場合、BITにおける座標を左右反転すればよい。
すなわち左端からの距離0の紙の量がBIT[L]、距離1の紙の量がBIT[L-1]…距離(R-L)の紙の量がBIT[R] (R

int N,W,Q;
int L,R;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void update(int e, V val) {e++; while(e<=1<<ME) bit[e-1]+=val,e+=e&-e;}
};
BIT<int,20> bt;
int B[100010];

void solve() {
	int f,i,j,k,l,x,y,r;
	cin>>N>>Q;
	L=1, R=N+1;
	
	FOR(i,N) bt.update(i+1,1), B[i+1]=1;
	
	while(Q--) {
		cin>>x;
		if(x==1) {
			cin>>x;
			
			if(L<R) {
				if(2*x<=R-L) {
					for(i=L;i<L+x;i++) B[L+x+(L+x-1-i)]+=B[i],bt.update(L+x+(L+x-1-i),B[i]);
					L+=x;
				}
				else {
					for(i=R-1;i>=L+x;i--) B[L+x-1-(i-(L+x))]+=B[i],bt.update(L+x-1-(i-(L+x)),B[i]);
					R=L-1;
					L=L+x-1;
				}
			}
			else {
				if(2*x<=L-R) {
					for(i=L;i>L-x;i--) B[L-x-(i-(L-x+1))]+=B[i],bt.update(L-x-(i-(L-x+1)),B[i]);
					L-=x;
				}
				else {
					for(i=R+1;i<=L-x;i++) B[L-x+1-(i-(L-x))]+=B[i],bt.update(L-x+1-(i-(L-x)),B[i]);
					R=L+1;
					L=L-x+1;
				}
			}
		}
		else {
			cin>>l>>r;
			if(L<R) cout<<bt.total(r+L-1)-bt.total(l+L-1)<<endl;
			else cout<<bt.total(L-l)-bt.total(L-r)<<endl;
		}
	}
}

まとめ

本番は平方分割でTLEした。