本文主要是介绍【FZU】2105 Digits Count 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【FZU】2105 Digits Count
题目分析：与、或、异或三种操作都是每一位相互独立的，所以可以将线段树建四棵，分别对应一位，and和or操作相当于覆盖操作，xor操作相当于反转操作，就和普通的线段树方法类似，设立两个lazy标记即可。查询的时候求得每一位的1的个数*权重（1，2，4，8），全部累加就是答案。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define rt o , l , r
#define root 1 , 0 , n - 1
#define mid ( ( l + r ) >> 1 )const int MAXN = 1000005 ;int Sum[4][MAXN << 2] ;
int Xor[4][MAXN << 2] ;
int Set[4][MAXN << 2] ;int n , m ;void pushup ( int o ) {rep ( i , 0 , 4 ) Sum[i][o] = Sum[i][ls] + Sum[i][rs] ;
}void pushdown ( int o , int l , int r ) {int m = mid ;rep ( i , 0 , 4 ) {if ( ~Set[i][o] ) {Set[i][ls] = Set[i][rs] = Set[i][o] ;Sum[i][ls] = Set[i][o] ? m - l + 1 : 0 ;Sum[i][rs] = Set[i][o] ? r - m : 0 ;Xor[i][ls] = Xor[i][rs] = 0 ;Set[i][o] = -1 ;}if ( Xor[i][o] ) {Sum[i][ls] = m - l + 1 - Sum[i][ls] ;Sum[i][rs] = r - m - Sum[i][rs] ;Xor[i][ls] ^= 1 ;Xor[i][rs] ^= 1 ;Xor[i][o] = 0 ;}}
}void build ( int o , int l , int r ) {rep ( i , 0 , 4 ) Set[i][o] = -1 , Xor[i][o] = 0 ;if ( l == r ) {int x ;scanf ( "%d" , &x ) ;rep ( i , 0 , 4 ) {Sum[i][o] = ( ( x >> i ) & 1 ) ;//printf ( ":%d" , x & ( 1 << i ) ) ;}//printf ( "\n" ) ;return ;}int m = mid ;build ( lson ) ;build ( rson ) ;pushup ( o ) ;
}void update ( int L , int R , int op , int v , int o , int l , int r ) {if ( L <= l && r <= R ) {if ( op == 0 ) {rep ( i , 0 , 4 ) {int tmp = ( ( v >> i ) & 1 ) ;if ( tmp == 0 ) {Sum[i][o] = 0 ;Set[i][o] = 0 ;Xor[i][o] = 0 ;}}} else if ( op == 1 ) {rep ( i , 0 , 4 ) {int tmp = ( ( v >> i ) & 1 ) ;if ( tmp ) {Sum[i][o] = r - l + 1 - Sum[i][o] ;Xor[i][o] ^= tmp ;}}} else {rep ( i , 0 , 4 ) {int tmp = ( ( v >> i ) & 1 ) ;if ( tmp == 1 ) {Sum[i][o] = r - l + 1 ;Set[i][o] = 1 ;Xor[i][o] = 0 ;}}}return ;}int m = mid ;pushdown ( rt ) ;if ( L <= m ) update ( L , R , op , v , lson ) ;if ( m < R ) update ( L , R , op , v , rson ) ;pushup ( o ) ;
}int query ( int L , int R , int i , int o , int l , int r ) {if ( L <= l && r <= R ) return Sum[i][o] ;int m = mid ;pushdown ( rt ) ;if ( R <= m ) return query ( L , R , i , lson ) ;if ( m < L ) return query ( L , R , i , rson ) ;return query ( L , R , i , lson ) + query ( L , R , i , rson ) ;
}void solve () {char buf[10] ;int v , L , R ;scanf ( "%d%d" , &n , &m ) ;build ( root ) ;while ( m -- ) {scanf ( "%s" , buf ) ;if ( buf[0] == 'A' ) {scanf ( "%d%d%d" , &v , &L , &R ) ;update ( L , R , 0 , v , root ) ;} else if ( buf[0] == 'X' ) {scanf ( "%d%d%d" , &v , &L , &R ) ;update ( L , R , 1 , v , root ) ;} else if ( buf[0] == 'O' ) {scanf ( "%d%d%d" , &v , &L , &R ) ;update ( L , R , 2 , v , root ) ;} else {scanf ( "%d%d" , &L , &R ) ;int x = 0 ;rep ( i , 0 , 4 ) {x += ( 1 << i ) * query ( L , R , i , root ) ;//printf ( "debug --%d\n" , x ) ;}printf ( "%d\n" , x ) ;}}
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- ) solve () ;return 0 ;
}这篇关于【FZU】2105 Digits Count 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
