2019银川网络赛 A. Simple Data Structures

小咪咪 2024-04-18 15:22 69阅读 0赞

宁夏理工办这个网络赛体验真心不好，讲题，

## Description ##

You've got an array a, consisting of n integers a1,a2,...,an. You are allowed to perform four operations on this array:

1.  `l r`: Calculate the sum of current array elements on the segment \[l,r\], that is, count value a\[l\] + a\[l+1\] +...+a\[r\].
2.  `l r x`: Apply the xor(^) operation of the given number x to each array element on segment \[l, r\]
3.  `l r x`: Apply the or(|) operation of the given number x to each array element on segment \[l, r\]
4.  `l r x`: Apply the and(&) operation of the given number x to each array element on segment \[l, r\] You've got a list of m operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.

## Input ##

The first row contains the integer n(1<=n<=1e5)- the size of the array

The second line contains the space-separated integers a1,a2... an (1<=ai<=1e6)- initial array

The third line contains the integer m(1<=m<=5e4)- the operands of the array,

The following m rows are four operations, l,r,x(1<=l<=r<=n,1<=x<=1e6)

## Output ##

For each query of type 1 print in a single line the sum of numbers on the given segment. Print the answers to the queries in the order in which the queries go in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64d specifier.

## Examples ##

### input : ###

5
    1 1 1 1 1
    7
    1 1 5
    2 1 2 2
    1 1 2
    3 1 2 2
    1 1 2
    4 1 2 2
    1 1 2

### output : ###

5
    6
    6
    4

思路：自己读一下代码就行了，很简单，但是，讲不明白。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    #define lson (root << 1)
    #define rson (root << 1 | 1)
    
    const int N = 1e5 + 7;
    const int maxdigit = 22;
    
    long long arr[N];
    
    struct SegTree
    {
        int l, r;
        long long dig[maxdigit]; // 区间各位上有多少个1
        int lazyset[maxdigit]; // 懒惰标记，向下赋值，为-1表示区间没有被完全覆盖
        int lazyxor[maxdigit]; // 懒惰标记，异或，为1表示区间需要被反转
    } tr[N << 2];
    
    void pushup(int root, int pos)
    {
        tr[root].dig[pos] = tr[lson].dig[pos] + tr[rson].dig[pos];
    }
    
    void pushdown(int root, int pos)
    {
        if (tr[root].lazyset[pos] != -1) // 区间被完全覆盖
        {
            tr[lson].dig[pos] = (tr[lson].r - tr[lson].l + 1) * tr[root].lazyset[pos];
            tr[rson].dig[pos] = (tr[rson].r - tr[rson].l + 1) * tr[root].lazyset[pos];
            tr[lson].lazyset[pos] = tr[rson].lazyset[pos] = tr[root].lazyset[pos];
            tr[root].lazyset[pos] = -1;
            tr[root].lazyxor[pos] = tr[lson].lazyxor[pos] = tr[rson].lazyxor[pos] = 0; // 子节点也被完全覆盖，因此不用异或
        }
        if (tr[root].lazyxor[pos]) // 区间没被完全覆盖且需要异或
        {
            tr[lson].dig[pos] = (tr[lson].r - tr[lson].l + 1) - tr[lson].dig[pos];
            tr[rson].dig[pos] = (tr[rson].r - tr[rson].l + 1) - tr[rson].dig[pos];
            if (tr[lson].lazyset[pos] != -1) // 子节点被完全覆盖，直接反转
                tr[lson].lazyset[pos] ^= 1;
            else
                tr[lson].lazyxor[pos] ^= 1; // 否则进行异或
            if (tr[rson].lazyset[pos] != -1)
                tr[rson].lazyset[pos] ^= 1;
            else
                tr[rson].lazyxor[pos] ^= 1;
            tr[root].lazyxor[pos] = 0;
        }
    }
    
    void build(int root, int l, int r)
    {
        tr[root].l = l;
        tr[root].r = r;
        memset(tr[root].lazyset, -1, sizeof(tr[root].lazyset));
        memset(tr[root].lazyxor, 0, sizeof(tr[root].lazyxor));
        if (l == r)
        {
            for (int i = 0; i < maxdigit; i++)
            {
                if (arr[l] & (1LL << i))
                    tr[root].dig[i]++;
            }
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        for (int i = 0; i < maxdigit; i++)
            pushup(root, i);
    }
    
    void update(int root, int l, int r, int pos, int val)
    {
        if (l <= tr[root].l && r >= tr[root].r)
        {
            if (val == -1) // 异或
            {
                tr[root].dig[pos] = (tr[root].r - tr[root].l + 1) - tr[root].dig[pos];
                if (tr[root].lazyset[pos] != -1) // 如果被完全覆盖则对覆盖标记取反
                    tr[root].lazyset[pos] ^= 1;
                else
                    tr[root].lazyxor[pos] ^= 1; // 否则对异或标记取反
            }
            else
            {
                tr[root].dig[pos] = (tr[root].r - tr[root].l + 1) * val;
                tr[root].lazyset[pos] = val;
                tr[root].lazyxor[pos] = 0; // 区间被完全覆盖，不用异或
            }
            return;
        }
        pushdown(root, pos);
        int mid = (tr[root].l + tr[root].r) >> 1;
        if (l <= mid)
            update(lson, l, r, pos, val);
        if (r > mid)
            update(rson, l, r, pos, val);
        pushup(root, pos);
    }
    
    long long query(int root, int l, int r, int pos)
    {
        if (l <= tr[root].l && r >= tr[root].r)
            return tr[root].dig[pos];
        pushdown(root, pos);
        int mid = (tr[root].l + tr[root].r) >> 1;
        long long ans = 0;
        if (l <= mid)
            ans += query(lson, l, r, pos);
        if (r > mid)
            ans += query(rson, l, r, pos);
        return ans;
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%I64d", &arr[i]);
        build(1, 1, n);
        int m;
        scanf("%d", &m);
        while (m--)
        {
            int op, l, r, val;
            scanf("%d %d %d", &op, &l, &r);
            if (op == 4) // 按位且
            {
                scanf("%d", &val);
                for (int i = 0; i < maxdigit; i++)
                {
                    if ((val & (1LL << i)) == 0)
                        update(1, l, r, i, 0);
                }
            }
            else if (op == 3) // 按位或
            {
                scanf("%d", &val);
                for (int i = 0; i < maxdigit; i++)
                {
                    if (val & (1LL << i))
                        update(1, l, r, i, 1);
                }
            }
            else if (op == 2) // 按位异或
            {
                scanf("%d", &val);
                for (int i = 0; i < maxdigit; i++)
                {
                    if (val & (1LL << i))
                        update(1, l, r, i, -1);
                }
            }
            else if (op == 1) // 查询区间和
            {
                long long ans = 0;
                for (int i = 0; i < maxdigit; i++)
                    ans += query(1, l, r, i) * (1LL << i);
                printf("%I64d\n", ans);
            }
        }
        return 0;
    }

自己代码：

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50;
    const int md=30;
    #define ll long long
    struct Node{int l,r,xv[35],sv[35],dig[35];}t[M<<2];
    int n,a[M],m;
    void up(int k,int pos){t[k].dig[pos]=t[k*2].dig[pos]+t[k*2+1].dig[pos];}
    void build(int k,int l,int r){
        t[k].l=l;t[k].r=r;
        memset(t[k].xv,0,sizeof(t[k].xv));
        memset(t[k].sv,-1,sizeof(t[k].sv));
        if(l==r){
            for(int i=0;i<md,i++)
               if(a[i]&(1ll>>i))
                    t[k].dig[i]++;
            return ;
        }
        int mid=(l+r)>>1;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
        for(int i=0;i<md;i++)up(k,i);
    }
    void down(int k,int pos){
        if(t[k].sv[pos]!=-1){
            t[k*2].dig[pos]=(t[k*2].r-t[k*2].l+1)*t[k].sv[pos];
            t[k*2+1].dig[pos]=(t[k*2+1].r-t[k*2+1].l+1)*t[k].sv[pos];
            t[k*2].sv[pos]=t[k*2+1].sv[pos]=t[k].sv[pos];
            t[k].sv[pos]=-1;
            t[k*2].xv[pos]=t[k*2+1].xv[pos]=t[k].xv[pos]=0;
        }//如果某个点的赋值有值，那么这个点的异或肯定没有值
        if(t[k].xv[pos]){
            t[k*2].dig[pos]=(t[k*2].r-t[k*2].l+1)-t[k*2].dig[pos];
            t[k*2+1].dig[pos]=(t[k*2+1].r-t[k*2+1].l+1)-t[k*2+1].dig[pos];
            if(t[k*2].sv[pos]!=-1)t[k*2].sv[pos]V=1;
            else t[k*2].xv[pos]^=1;
            if(t[k*2+1].sv[pos]!=-1)t[k*2+1].sv[pos]V=1;
            else t[k*2+1].xv[pos]^=1;
            t[k].xv[pos]=0;
        }
    }
    void update(int k,int l,int r,int pos,int v){
    //修改的时候，如果是赋值，直接赋值，同时清空异或，
    //如果是异或，修改完本区间之后，判断儿子是否有赋值标记，有赋值，就把赋值标记异或，否则，标记异或标记
        if(l<=t[k].l&&t[k].r<=r){
            if(v==-1){
                t[k].dig[pos]=(t[k].r-t[k].l+1)-t[k].dig[pos];
                if(t[k].sv[pos]!=-1)t[k].sv[pos]^=1;//对这一位的标记取反
                else t[k].xv[pos]^=1;//对异或标记取反
            }else {
                t[k].dig[pos]=(t[k].r-t[k].l+1)*v;
                t[k].sv[pos]=v;
                t[k].xv[pos]=0;//区间异或清0
            }
            return ;
        }
        down(k,pos);
        int mid=(t[k].r+t[k].r)>>1;
        if(l<=mid)update(k*2,l,r,pos,v);
        if(mid<r)update(k*2+1,l,r,pos,v);
        up(k,pos);
    }
    ll query(int k,int l,int r,int pos){
        if(l<=t[k].l&&t[k].r<=r)return t[k].dig[pos];
        down(k,pos);
        int mid=(t[k].r+t[k].l)>>1;
        ll ans=0;
        if(l<=mid)ans+=query(k*2,l,r,pos);
        if(mid<r)ans+=query(k*2+1,l,r,pos);
        return ans;
    }
    
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        build(1,1,n);
        int op,l,r;ll x;
        scanf("%d",&m);
        while(m--){
            scanf("%d",&op);
            switch(op){
                case 1:
                    scanf("%d%d",&l,&r);
                    ll ans=0;
                    for(int i=0;i<md;i++)ans+=query(1,l,r,i)*(1ll<<i);
                    printf("%lld\n",ans);
                    break;
                case 2:
                    scanf("%d%d%lld",&l,&r,&x);
                    for(int i=0;i<md;i++)if(x&(1ll<<i))update(1,l,r,i,-1);
                    break;
                case 3:
                    scanf("%d%d%lld",&l,&r,&x);
                    for(int i=0;i<md;i++)if(x&(1ll<<i))update(1,l,r,i,1);
                case 4:
                    scanf("%d%d%lld",&l,&r,&x);
                    for(int i=0;i<md;i++)if(x&(1ll<<i)==0)update(1,l,r,i,0);
                    break;
            }
        }
        return 0;
    }