ZZULIOJ 2699: 二进制与、平方和（线段树）

2699: 二进制与、平方和

#include<stdio.h>typedef long long LL;
const int N = 300010, MOD = 998244353;
LL a[N];struct Node
{
    int l,r,sum,cnt[25];
}tr[N*4];void pushup(int u)
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%MOD;for(int i=0;i<25;i++) tr[u].cnt[i]=tr[u<<1].cnt[i]+tr[u<<1|1].cnt[i];
}void build(int u,int l,int r)
{
    if(l==r){
    for(int i=0;i<25;i++) tr[u].cnt[i]=(a[l]>>i&1);tr[u].l=l,tr[u].r=r;tr[u].sum=a[l]*a[l]%MOD;}else{
    int mid=(l+r)>>1;tr[u].l=l,tr[u].r=r;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int l,int r,int x)
{
    if(tr[u].l==tr[u].r){
    int sum=0;for(int i=0;i<25;i++){
    if(tr[u].cnt[i]&&(x>>i&1)) sum|=1<<i;else tr[u].cnt[i]=0;}tr[u].sum=(LL)sum*sum%MOD;}if(tr[u].l>=l&&tr[u].r<=r){
    bool flag=true;for(int i=0;i<25;i++)if(tr[u].cnt[i]&&(x>>i&1)==0){
    flag=false;break;}if(flag) return ;} int mid=(tr[u].l+tr[u].r)>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x);pushup(u);
}int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;else{
    int mid=(tr[u].l+tr[u].r)>>1;int sum=0;if(l<=mid) sum=(sum+query(u<<1,l,r))%MOD;if(r>mid) sum=(sum+query(u<<1|1,l,r))%MOD;return sum;	}
}int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);build(1,1,n);int m;scanf("%d",&m);while(m--){
    int k,l,r,x;scanf("%d%d%d",&k,&l,&r);if(k==1){
    scanf("%d",&x);modify(1,l,r,x);}else printf("%d\n",query(1,l,r));}return 0;
}