【红旗杯?】补题

D. Lowbit

输入一个数组a，对a数组有两种操作
1.l，r ： $[l，r]$区间的$a_i+=lowbit(a_i)$
2.l，r ：询问[l，r]区间和，取模998244353
$1\le a_i\le 998244352$
思路：
一个数log n 次lowbit后，会变成2的次方，以后再lowbit，就相当于乘以2

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int maxn=2e5+5;
const ll mod=998244353; 
const int N=5e5+5;
int t,n,q,vis[N];
ll tree[N],a[maxn],lz[N];
ll lowbit(ll x){
    
	return x&(-x);
}
void build(int rt,int l,int r){
    
	vis[rt]=tree[rt]=0;lz[rt]=1;
	if(l==r){
    
		tree[rt]=a[l];
		if(a[l]==lowbit(a[l])){
    
			vis[rt]=1;
		}
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	if(vis[rt<<1]&&vis[rt<<1|1])vis[rt]=1;
	tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%mod;
}
void pushdown(int rt){
    
	if(lz[rt]<=1)return;
	tree[rt<<1]*=lz[rt];
	tree[rt<<1]%=mod;
	tree[rt<<1|1]*=lz[rt];
	tree[rt<<1|1]%=mod;
	lz[rt<<1]*=lz[rt];
	lz[rt<<1]%=mod; 
	lz[rt<<1|1]*=lz[rt];
	lz[rt<<1|1]%=mod;
	lz[rt]=1;
}
void update(int rt,int l,int r,int x,int y){
    
	if(x<=l&&r<=y&&vis[rt]){
    
		tree[rt]*=2;
		tree[rt]%=mod;
		lz[rt]*=2;
		lz[rt]%=mod;
		return;
	}
	if(l==r&&l>=x&&l<=y){
    
		tree[rt]+=lowbit(tree[rt]);
		if(tree[rt]==lowbit(tree[rt])){
    
			vis[rt]=1;tree[rt]%=mod;
		}
		
		return;
	}
	int mid=(l+r)>>1;
	pushdown(rt);
    if(x<=mid)update(lson,x,y);
    if(y>mid)update(rson,x,y);
    tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%mod;
    if(vis[rt<<1]&&vis[rt<<1|1])vis[rt]=1;
}
ll query(int rt,int l,int r,int x,int y){
    
	if(x<=l&&r<=y)return tree[rt];
	int mid=(l+r)>>1;
	ll ans=0;
	pushdown(rt);
	if(x<=mid)ans=(ans+query(lson,x,y))%mod;
	if(y>mid)ans=(ans+query(rson,x,y))%mod;
	return ans;
}
int main(){
    
    scanf("%d",&t);
    while(t--){
    
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    
    		scanf("%lld",&a[i]);
		}
		build(1,1,n);
		scanf("%d",&q);
		while(q--){
    
			int op,l,r;
			scanf("%d%d%d",&op,&l,&r);
			if(op==1){
    
				update(1,1,n,l,r);
			}
			else printf("%lld\n",query(1,1,n,l,r));
		}
	}
}