您的位置: 首页  >  IT文章  >  牛客练习赛29E位运算？位运算！（位运算线段树>>,<<,|,&）

牛客练习赛29E位运算？位运算！（位运算线段树>>,<<,|,&）

分类: IT文章 • 2024-06-04 22:54:37

链接：https://ac.nowcoder.com/acm/contest/211/E?&headNav=www
来源：牛客网

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

请实现一个数据结构支持以下操作：
区间循环左右移，区间与，区间或，区间求和。

输入描述:

第一行n,q表示数列长度及操作次数。
第二行n个数表示初始序列。
接下来q行表示操作。
操作格式如下：
一行表示一个操作。所有操作形如 opt  l  r  v。
opt=1 表示将区间[l,r]循环右移v位。
opt=2 表示将区间[l,r]循环左移v位。
opt=3 表示将区间[l,r]按位或上v。
opt=4 表示将区间[l,r]按位与上v。
opt=5 询问区间[l,r]的和。
保证opt=1或2时 1 ≤ v ≤ 20
注意：为了优化你的做题体验，操作5也会输入一个v，但是是没有意义的。
注意：循环左右移在20个二进制位的意义下进行

输出描述:

对于每个opt=5的操作，输出一个数表示答案

示例1

输入

10 10
10112 23536 1305 7072 12730 29518 12315 3459 12435 29055
4 5 10 12373
2 1 6 7
5 4 10 24895
1 1 4 8
5 3 7 7767
5 7 9 6127
4 2 8 30971
5 4 10 2663
1 7 10 1
1 2 9 5

输出

2001530
1600111
24611
49482

备注:

1 ≤ N,Q ≤ 2*105 0 ≤ ai < 220
一些说明：
1. 对于00000000000000000101，右移一位后会变成10000000000000000010
2. 不是区间位移，是区间中的每一个数的二进制位的位移
 
和FZU2105有类似之处，只不过把位运算换成了异或运算，之前写过一篇题解：https://blog.****.net/qq_43906000/article/details/102422600
 
很显然，或运算和与运算在二进制的状态表示下只是区间覆盖而已，所以一个标记就够了，&0的任何数都是0，|1的任何数都是1，其他的不变。
接下来就是位运算的操作了，这个位运算有点特别，我们可以直接模拟就好了，然后打上标记，由于二进制的位数是确定的就，所以左移（<<）x位，相当于右移20-x位。反之亦然。不过有点奇怪的是
tree[i]=p[(i+val)%nb]
 这种写法应该是代表左移的，那么也就是说右移的应该是20-x位，但这么写就不对了。。。
 
接下来需要注意的是位移的同时，不仅要把二进制下的数移走，同时还要移走懒标记！！！这个WA了n发。。。
 
以下是pushdown的代码，也是核心代码：
void pushdown(int l,int r,int rt)
{
    int mid=(l+r)>>1;
    if(tree[rt].f1){//位运算
        int p[21],ps[21],p1[21],ps1[21];
        for (int i=0; i<nb; i++) {
            p[i]=tree[ls].sum[i];p1[i]=tree[ls].f2[i];
            ps[i]=tree[rs].sum[i];ps1[i]=tree[rs].f2[i];
        }
        tree[ls].f1+=tree[rt].f1;
        tree[rs].f1+=tree[rt].f1;
        for (int i=0; i<nb; i++){
            tree[ls].sum[i]=p[(i+tree[rt].f1)%nb];
            tree[rs].sum[i]=ps[(i+tree[rt].f1)%nb];
            tree[ls].f2[i]=p1[(i+tree[rt].f1)%nb];
            tree[rs].f2[i]=ps1[(i+tree[rt].f1)%nb];
        } 
        tree[rt].f1=0;
    }
    for (int i=0; i<nb; i++){
        if (tree[rt].f2[i]!=-1) {//区间覆盖的标记传递
            tree[ls].sum[i]=(mid-l+1)*tree[rt].f2[i];
            tree[rs].sum[i]=(r-mid)*tree[rt].f2[i];
            tree[ls].f2[i]=tree[rt].f2[i];
            tree[rs].f2[i]=tree[rt].f2[i];
            tree[rt].f2[i]=-1;
        }
    }
}
接下来询问操作的时候如果还像我之前FZU2105那么写的话就会T（我就是这样T了n发的）。。。所以也需要注意拆位的时候尽量在函数里面拆位，不要每拆一位就跑一遍函数。由于加了快读所以跑起来挺快的，1400ms+
 
以下是AC代码：
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1

const int mac=2e5+10;
const int nb=20;

struct Tree
{
    int sum[21],f1,f2[21];//f1代表位运算，f2代表或与运算 
}tree[mac<<2];
int a[mac];

void build(int l,int r,int rt)
{
    for (int i=0; i<nb; i++) tree[rt].f2[i]=-1;
    if (l==r){
        for (int i=0; i<nb; i++)
            if (a[l]&(1<<i)) tree[rt].sum[i]++;
        return;    
    }
    int mid=(l+r)>>1;
    build(lson);build(rson);
    for (int i=0; i<nb; i++) 
        tree[rt].sum[i]=tree[ls].sum[i]+tree[rs].sum[i];
}

void pushdown(int l,int r,int rt)
{
    int mid=(l+r)>>1;
    if(tree[rt].f1){
        int p[21],ps[21],p1[21],ps1[21];
        for (int i=0; i<nb; i++) {
            p[i]=tree[ls].sum[i];p1[i]=tree[ls].f2[i];
            ps[i]=tree[rs].sum[i];ps1[i]=tree[rs].f2[i];
        }
        tree[ls].f1+=tree[rt].f1;
        tree[rs].f1+=tree[rt].f1;
        for (int i=0; i<nb; i++){
            tree[ls].sum[i]=p[(i+tree[rt].f1)%nb];
            tree[rs].sum[i]=ps[(i+tree[rt].f1)%nb];
            tree[ls].f2[i]=p1[(i+tree[rt].f1)%nb];
            tree[rs].f2[i]=ps1[(i+tree[rt].f1)%nb];
        } 
        tree[rt].f1=0;
    }
    for (int i=0; i<nb; i++){
        if (tree[rt].f2[i]!=-1) {
            tree[ls].sum[i]=(mid-l+1)*tree[rt].f2[i];
            tree[rs].sum[i]=(r-mid)*tree[rt].f2[i];
            tree[ls].f2[i]=tree[rt].f2[i];
            tree[rs].f2[i]=tree[rt].f2[i];
            tree[rt].f2[i]=-1;
        }
    }
}

void update(int l,int r,int rt,int L,int R,int val,int id)
{
    if (l>=L && r<=R){
        if (id==1){
            int p[21],p1[21];
            for (int i=0; i<nb; i++) 
                p[i]=tree[rt].sum[i],p1[i]=tree[rt].f2[i];
            for (int i=0; i<nb; i++) 
                tree[rt].sum[i]=p[(i+val)%nb],tree[rt].f2[i]=p1[(i+val)%nb];
            tree[rt].f1+=val;
        }
        else if (id==2) 
            for (int i=0; i<nb; i++) 
                {if (val&(1<<i)) tree[rt].sum[i]=(r-l+1),tree[rt].f2[i]=1;}
        else 
            for (int i=0; i<nb; i++)
                {if (!(val&(1<<i))) tree[rt].sum[i]=0,tree[rt].f2[i]=0;}
        return;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if (mid>=L) update(lson,L,R,val,id);
    if (mid<R) update(rson,L,R,val,id);
    for (int i=0; i<nb; i++) 
        tree[rt].sum[i]=tree[ls].sum[i]+tree[rs].sum[i];
}

ll query(int l,int r,int rt,int L,int R)
{
    ll ans=0;
    if (l>=L && r<=R){
        for (int i=0; i<nb; i++)
            ans+=tree[rt].sum[i]*(1ll<<i);
        return ans;
    } 
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if (mid>=L) ans+=query(lson,L,R);
    if (mid<R) ans+=query(rson,L,R);
    return ans; 
}

void in(int &x)
{
    int f=0;
    char ch=getchar();
    while (ch>'9' || ch<'0') ch=getchar();
    while (ch>='0' && ch<='9') f=(f<<1)+(f<<3)+ch-'0',ch=getchar();
    x=f;
}

void print(ll x)
{
    if (x>=10)
        print(x/10);
    putchar(x%10+'0');
}

int main()
{int n,q;
    in(n);in(q);
    for (int i=1; i<=n; i++) in(a[i]);
    build(1,n,1);
    while (q--){
        int opt,l,r,val;
        in(opt);in(l);in(r);in(val);
        if(opt==1) update(1,n,1,l,r,val,1);//>>
        else if (opt==2) update(1,n,1,l,r,nb-val,1);//<<
        else if (opt==3) update(1,n,1,l,r,val,2);
        else if (opt==4) update(1,n,1,l,r,val,3);
        else {
            ll ans=query(1,n,1,l,r);
            print(ans);
            putchar('
');
        }
    }
    return 0;
}

相关推荐