记录编号	322172	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2016-10-14 19:31:49	内存使用	0.48 MiB

#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
const int maxn = 10010;
const int mod = 998244353;
int block[maxn],f[maxn],c[maxn];
int f1[maxn],f2[maxn],size,n;
void add(int s,int t){
	int l = block[s],r = block[t];
	if(l == r){
		for(int i=s;i <= t;++i){
			(c[i] += f[i-s+1]) %= mod;
		}return;
	}
	for(int i=s;block[i] == l;++i) (c[i] += f[i-s+1]) %= mod;
	for(int i=t;block[i] == r;--i) (c[i] += f[i-s+1]) %= mod;
	for(int i=l+1;i<r;++i){
		(f1[i] += f[((i-1)*size+1) - s + 1]) %= mod;
		(f2[i] += f[((i-1)*size+2) - s + 1]) %= mod;
	}return;
}
int query(int pos){
	int b = block[pos];
	int l = (b-1)*size + 1,r = cat_min(b*size,n);
	(c[l] += f1[b]) %= mod;
	(c[l+1] += f2[b]) %= mod;
	int a = f1[b] % mod,d = f2[b] % mod,e;f1[b] = f2[b] = 0;
	for(int i=l+2;i<=r;++i){
		e = (a+d) % mod;
		(c[i] += e) %= mod;
		a = d;d = e;
	}return c[pos] % mod;
}
int main(){
	freopen("chenyao_fib_game.in","r",stdin);
	freopen("chenyao_fib_game.out","w",stdout);
	int m;read(n);read(m);
	f[1] = f[2] = 1;size = sqrt(n+0.5);
	for(int i=1;i<=n;++i){
		block[i] = (i - 1)/size + 1;
		if(i < 3) continue;
		f[i] = (f[i-1] + f[i-2])%mod;
	}
	for(int i=1,cmd,x,l,r;i<=m;++i){
		read(cmd);
		if(cmd){
			read(l);read(r);
			add(l,r);
		}else{
			read(x);
			printf("%d\n",query(x) % mod);
		}
	}
}