竞赛讨论区 > 求解,为什么我的线段树一直RE?数据范围是100w啊
头像
Revenant
编辑于 2018-08-19 09:16
+ 关注

求解,为什么我的线段树一直RE?数据范围是100w啊

#include <stdio.h>
#define ll long long
#define MAXN 1100000
#define Mod 1000000007

struct ST{
    ll val;
    int l,r;
} st[MAXN*5];

void build( int id , int l , int r ){
    st[id].val = 1;
    st[id].l = l;
    st[id].r = r;
    if( l == r )
        return ;
    int mid = ( l+r )/2;
    build( id*2,l,mid );
    build( id*2+1,mid+1,r );
}

void updata( int id , int l , int r , int val , bool flag ){
    if( st[id].l == l && st[id].r == r ){
        if( flag )
            st[id].val = st[id].val * val % Mod;
        else
            st[id].val /= val;
        return ;
    }
    int mid = ( st[id].l + st[id].r )/2;
    if( mid<l )
        updata( id*2+1,l,r,val,flag );
    else if( mid>=r )
        updata( id*2,l,r,val,flag );
    st[id].val = st[id*2].val * st[id*2+1].val % Mod;
}

ll query( int id , int l , int r ){
    if( st[id].l == l && st[id].r == r )
        return st[id].val;
    int mid = ( st[id].l + st[id].r )/2;
    if( mid <= l )
        return query( id*2+1,l,r );
    else if( mid > r ){
        return query( id*2,l,r );
    }else {
        return query( id*2,l,mid ) * query( id*2+1,mid+1,r ) % Mod;
    }
}

int main(){
//    freopen( "in.txt","r",stdin );
    int n,m;
    while( ~scanf( "%d%d",&n,&m ) ){
        build( 1,1,n );
        int op,y,z;
        while( m-- ){
            scanf( "%d%d%d",&op,&y,&z );
            if( op == 1 ){ 
                updata( 1,y,y,z,1 );
            }else if( op == 2 ){ 
                updata( 1,y,y,z,0 );
            }else{ 
                printf( "%lld\n",query( 1,y,z ) );
            } 
        }
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐