记录编号	461202	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2017-10-19 15:47:32	内存使用	0.83 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    char tmp = getc();
    int res = 0;
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

#define MAXN (10010)
#define MOD (998244353)

inline void init(void);
inline void work(void);
inline void Sum(int &a, int b);
inline void change(int l, int r);
inline int query(int x);

int fib[MAXN] = {0, 1};
int N, Q, M, block;
int pos[MAXN], st[MAXN], ed[MAXN];
int sign1[MAXN], sign2[MAXN], s[MAXN];

int main() { 
#ifndef LOCAL
	freopen("chenyao_fib_game.in", "r", stdin);
	freopen("chenyao_fib_game.out", "w", stdout);
#endif
    init();
    work();
    return 0;
}

inline void init(void) { 
    N = read(), Q = read();
    for(int i = 2; i <= N; ++i)
        fib[i] = (fib[i-1] + fib[i-2]) % MOD;
    block = (int)sqrt(N);
    if(N % block) M = N / block + 1;
    else M = N / block;
    for(int i = 1; i <= N; ++i)
        pos[i] = (i-1) / block + 1;
    for(int i = 1; i <= M; ++i) { 
        st[i] = (i-1) * block + 1;
        ed[i] = min(i * block, N);
    }
}

inline void change(int l, int r) { 
    if(pos[l] == pos[r])
        for(; r >= l; --r)
            Sum(s[r], fib[r-l+1]);
    else { 
        for(int i = l; i <= ed[pos[l]]; ++i)
            Sum(s[i], fib[i-l+1]);
        for(int i = st[pos[r]]; i <= r; ++i)
            Sum(s[i], fib[i-l+1]);
        for(int i = pos[l] + 1; i < pos[r]; ++i) { 
            Sum(sign1[i], fib[st[i]-l+1]);
            Sum(sign2[i], fib[st[i]-l+2]);
        }
    }
}

inline void Sum(int &a, int b) { a = (a + b) % MOD;}

inline int query(int x) { 
    int pre = sign1[pos[x]], now = sign2[pos[x]];
    if(x == st[pos[x]]) return (s[x] + pre) % MOD;
    if(x == st[pos[x]] + 1) return (s[x] + now) % MOD;
    for(int i = st[pos[x]] + 2; i <= x; ++i) { 
        now = now + pre;
        pre = now - pre;
        now %= MOD;
    }
    return (s[x] + now) % MOD;
}

inline void work(void) { 
    for(int i = 1, l, r; i <= Q; ++i)
        if(read()) { 
            l = read(), r = read();
            change(l, r);
        } else printf("%d\n", query(read()));
    return ;
}