记录编号	352914	评测结果	AAAAAAAAAA
题目名称	[SYZOJ 218]小L的斐波那契数列游戏	最终得分	100
用户昵称	丿Mht丶闪电	是否通过	通过
代码语言	C++	运行时间	3.755 s
提交时间	2016-11-17 18:57:28	内存使用	36.33 MiB

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define MAX 300007
 
using namespace std;
 
typedef long long LL;
 
int n,m,a[MAX];
const LL mod = 998244353;
LL fib[MAX];
struct Tree
{
    int l,r;
    LL sum,f1,f2;
}tree[MAX<<2];
void push_up ( int u )
{
    tree[u].sum = tree[u<<1].sum + tree[u<<1|1].sum;
    tree[u].sum %= mod;
}
void build ( int u , int l , int r )
{
    tree[u].l = l;
    tree[u].r = r;
    tree[u].f1 = tree[u].f2 = 0;
    if ( l == r )
    {
        tree[u].sum = a[l];
        return;
    }
    int mid = l+r>>1;
    build ( u<<1 , l , mid );
    build ( u<<1|1 , mid+1 , r );
    push_up ( u );
}
void init ( )
{
    fib[1] = fib[2] = 1;
    for ( int i = 3 ; i < MAX ; i++ )
    {
        fib[i] = fib[i-1] + fib[i-2];
        fib[i] %= mod;
    }
}
 
LL get ( LL a , LL b , int n )
{
    if ( n == 1 ) return a%mod;
    if ( n == 2 ) return b%mod;
    return (a*fib[n-2]%mod+b*fib[n-1]%mod)%mod;
}
 
LL sum ( LL a , LL b , int n )
{
    if ( n == 1 ) return a;
    if ( n == 2 ) return (a+b)%mod;
    return ((get ( a , b , n+2 )-b)%mod+mod)%mod;
}
 
void push_down ( int u )
{
    int f1 = tree[u].f1;
    int f2 = tree[u].f2;
    int l = tree[u].l;
    int r = tree[u].r;
    int ll = (l+r)/2-l+1;
    int rr = r-(l+r)/2;
    if ( f1 )
    {
        if ( l != r )
        {
            tree[u<<1].f1 += f1;
            tree[u<<1].f1 %= mod;
            tree[u<<1].f2 += f2;
            tree[u<<1].f2 %= mod;
            tree[u<<1].sum += sum ( f1 , f2 , ll );
            tree[u<<1].sum %= mod;
            int x = f1 , y = f2;
            f2 = get ( x , y , ll+2 );
            f1 = get ( x , y , ll+1 );
            tree[u<<1|1].f2 += f2;
            tree[u<<1|1].f2 %= mod;
            tree[u<<1|1].f1 += f1;
            tree[u<<1|1].f1 %= mod;
            tree[u<<1|1].sum += sum ( f1 , f2 , rr );
            tree[u<<1|1].sum %= mod;
        }
        tree[u].f1 = tree[u].f2 = 0;
    }
}
 
void update ( int u , int left , int right )
{
    int l = tree[u].l;
    int r = tree[u].r;
    int mid = l+r>>1;
    if ( left <= l && r <= right )
    {
        tree[u].f1 += fib[l-left+1];
        tree[u].f1 %= mod;
        tree[u].f2 += fib[l-left+2];
        tree[u].f2 %= mod;
        int f1 = fib[l-left+1], f2 = fib[l-left+2];
        tree[u].sum += sum ( f1 , f2 , r-l+1 );
        tree[u].sum %= mod;
        return;
    }
    push_down ( u);
    if ( left <= mid && right >= l )
        update ( u<<1 , left , right );
    if ( left <= r && right > mid )
        update ( u<<1|1 , left , right );
    push_up ( u );
}
 
LL query ( int u , int left , int right )
{
    int l = tree[u].l;
    int r = tree[u].r;
    int mid = l+r>>1;
    if ( left <= l && r <= right )
        return tree[u].sum;
    push_down ( u );
    LL ret = 0;
    if ( left <= mid && right >= l ) 
    {
        ret += query ( u<<1 , left , right );
        ret %= mod;
    }
    if ( left <= r && right > mid )
    {
        ret += query ( u<<1|1 , left , right );
        ret %= mod;
    }
    return ret;
}
 
int main ( )
{
	freopen("chenyao_fib_game.in","r",stdin);
	freopen("chenyao_fib_game.out","w",stdout);
    init ( );
    scanf ( "%d%d" , &n , &m );
    build ( 1 , 1 , n );
    while ( m-- )
    {
        int x,l,r;
        scanf ( "%d" , &x  );
        if ( x == 1 )
        {	scanf("%d%d",&l,&r);
            update ( 1 , l , r );}
        else
        {	scanf("%d",&l);
            printf ( "%lld\n" , query ( 1 , l , l  ) );
		}
    }
}