势能分析,一个数加上自己的 的值,最多 次就会退化为乘二操作。
故若一个区间内全都是 类型的数,就打上乘二的 ,否则就暴力 。
记得取模。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int arr[100005];
set<int> S;
struct node{
int l,r,sum,cnt;
int lztag;
}t[400005];
void pushup(int p){
t[p].cnt=t[p*2].cnt+t[p*2+1].cnt;
t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}
void pushdown(int p){
if(t[p].lztag==1) return;
t[p*2].sum*=t[p].lztag;
t[p*2].sum%=mod;
t[p*2+1].sum*=t[p].lztag;
t[p*2+1].sum%=mod;
t[p*2].lztag*=t[p].lztag;
t[p*2].lztag%=mod;
t[p*2+1].lztag*=t[p].lztag;
t[p*2+1].lztag%=mod;
t[p].lztag=1;
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
t[p].lztag=1;
if(l==r){
t[p].sum=arr[l];
if(S.count(arr[l])){
t[p].cnt=1;
}
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushup(p);
}
int _lowbit(int x){
return x&(-x);
}
void lowbit(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r&&t[p].cnt==t[p].r-t[p].l+1){
t[p].sum*=2;
t[p].sum%=mod;
t[p].lztag*=2;
t[p].lztag%=mod;
return;
}
if(t[p].l==t[p].r){
t[p].sum+=_lowbit(t[p].sum);
if(S.count(t[p].sum)){
t[p].cnt=1;
t[p].sum%=mod;
}
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)/2;
if(mid>=l){
lowbit(p*2,l,r);
}
if(mid<r){
lowbit(p*2+1,l,r);
}
pushup(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].sum;
}
pushdown(p);
int mid=(t[p].l+t[p].r)/2,sum=0;
if(mid>=l){
sum+=query(p*2,l,r);
}
if(mid<r){
sum+=query(p*2+1,l,r);
}
return sum%mod;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
S.insert(0);
for(int i=0;i<=30;i++){
S.insert(1<<i);
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
build(1,1,n);
int q;
cin>>q;
while(q--){
int opt,l,r;
cin>>opt>>l>>r;
if(opt==1){
lowbit(1,l,r);
}else{
cout<<query(1,l,r)%mod<<"\n";
}
}
return 0;
}