Codeforces 446(#255 Div1) C. DZY Loves Fibonacci Numbers

問題

フィボナッチ数のi番目をF[i]とする。
長さnの数列a[i]が与えられる。次のようなクエリがq個来るので処理せよ。

1 l r : l≦i≦rなるiに対してa[i]:=a[i] + F[i-l+1]と更新する
2 l r : l≦i≦rなるiに対してa[i]の和をmod 10^9 + 9で出力する。

制約条件

n, q≦30万

方針

セグメント木のほうが楽な気がしたけど、平方分割への愛が抑えられなかったため、平方分割してみたら通った(3.5s)。

各バケットごとに、そのバケット内のa[i]の和,
バケットの一番最初のa[i]に足すべきフィボナッチ数,
「その直前のフィボナッチ数」を持っておく。

後ろのふたつをバケットごとに持っておけば、フィボナッチ数の漸化式の線形性から、
バケットのi番目の要素が線形時間で求まるし、
バケット全体にフィボナッチ数列を足しこむ操作もO(1)でできる。

バケットからはみ出た部分はa[i]を直接更新する。
このとき、i番目のフィボナッチ数とi番目までのフィボナッチ数の和を前計算しておけば、a[i]にいくつを足せばよいかがそれぞれO(1)時間でわかる。

ソースコード

const int mod = (int)1e9 + 9;
const int MX = 310000;
const int SZ = 550;
const int NUM = (MX + SZ - 1) / SZ;

int sum[MX], fib[MX];

int n, q;
int a[MX];
int b[NUM], c[NUM], s[NUM];

inline ll calc(int bkt, int l, int r){
	int x = b[bkt], y = c[bkt];
	ll res = 0;
	
	rep(i, l){
		swap(y, x);
		y += x;
		if(y >= mod) y -= mod;
	}
	l += bkt * SZ; r += bkt * SZ;
	while(l < r){
		res += a[l++] + y;
		swap(y, x);
		y += x;
		if(y >= mod) y -= mod;
	}
	return res % mod;
}
inline void add(int bkt, int l, int r, int idx){
	l += bkt * SZ; r += bkt * SZ;
	while(l < r){
		s[bkt] += fib[idx];
		a[l] += fib[idx];
		if(s[bkt] >= mod) s[bkt] -= mod;
		if(a[l] >= mod) a[l] -= mod;
		l++; idx++;
	}
}
int main(){
	fib[1] = sum[1] = 1;
	rep(i, MX - 2){
		fib[i + 2] = fib[i + 1] + fib[i];
		if(fib[i + 2] >= mod) fib[i + 2] -= mod;
		
		sum[i + 2] = sum[i + 1] + fib[i + 2];
		if(sum[i + 2] >= mod) sum[i + 2] -= mod;
	}
	
	
	scanf("%d%d", &n, &q);
	rep(i, n){
		scanf("%d", a + i);
		s[i / SZ] += a[i];
		if(s[i / SZ] >= mod) s[i / SZ] -= mod;
	}
	
	while(q--){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		y--;
		
		if(x == 1){
			if(y / SZ < z / SZ){
				add(y / SZ, y % SZ, SZ, 1);
				add(z / SZ, 0, z % SZ, z / SZ * SZ - y + 1);
				
				int rem = SZ - y % SZ + 1 - (y / SZ + 1) * SZ;
				y /= SZ; z /= SZ; y++;
				
				while(y < z){
					s[y] += sum[(y + 1) * SZ + rem - 1] - sum[y * SZ + rem - 1];
					b[y] += fib[y * SZ + rem - 1];
					c[y] += fib[y * SZ + rem];
					
					if(s[y] < 0) s[y] += mod;
					if(s[y] >= mod) s[y] -= mod;
					if(b[y] >= mod) b[y] -= mod;
					if(c[y] >= mod) c[y] -= mod;
					
					y++;
				}
				
			}
			else{
				add(y / SZ, y % SZ, z % SZ, 1);
			}
		}
		else{
			ll ans = 0;
			if(y / SZ < z / SZ){
				ans += calc(y / SZ, y % SZ, SZ);
				ans += calc(z / SZ, 0, z % SZ);
				y /= SZ; z /= SZ; y++;
				while(y < z) ans += s[y++];
			}
			else{
				ans = calc(y / SZ, y % SZ, z % SZ);
			}
			printf("%d\n", (int)(ans % mod));
		}
	}
	return 0;
}