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

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
int read(){
	int x=0,f=1;char ch;
	while(ch=getchar(),ch<'!');
	if(ch=='-') f=-1,ch=getchar();
	x=ch-48;
	while(ch=getchar(),ch>'!') x=x*10+ch-48;
	return x*f;
}
const int maxn=101000;
const int mod=998244353;
int n,m,size;
int block[maxn],c[maxn],add[1010][5],f[maxn];

void modify(int l,int r){
	int bl=block[l],br=block[r];
	if(bl==br){
		for(int i=l;i<=r;i++) c[i]=(c[i]+f[i-l+1])%mod;
	}else{
		for(int i=l;block[i]==bl;i++) c[i]=(c[i]+f[i-l+1])%mod;
		for(int i=r;block[i]==br;i--) c[i]=(c[i]+f[i-l+1])%mod;
		for(int i=bl+1;i<br;i++){
			int ml=(i-1)*size+1;
			add[i][1]=(add[i][1]+f[ml-l+1])%mod;
			add[i][2]=(add[i][2]+f[ml-l+2])%mod;
		}
	}
}
int query(int x){
	int bl=block[x],f1=add[bl][1],f2=add[bl][2],ans=0;
	if(x==(bl-1)*size+1)return f1+c[x];
	if(x==(bl-1)*size+2)return f2+c[x];
	for(int i=(bl-1)*size+2;i<x;i++){
		ans=(f1+f2)%mod;
		f1=f2;f2=ans;
	}
	return ans+c[x];
}

int main(){
	freopen("chenyao_fib_game.in","r",stdin);freopen("chenyao_fib_game.out","w",stdout);
	n=read(),m=read(),size=sqrt(n);
	for(int i=1;i<=n;i++)block[i]=(i-1)/size+1;
	f[1]=1;for(int i=2;i<=n;i++)f[i]=(f[i-1]+f[i-2])%mod;
	//for(int i=1;i<=n;i++) printf("%lld ",f[i]);puts("");
	for(int i=1,l,r,x;i<=m;i++){
		int op=read();
		if(op){l=read(),r=read();modify(l,r);}
		else x=read(),printf("%d\n",query(x)%mod);
	}
	getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
5 8
1 1 3
1 2 5
0 3
0 5
0 1
1 1 5
0 4
0 5 

 */