Codeforces #255 Div1 C. DZY Loves Fibonacci Numbers

Editorialが衝撃的な問題。
http://codeforces.com/contest/446/problem/C

問題

N要素の数列A[i]が与えられる。
ここに以下のM個のクエリを処理せよ。

1. (l,r)の2値が与えられるので、A[l]～A[r]にフィボナッチ数列F[1]～F[r-l+1]を加算する。
2. (l,r)の2値が与えられるので、A[l]～A[r]の総和を出力する。

解法

幾つかアプローチがあるようだ。

• 行列累乗を使う。
• SegTreeで遅延伝搬させる。
• 3つのBITを使い、定数項およびindex依存の項を管理する。
• 平方分割する。

今回は一番お手軽な平方分割で解く。

事前にフィボナッチ数列の累積和をとっておく。
1番目の種類のクエリ(l,r)に対して、2番目の種類のクエリ(l',r')との交差部分を求めると、1番目の種類のクエリによる増分がO(1)で求められるので、1番目のクエリがたまるまでは2番目のクエリの度に各クエリの増分を累積する。
1番目の種類のクエリがたまってきたら、A[i]を更新する。

全体ではO(N√M)程度で解ける。
剰余計算をやりすぎると4sec制限が結構危ないので注意。

int N,M;
ll A[300100],AS[300100];
ll S[300100];
ll F[300100];
ll mo=1000000009;
vector<pair<int,int> > P;
ll sum[300100];

void solve() {
	int f,i,j,k,l,x,y,r;
	cin>>N>>M;
	FOR(i,N) cin>>A[i+1],AS[i+1]=(AS[i]+A[i+1])%mo;
	
	F[1]=F[2]=S[1]=1;
	S[2]=2;
	for(i=3;i<=300005;i++) {
		F[i]=(F[i-1]+F[i-2])%mo;
		S[i]=(S[i-1]+F[i])%mo;
	}
	
	while(M--) {
		cin>>f>>l>>r;
		if(f==1) {
			P.push_back(make_pair(l,r));
			sum[l]=(sum[l]+1)%mo;
			sum[r+1]=(sum[r+1]+mo-F[r+2-l])%mo;
			sum[r+2]=(sum[r+2]+mo-F[r+1-l])%mo;
			if(P.size()>600) {
				for(i=1;i<=300005;i++) {
					if(i>=2) {
						sum[i]=(sum[i]+sum[i-1]+sum[i-2]);
						while(sum[i]>=mo) sum[i]-=mo;
					}
					A[i]+=sum[i];
					if(A[i]>=mo) A[i]-=mo;
					AS[i]=AS[i-1]+A[i];
					if(AS[i]>=mo) AS[i]-=mo;
				}
				ZERO(sum);
				P.clear();
			}
		}
		else {
			ll ret=0;
			
			FOR(i,P.size()) {
				f=P[i].first;
				x=max(l,P[i].first);
				y=min(r,P[i].second);
				if(x>y) continue;
				ret+=S[y-f+1];
				ret-=S[x-f];
				if(ret>mo) ret-=mo;
				if(ret<0) ret+=mo;
			}
			
			ret=(mo+(ret+AS[r]-AS[l-1])%mo)%mo;
			cout<<ret<<endl;
		}
	}
}

まとめ

Editorialの解法は思い浮かばないわ…。