yukicoder : No.151 セグメントフィッシング、No.259 セグメントフィッシング＋

計算量の見積もりが甘く、面倒な実装をしてしまった。
http://yukicoder.me/problems/383
http://yukicoder.me/problems/396

問題

１次元の数直線において、0～(N-1)のN個の地点で構成された釣堀がある。
魚は左(数直線減少方向)または右(数直線増加方向)のどちらかを向いており、時間１毎に進行方向に１向かう。
ただし向いている方向に進めない場合、その場で逆を向く。

Q個のクエリが与えられる。
i番目のクエリを時刻iに実行するとし、各クエリを処理せよ。

1. 座標Y[i]に左向きの魚をZ[i]匹放つ
2. 座標Y[i]に右向きの魚をZ[i]匹放つ
3. 区間[Y[i],Z[i])に含まれる魚の数を答える。

なお、No.259はクエリの実行時刻がiではない、またNの上限が10倍な点で異なる。

解法

O(Q^2)解法

No.151はこれで通る。
時刻tに魚の数を答えるクエリを受けた場合、1～(t-1)に放たれた魚が時刻tにどこにいるかを求め、区間[Y[i],Z[i])に含まれるものをカウントすればよい。

O(Q*logN)解法

No.259はO(Q*logN)解でないと間に合わない。
魚および区間が時刻0にどこにいるか、を逆算して解くと良い。

今回のように物体が反転して動く問題では、探索範囲を２倍にする手法が使える（例：リベリオン・某マヨネーズの網目柄）。
例えば魚の位置は0～(N-1)ではなく２倍に拡大して0～(2*N-1)にいると考える。
（右向きの魚が座標x(N≦x≦2*N-1)にいる＝左向きで2*N-1-xにいる、と考える）

左向き魚用BITと右向き魚用BITを使い、それぞれ区間内の魚の合計を求める。

• 時刻tに座標Y[i]から左向きに放たれた魚は、時刻0に座標(Y[i]+t)%2Nにいると考え、左向き用BITのその位置にZ[i]匹に加える。
• 時刻tに座標Y[i]から右向きに放たれた魚は、時刻0に座標(Y[i]-t)%2Nにいると考え、同様に右向き用BITにZ[i]匹を加える。
• ３番目のクエリに対しては、区間[Y[i],Z[i])だとわかりにくいので区間[Y[i],Z[i]-1]と考えると時刻0の位置を考えて以下の区間の魚の数の総和を取る
  • 左向き用BITから区間[(Y[i]+t)%2N,(Z[i]-1+t)%2N]
  • 左向き用BITから区間[(2N-1-Z[i]-1+t)%2N,(2N-1-Y[i]]+t)%2N]
  • 右向き用BITから区間[(Y[i]-t)%2N,(Z[i]-1-t)%2N]
  • 右向き用BITから区間[(2N-1-Z[i]-1-t)%2N,(2N-1-Y[i]]-t)%2N]
    • 放したときは左向きだが、時刻tでは左向きの場合と右向きの場合があるので、両BITから２回区間の和を取る必要がある。

以下、上はNo.151、下はNo.259解です。

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
	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<ll,20> Lbt;
BIT<ll,20> Rbt;


int N,N2,Q;
string X[30000];
int Y[30000],Z[30000];

ll momo(ll a) { return (a%N2+N2)%N2;}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	N2=2*N;
	FOR(i,Q) {
		cin>>X[i]>>Y[i]>>Z[i];
		if(X[i][0]=='L') {
			Lbt.update(1+momo(Y[i]+i+1),Z[i]);
		}
		if(X[i][0]=='R') {
			Rbt.update(1+momo(Y[i]-(i+1)),Z[i]);
		}
		if(X[i][0]=='C') {
			Z[i]--;
			ll ret=0;
			x=momo(Y[i]+(i+1));
			y=momo(Z[i]+(i+1));
			if(x<=y) ret +=Lbt.total(y+1)-Lbt.total(x);
			else ret +=Lbt.total(N2+2)-Lbt.total(x) + Lbt.total(y+1);
			
			x=momo(N2-1-Z[i]+(i+1));
			y=momo(N2-1-Y[i]+(i+1));
			if(x<=y) ret +=Lbt.total(y+1)-Lbt.total(x);
			else ret +=Lbt.total(N2+2)-Lbt.total(x) + Lbt.total(y+1);
			
			x=momo(Y[i]-(i+1));
			y=momo(Z[i]-(i+1));
			if(x<=y) ret +=Rbt.total(y+1)-Rbt.total(x);
			else ret +=Rbt.total(N2+2)-Rbt.total(x) + Rbt.total(y+1);
			
			x=momo(N2-1-Z[i]-(i+1));
			y=momo(N2-1-Y[i]-(i+1));
			if(x<=y) ret +=Rbt.total(y+1)-Rbt.total(x);
			else ret +=Rbt.total(N2+2)-Rbt.total(x) + Rbt.total(y+1);
			
			cout<<ret<<endl;
		}
	}
	
}

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	V set(int e,V v) { add(e,v-val[e]);}
};

BIT<ll,20> lbt,rbt;

int N,Q;
int X,T,Y,Z;

void solve() {
	int i,j,k,l,r,x,y,z,t; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>s>>t>>y>>z;
		if(s=="L") {
			y += t;
			y = ((y%(2*N))+2*N)%(2*N);
			lbt.add(y+1,z);
		}
		if(s=="R") {
			y -= t;
			y = ((y%(2*N))+2*N)%(2*N);
			rbt.add(y+1,z);
		}
		if(s=="C") {
			ll sum=0;
			
			ll L=y+t,R=z-1+t;
			L = ((L%(2*N))+2*N)%(2*N);
			R = ((R%(2*N))+2*N)%(2*N);
			if(R<L) sum += lbt.total(R+1) + lbt.total(2*N)-lbt.total(L);
			else sum += lbt.total(R+1) - lbt.total(L);
			
			L=2*N-1-(z-1)+t,R=2*N-1-y+t;
			L = ((L%(2*N))+2*N)%(2*N);
			R = ((R%(2*N))+2*N)%(2*N);
			if(R<L) sum += lbt.total(R+1) + lbt.total(2*N)-lbt.total(L);
			else sum += lbt.total(R+1) - lbt.total(L);
			
			L=y-t,R=z-1-t;
			L = ((L%(2*N))+2*N)%(2*N);
			R = ((R%(2*N))+2*N)%(2*N);
			if(R<L) sum += rbt.total(R+1) + rbt.total(2*N)-rbt.total(L);
			else sum += rbt.total(R+1) - rbt.total(L);
			
			L=2*N-1-(z-1)-t,R=2*N-1-y-t;
			L = ((L%(2*N))+2*N)%(2*N);
			R = ((R%(2*N))+2*N)%(2*N);
			if(R<L) sum += rbt.total(R+1) + rbt.total(2*N)-rbt.total(L);
			else sum += rbt.total(R+1) - rbt.total(L);
			
			cout<<sum<<endl;
		}
	}
}

まとめ

区間を[Y[i],Z[i]-1]でなく[Y[i],Z[i])のまま反転処理したので頭が混乱した。
反射系問題は、領域を２倍もしくは無限に拡大して解くのは鉄板ですね。