2021HDU多校8 - 7059 Counting Stars(线段树)

题目链接：点击查看

题目大意：给出 $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\ast 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(线段树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。