记录编号	321173	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.464 s
提交时间	2016-10-13 15:51:00	内存使用	0.46 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 10005, mod = 998244353;
int N, M, B;
int b[maxn], c[maxn], d[maxn];
int fib[maxn];

void Insert(int l, int r) {
	int bl = b[l], br = b[r];
	if (bl == br) {
		for (int i=l; i<=r; ++i)
			c[i] += fib[i-l+1], c[i] %= mod;
		return;
	}
	for (int i=l; b[i]==bl; ++i) 
		c[i] += fib[i-l+1], c[i] %= mod;
	for (int i=r; b[i]==br; --i) 
		c[i] += fib[i-l+1], c[i] %= mod;
	for (int i=bl+1; i<br; ++i) {
		int p = (i-1)*B+1;
		d[p] += fib[p-l+1], d[p] %= mod;
		++p;
		d[p] += fib[p-l+1], d[p] %= mod;
	}
}
int Query(int p){
	int c1 = (b[p]-1)*B+1, c2 = c1+1;
	if(p==c1) return d[p]+c[p];
	while(c2!=p) {
		d[c2+1] = d[c1]+d[c2];
		d[c2+1] %= mod;
		++c1, ++c2;
	}
	return d[p]+c[p];
}
int main(){
    freopen("chenyao_fib_game.in", "r", stdin); 
    freopen("chenyao_fib_game.out", "w", stdout);

	scanf("%d%d", &N, &M);

	fib[1] = fib[2] = 1;
	for (int i=3; i<=N; ++i) 
		fib[i] = fib[i-1]+fib[i-2], fib[i] %= mod;

	B = (int)sqrt(N);
	for (int i=1; i<=N; ++i) b[i] = (i-1)/B+1;

	for (int i=1,op,a,b; i<=M; ++i)	{
		scanf("%d", &op);
		if (op==1) scanf("%d%d", &a, &b), Insert(a, b);
		else scanf("%d", &a), printf("%d\n", Query(a)%mod);
	}

	return 0;
}