P7492 [传智杯 #3 决赛] 序列

本文主要是介绍P7492 [传智杯 #3 决赛] 序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

*原题链接*

一道类似势能线段树的题，区间按位或上k，不满足区间可合并的性质，只能暴力的单点修改。

但是考虑按位或的性质，一个数或上另一个数，只会变大或不变，如果我们能找到一个方法，能够判定区间里的数，或上k后是否有改变，就可以避免的暴力了。我一开始想的是线段树里维护一个的数组，表示区间内所有数的二进制表示下某一位是否为1，但这太难写，最后无奈去看官方题解，发现只要维护区间所有数的按位与和And，如果(And&k)==k的话那就不用修改了。那样的话这个题就很简单了，维护最大子段和可以见P4513。至于时间复杂度用类似势能分析的方法分析一波就行了，时间复杂度

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;int n,m,a[N];struct node{int l,r;int sum,lmax,rmax,smax,And;
}tr[N*4];int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}void pushup(node &u,node &l,node &r){u.And=(l.And&r.And);u.sum=l.sum+r.sum;u.lmax=max(l.lmax,l.sum+r.lmax);u.rmax=max(r.rmax,r.sum+l.rmax);u.smax=max(l.rmax+r.lmax,max(l.smax,r.smax));
}void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r){if(l==r){tr[u]={l,r,a[l],a[l],a[l],a[l],a[l]};}else{tr[u].l=l,tr[u].r=r;int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r,int k){if((tr[u].And&k)==k) return;if(tr[u].l==tr[u].r){int x=tr[u].sum|k;tr[u]={tr[u].l,tr[u].r,x,x,x,x,x};}else{int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r,k);if(r>mid) modify(u<<1|1,l,r,k);pushup(u);}
}node query(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r) return tr[u];int mid=(tr[u].l+tr[u].r)>>1;if(r<=mid) return query(u<<1,l,r);if(l>mid) return query(u<<1|1,l,r);node tmp,left=query(u<<1,l,r),right=query(u<<1|1,l,r);pushup(tmp,left,right);return tmp;
}signed main(){n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);while(m--){int opt,l,r,k;opt=read(),l=read(),r=read();if(opt==1){int tmp=query(1,l,r).smax;if(tmp<0) cout<<0<<endl;else cout<<tmp<<endl;}else{k=read();modify(1,l,r,k);}}return 0;
}

这篇关于P7492 [传智杯 #3 决赛] 序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---