題目鏈接：點擊查看

題目大意：給出 $n$ 個數字，需要執行 $m$ 次操作，每次操作分為下列三種類型：

1 l r ：輸出區間 $[l,r]$ 的 $sum$ 和

2 l r：區間 $[l,r]$ 內的每個數都減去 $lowbit(a[i])$

3 l r：區間 $[l,r]$ 內的每個數都加上 $highbit(a[i])$

每個數的 $lowbit$ 和 $highbit$ 分別是二進制下的最低位的 $1$ 和最高位的 $1$

題目分析：如果從二進制下 $1$ 的個數出發，不難發現操作二會使每個數的 $1$ 的個數減一，而操作三不會影響這個個數

又因為操作三只會影響最高位，所以我們不妨將每個數字拆成兩個數字來維護，即 $lower$ 和 $upper$，其中 $upper$ 維護的是每個數字的最高位，$lower$ 維護的是每個數字剩下的，即滿足 $x=lower+upper$

這樣每次操作三可以視為區間乘法，即區間內的每個數都乘以 $2$

操作二的話因為每次都會使得每個數字的 $1$ 的個數減少一，根據勢能，每個數字至多被減少 $30$ 次，所以對于操作二每次可以暴力修改到葉子節點，均攤的時間復雜度最壞不會超過 $nlogn?30$ 的。當且僅當某個數字的 $1$ 的個數等于 $0$ 時，需要同時將 $upper$ 也修改為 $0$，代表這個數字已經變成了 $0$

可以預處理一下 $2$ 的冪次用于 $pushdown$

代碼：

// Problem: Counting Stars // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-7059 // Memory Limit: 131 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=998244353; LL _2[N]; struct Node {int l,r,lazy;LL upper,lower,cnt; }tree[N<<2]; int get(int x) {for(int i=30;i>=0;i--) {if(x>>i&1) {return 1<<i;}}return 0; } void pushup(int k) {tree[k].lower=(tree[k<<1].lower+tree[k<<1|1].lower)%mod;tree[k].upper=(tree[k<<1].upper+tree[k<<1|1].upper)%mod;tree[k].cnt=max(tree[k<<1].cnt,tree[k<<1|1].cnt); } void pushdown(int k) {if(tree[k].lazy) {int lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].lazy+=lz,tree[k<<1|1].lazy+=lz;tree[k<<1].upper=tree[k<<1].upper*_2[lz]%mod;tree[k<<1|1].upper=tree[k<<1|1].upper*_2[lz]%mod;} } void build(int k,int l,int r) {tree[k]={l,r,0,0,0,0};if(l==r) {int x;scanf("%d",&x);tree[k].cnt=__builtin_popcount(x);tree[k].upper=get(x);tree[k].lower=x-tree[k].upper;return;}int mid=(l+r)>>1;build(k<<1,l,mid),build(k<<1|1,mid+1,r);pushup(k); } void update1(int k,int l,int r) {if(tree[k].cnt==0) {return;}if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l==tree[k].r) {tree[k].cnt--;tree[k].lower-=lowbit(tree[k].lower);if(tree[k].cnt==0) {tree[k].upper=0;}return;}pushdown(k);update1(k<<1,l,r),update1(k<<1|1,l,r);pushup(k); } void update2(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].upper=tree[k].upper*2%mod;tree[k].lazy++;return;}pushdown(k);update2(k<<1,l,r),update2(k<<1|1,l,r);pushup(k); } LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return (tree[k].lower+tree[k].upper)%mod;}pushdown(k);return (query(k<<1,l,r)+query(k<<1|1,l,r))%mod; } void init() {_2[0]=1;for(int i=1;i<N;i++) {_2[i]=_2[i-1]*2%mod;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int w;cin>>w;while(w--) {int n;scanf("%d",&n);build(1,1,n);int m;scanf("%d",&m);while(m--) {int op,l,r;scanf("%d%d%d",&op,&l,&r);if(op==1) {printf("%lld\n",query(1,l,r));} else if(op==2) {update1(1,l,r);} else if(op==3) {update2(1,l,r);}}}return 0; }

總結

以上是生活随笔為你收集整理的2021HDU多校8 - 7059 Counting Stars(线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。