[BZOJ5334]-[TJOI2018]数学计算-线段树

说在前面

这应该是me写过的最短的线段树了…

题目

BZOJ5334传送门
看题可进传送门

解法

发现每个数字都有其存在的区间，直接线段树分治即可
然后发现甚至连线段树分治都不用，直接对操作建线段树就可以了，乘法就是单点修改，除法还是单点修改
每个节点维护一下乘积，答案就在根上

下面是代码

#include 
#include 
#include 
using namespace std ;int T , Q , P ;
struct Node{long long mul ;Node *ch[2] ;void update(){mul = ch[0]->mul * ch[1]->mul %P ;}
} w[200005] , *tw = w , *root ;Node *build( int lf , int rg ){Node *nd = ++tw ; nd->mul = 1 ;if( lf != rg ){int mid = ( lf + rg ) >> 1 ;nd->ch[0] = build( lf , mid ) ;nd->ch[1] = build( mid+1,rg ) ;} return nd ;
}void Modify( Node *nd , int lf , int rg , int pos , int val ){if( lf == rg ) return void( nd->mul = val ) ;int mid = ( lf + rg ) >> 1 ;if( pos <= mid ) Modify( nd->ch[0] , lf , mid , pos , val ) ;else Modify( nd->ch[1] , mid+1,rg , pos , val ) ;nd->update() ;
}int main(){scanf( "%d" , &T ) ;while( T -- ){scanf( "%d%d" , &Q , &P ) ;tw = w , root = build( 1 , Q ) ;for( int i = 1 , op , m ; i <= Q ; i ++ ){scanf( "%d%d" , &op , &m ) ;if( op == 1 ) Modify( root , 1 , Q , i , m ) ;else Modify( root , 1 , Q , m , 1 ) ;printf( "%lld\n", root->mul ) ;}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！